使用旅行商求解器来决定哈密顿路径

题

这是一个项目，我要求实现对旅行商优化问题启发式，也是汉弥尔顿路径或周期确定的问题。我并不需要与实现本身的帮助，但对我要去的方向的问题。

我已经有基于遗传算法TSP启发：它假设一个完整的图形，用一组随机的解决方案作为一个人口开始，并努力提高人口为许多世代。我也可以用它来解决汉弥尔顿路径或循环的问题？相反，优化得到的最短路径，我只是想检查是否存在一个路径。

现在任何完整的图形将具有在其中的汉弥尔顿路径，所以TSP的启发式将必须被扩展到任何图形。这可以通过，如果有两个城市之间没有路径的边缘设置为无穷大一些的值，并返回，是一个有效哈密尔顿路径的第一路径来完成。

是正确的方式来处理呢？或者我应该使用汉弥尔顿路径不同的启发？我最关心的是它是否是一个可行的办法，因为我可能有点肯定的是TSP优化工作（因为你开始与解决方案，并提高它们），但如果汉弥尔顿路径决胜局会发现在一个固定的数代人的任何路径。

我假设最好的办法是，以测试它自己，但我的时间的限制，我想我会才去这条路线问...（我能找到的，而不是哈密尔顿路径不同的启发式）

解决方案

不知道你是否有一个答案。简单的窍门是添加具有零至所有其他点的距离一个虚拟点。解决TSP和摆脱虚拟点 - 剩下的就是汉弥尔顿路径。简单！

其他提示

两者都是NP完全问题，所以根据定义可以转换输入和使用相同的算法; - ）

但基本的思路应该工作。当然，你可能需要改变的新路径和成功的标准生成。

许可以下： CC-BY-SA 和归因