使用字符串重写系统高效构造回文

Question

给定一个具有以下规则的字符串重写系统：

1. c -> a c b
2. c -> b a c a
3. c -> b c b a b

给定一个起始字符串

c

，我想找到一种有效的方法来构造回文。

规则序列 (1, 1, 2) 的构造示例：c (规则 1) -> acb (规则 1) -> aacbb (规则 2) -> aabacabb

我的尝试：

1. 生成排列：我考虑生成一系列重写步骤（n 步骤）的所有排列，但发现它的计算成本很高。
2. 平衡方法：规则2使弦向左不平衡，而规则3使弦向右不平衡。规则 1 是中立的。这促使我探索规则 2 的应用频率是规则 3 的两倍以保持平衡的序列。
3. 最后一个规则约束：最后应用规则 1 不能创建回文，因为它会在中间引入非回文三元组 (acb)。

虽然平衡和最后规则约束减少了搜索空间，但暴力破解仍然是计算密集型的。是否有更多的结构性方法或更严格的约束来有效地解决这个问题？

我知道存在 150 个步骤序列内的解决方案。

Answer 1

尝试每一个规则的排列是非常低效的。许多可以在早期生成非回文时很快被消除并完全修剪。相反，请考虑一种从

c

开始，应用规则，然后开始“取消”两侧匹配字符的方法。如果两边都有不匹配的字符，则进一步的替换不会产生回文，因此您应该尽早退出并尝试应用不同的规则排列。由于这种“取消”，您的字符串将以

c

开头或结尾，或两者兼而有之。

您最初将从

c

开始，如果您再次到达字符串

c

，您就找到了一系列产生回文的规则。通过提前退出，您可以轻松地发现序列必须以

3 1

开头（正如评论中提到的）。每个操作最多有两个选择，为您的搜索提供最坏情况的分支因子

2

（平均为

1.5

）。

您可以采用的下一个优化是缓存以前访问过的状态。如果您已经访问过状态

cabbba

，则没有理由重新评估您可以从该状态继续应用的所有规则，因此只需忽略它/回溯即可。您可能会遇到多个周期，因此用此方法修剪它们将显着提高性能。

最后，通过同时执行两次搜索，将搜索深度减半 - 一次搜索正常应用规则，一次搜索“向后”移动，从所需的最终状态开始执行每个规则的逆操作（也

c

）。例如，将规则 2 应用于

XXXcYYY

会得到

XXXbacaYYY

，但是应用规则 2 的逆会得到

baXXXcYYYa

，因为你正在使用旧字符串并将其替换为

c 中的 

baca。这也意味着您从

c

向外执行取消，而不是从回文的外部向内执行取消，例如

abbcbaa

变为

abcaa

，而不是

bbcba

。

在执行上述操作时，您可以从最终状态向后搜索，并尝试在两次搜索之间的中间相遇，每次搜索的深度都是一半。由于搜索的深度呈指数级增长，因此这可以节省大量工作，即使它使我们的工作量增加一倍。为了在中间相遇，只需将状态/字符串存储在哈希表中进行一次搜索，并在另一次搜索期间搜索相反的状态/字符串。

通过所有这些优化，搜索变得非常快。事实上，我什至没有为求解器编写代码，因为我只能手动求解；只有20条规则，其中大约一半是强制走法。这是到达回文的规则序列，具有中间状态（带有取消）：

c
cba 3
cbb 1
cabbb 3
cbababb 3
cbabbabab 3
cababbab 2
caababb 2
cbabaabab 3
cababaab 2
caababa 2
cbaabab 1
cabaab 2
caaba 2
cbaab 1
caba 2
cbab 1
cab 2
ca 2
cb 1
c 2