logo标签列表

最小距离哈密顿路径Javascript

javascriptalgorithmtraveling-salesman
8
我知道这是一个相当常见的问题（tsp一般来说），但我已经被它困扰了一段时间。我要找到给定一组x，y坐标的最小距离哈密顿路径。起点和终点完全是任意的，但它不能形成循环，因此标准的tsp不适用（虽然据说添加一个假节点到所有其他节点的0距离，然后稍后删除它可以解决问题，但我不知道如何做）。
有很多链接到数学论文之类的东西，讨论解决类似问题的算法，但我宁愿使用代码而不是复杂的方程式，我真的不想重新发明轮子。
肯定有一个相当直接的实现在主要语言Java、c#、C++、ruby、javascript、php等中可以解决我的问题的20个节点版本。
编辑：我还要尽可能准确，显然不能完全准确，因为20！是很多排列，但比人类在几分钟内完成的要好或者相同就可以了。
编辑2：为了澄清，我正在使用未加权图上的标准二维坐标。距离A-B == B-A
编辑3：为了消除混乱，这里有一个视觉示例，只有几个点，以显示tsp可能是次优的（这种情况是一个简单的修复，但有更多的节点它可以更极端）。
期望输出：
2
我认为使用与其他所有点距离为零的虚拟点的想法是，TSP答案将使用两个长度为零的链接，一个链接到该虚拟点，另一个从该虚拟点链接。因此，在修改后的问题中，TSP的成本正好是您的哈密顿路径的成本，并且最小化这个成本会产生最小哈密顿路径的成本，您可以通过删除虚拟节点及其链接来恢复它。 - mcdowella
我修改了一个免费的库来实现这个目标：www.chihoang.de/index.php?id=1373。它使用了蚁群优化算法。我用双最小生成树方法对其进行了检查。我不太确定我的方法是否非常科学，但欢迎您来看看？ - Micromega
1个回答
1
看起来这会形成一个闭合回路 :/。在某些配置中，仅仅移除闭合回路中最长的线段并不能为我的问题提供一个好的解决方案。 - stumpedcoder
如果你解决了TSP问题，然后删除最长的线段，那么你必须有更好的路径。如果这是错误的，那么我们可以找到另一个经过这些点的电路，加上你刚刚删除的线段，就可以得到TSP问题的最短解决方案。 - Simone
看一下这些图片，除非我漏掉了什么，否则我很确定 tsp 方法行不通。如果你在看完图片后认为它仍然有效，我会尝试理解你的意思。 - stumpedcoder
好的，也许你是对的...但是添加一个虚拟节点肯定对于比特诺克旅行和TSP问题都有帮助。 - Simone
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接