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）。有没有办法确定最大迭代次数的界限？

任何指向相关概念/相关工作的指针都表示赞赏。

score 1 · Accepted Answer

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

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

前缀： and
的情况给我们一个问题，除非给定的字符串是以某种方式构建的，否则两个规则都不是问题。（变成）。这可以通过以某种方式标记的有向边来检查。如果他们创建了一个循环，那么您将遇到某些字符串的问题，但不会遇到其他字符串。ab -> xyxyc -> 123abcxyc

希望这有帮助。

1 回答 1