不知道你是否已经得到了这个问题的答案。 一个简单的技巧是添加一个与所有其他点距离为零的虚拟点。 解决 TSP 并消除虚拟点 - 剩下的就是哈密顿路径。 简单的 ！
Don't know if you ever got an answer to this. The simple trick is to add one dummy point that has a distance of zero to all your other points. Solve the TSP and get rid of the dummy point - what remains is the Hamiltonian Path. Simple !
两者都是 NP 完全问题，因此根据定义，您可以转换输入并使用相同的算法;-)
但基本思想应该可行。 当然，您可能需要更改新路径的生成和成功标准。
编辑：顺便提一句：有一个关于随机算法的建议：http://en.wikipedia.org/wiki/Hamiltonian_path_problem
Both are NP complete problems, so by definition you can convert the input and use the same algorithm ;-)
But the basic idea should work. Of course you may need to change the generation of new paths and the success criteria.
EDIT:BTW:There is a suggestion for a randomized algorithm:http://en.wikipedia.org/wiki/Hamiltonian_path_problem
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
暂无简介
文章 0 评论 0
接受
发布评论
评论（2）
不知道你是否已经得到了这个问题的答案。 一个简单的技巧是添加一个与所有其他点距离为零的虚拟点。 解决 TSP 并消除虚拟点 - 剩下的就是哈密顿路径。 简单的 ！
Don't know if you ever got an answer to this. The simple trick is to add one dummy point that has a distance of zero to all your other points. Solve the TSP and get rid of the dummy point - what remains is the Hamiltonian Path. Simple !
两者都是 NP 完全问题，因此根据定义，您可以转换输入并使用相同的算法;-)
但基本思想应该可行。 当然，您可能需要更改新路径的生成和成功标准。
编辑：
顺便提一句：
有一个关于随机算法的建议：
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
Both are NP complete problems, so by definition you can convert the input and use the same algorithm ;-)
But the basic idea should work. Of course you may need to change the generation of new paths and the success criteria.
EDIT:
BTW:
There is a suggestion for a randomized algorithm:
http://en.wikipedia.org/wiki/Hamiltonian_path_problem