string - 从给定的单词生成填字游戏最大化交叉点

Question

是否有一些可行的（即多项式时间）算法从一小部分（约 20 个）单词开始构建一个使交叉点数量最大化（或至少“大”）的填字游戏？或者，如果交叉标准不切实际，是否可以最大化填字游戏的密度（在某种意义上）？

我已经用 Python 写了一个详尽的搜索，但是超过六个单词需要的时间太长了……

另请参阅： 生成填字游戏的算法（但那里的答案虽然不错，但并没有真正解决我的问题）。

Answer 1

有一些多项式时间算法吗？

回答：没有。

对于一个简单的版本：如果一个单词结尾的字母与另一个单词开头的字母相同，我们可以将它们连接起来。例如：

cat+tree+element -> Valid
aaa+aaa -> Valid
cab+aboard -> Invalid ('a' != 'b')

问题是：尝试连接尽可能多的单词。

但它相当于哈密顿路径问题，所以我们没有任何多项式时间算法来解决这个问题。

有关详细信息，请参阅：哈密顿路径问题

PS：

对于小（~20）集，您可以尝试启发式搜索或动态规划方法以获得可行的解决方案。