我已经用哈密顿路径玩了一段时间，发现了一些很酷的用法。其中一个是一个难题，目标是连接所有节点形成哈密顿路径。
所以，作为一个新手程序员，我创建了一个非常基本的蛮力图生成器，它可以创建具有哈密顿路径的图。但当我试图将图形大小增加到10x10时，问题就出现了。不用说，暴力在那里是行不通的。
我知道哈密顿路径是一个np完全问题，但有没有一种方法来优化图的生成过程。任何可以在合理时间内创建15x15网格的技巧。
非常感谢你。
最佳答案
你正在寻找所谓的“backsite算法”-从任何哈密顿路径开始，一个很小的路径就可以了（在网格上来回曲折，或者有一个螺旋）。
然后循环随机次数：
选择任一端点
至少有两个且最多有四个相邻顶点；随机选择一个不是起点的哈密顿邻居
如果第二个点不是另一个端点
A.连接你选择的两点-这将生成一个看起来像有尾巴的循环的图形
b.找到导致循环的边（不是刚添加的边，而是它的一个邻居），然后删除它（这是“backsite”步骤）
如果在步骤3中，第二个点是另一个端点，则将这两个端点连接起来（现在将有一个哈密顿循环），并删除任何其他随机边
在每一步，新的图仍然是哈密顿路径。