基于指定字符串重写系统高效构造回文的方法问询

问题描述 #

给定一套字符串重写系统，包含以下规则：

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

已尝试的解决思路 #

• 全排列生成：尝试生成n步重写的所有规则排列组合，但这种方法计算成本极高，无法高效推进；
• 字符平衡法：分析各规则对字符串左右侧字符的影响：规则2会导致左侧字符失衡，规则3导致右侧失衡，规则1为中性。因此尝试限定「规则2的使用次数为规则3的两倍」，以此维持字符串的整体平衡；
• 最后一步规则约束：发现若最后一步应用规则1，无法生成回文——因为该规则会在字符串中间引入非回文三元组acb。

待解决疑问 #

虽然通过平衡法和最后规则约束缩小了搜索范围，但暴力求解的计算量仍然过大。是否存在更结构化的方法或更严格的约束条件，能够高效找到可行的重写序列？已知150步内存在可行解。

内容的提问来源于stack exchange，提问作者d.na