algorithm - 反复搜索替换直到收敛

Question

我正在搜索以下问题的名称和有效解决方案:假设我有一个字符串 s='abcdef' 和一组查找/替换规则 Pn

P1: ab -> xy
P2: xyc -> 123
P3: ef -> ab

将这些规则依次应用于 s 我可以得到以下字符串:

1. xycdef
2. 123def
3. 123dab
4. 123dxy

我的目标是达到所有(大多数？)规则都已应用的“稳定”状态(此处:123dxy)。

所以我的问题是，是否有明确定义的方法来处理此类问题？是否对规则有一般约束以避免无限循环(例如，ab -> xy、xy -> ab)。有没有办法确定最大迭代次数的界限？

感谢任何指向相关概念/相关工作的指针。

Answer 1

我会将其转化为图形问题。
在你的情况下，我会有一个名为 ab 的节点，另一个 xy、xyc 等。
节点之间按规则存在有向边。
这里:V={ab, xy, xyc, 123, ef}; E={(ab,xy), (xyz.123), (ef, ab)}

基本检查:
如果在这个阶段你的图表中有循环，那么你就有了真正的问题。

前缀:
ab -> xy 和 xyc -> 123 的情况给我们带来了一个问题，即两个规则不是问题，除非给定的字符串是以某种方式构建的。 (abc 变为 xyc)。这可以用以某种方式标记的有向边来检查。如果它们创建了一个循环，那么您将对某些字符串有问题，但对其他字符串则不会。

希望这对您有所帮助。