algorithm - 哈密​​顿路径生成器算法

Question

我玩哈密顿路径已经有一段时间了，并发现了一些很酷的用途。一个是一种谜题，其目标是连接所有节点以形成哈密顿路径。

所以，作为一个新手程序员，我创建了一个非常基本的蛮力图生成器，它可以创建具有哈密顿路径的图。但是当我尝试将图形大小增加到 10x10 时，问题就出现了。不用说，通过蛮力在那里不起作用。

我了解哈密顿路径是一个 NP 完全问题，但有没有一种方法可以优化图形生成过程。任何可以在合理时间内创建 15x15 网格的技巧。

非常感谢。

Answer 1

您正在寻找所谓的“Backbite 算法” - 从任何哈密顿路径开始，一个微不足道的路径就可以了（在您的网格上来回曲折，或有一个螺旋）。

然后循环随机次数：

1. 选择任一端点

2. 至少有两个，最多四个相邻顶点；随机选择一个不是你开始的终点的哈密顿邻居

3. 如果第二个点不是另一个端点

   一个。连接您选择的两个点 - 这将生成一个看起来像带尾巴的循环的图形

   湾。找到导致循环的边缘（不是您刚刚添加的边缘，而是它的邻居之一），然后将其删除（这是“backbite”步骤）

4. 如果在步骤 3 中第二个点是另一个端点，则加入这两个点（您现在将有一个哈密顿循环），并删除任何其他随机边

在每一步，新图仍然是哈密顿路径。