最小距离哈密顿路径Javascript
我知道这是一个相当常见的问题（一般而言），但我已经被它难住了一段时间了。我正在寻找给定一组 x,y 坐标的最小距离哈密顿路径。起点和终点完全是任意的，但它不能循环，所以标准 tsp 已经出来了（虽然据说在与所有其他节点的距离为 0 处添加一个虚拟点，然后稍后将其删除，但我不知道该怎么做）。
有很多数学论文和类似讨论解决类似问题的算法的链接，但我更愿意使用代码而不是复杂的方程，而且我真的不想重新发明轮子。
当然，在主要语言 java、c#、c++、ruby、javascript、php 等中有一个相当简单的实现，可以解决我的问题的约 20 个节点版本。
编辑：我也在寻找尽可能精确的值，显然它不能完全精确到20！是很多排列，但等于或优于人类在几分钟内可以完成的事情将是完美的。
编辑2：还要澄清一下，我正在未加权的图表上使用标准二维坐标。距离 A->B == B->A
Edit3: 为了消除混淆，这里有一个直观的示例，其中只有几个点来展示 tsp 如何不是最优的（这种情况很容易修复但如果节点更多，情况可能会更加极端）。
TSP 减去最长段（红线）
所需输出
I know this is a fairly frequent question (tsp in general), but I've been stumped by it for awhile now. I'm looking to find the minimal distance hamiltonian path given a set of x,y coordinates. The start and end point are completely arbitrary but it must NOT cycle, so standard tsp is out (although supposedly adding a dummy point at 0 distance to all other nodes and then removing it later works, i have no idea how I'd do that).
There are plenty of links to math papers and the like discussing algorithms to solve similar problems, but I'd much rather work with code than complex equations and i'd really rather not reinvent the wheel.
Surely there is a fairly straightforward implementation in a major language java,c#,c++,ruby,javascript,php,etc that can solve a ~20 node version of my problem.
Edit: I'm also looking for as accurate as possible, obviously it can't be completely accurate as 20! is a lot of permutations, but equal to or better than what a human could do in a couple minutes would be perfect.
Edit2: Also to clarify, I'm working with standard 2d coordinates on an unweighted graph. The distance A->B == B->A
Edit3: To eliminate confusion, here's a visual example with just a few points to show how tsp can be suboptimal (this case is an easy fix but with more nodes it can be more extreme).
TSP Minus Longest Segment (red line)
Desired Output
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以解决双调欧几里得旅行商问题。是可通过
O(n^2)动态编程解决的 tsp 简化版本：http://en.wikipedia.org/wiki/Bitonic_tourYou can solve the bitonic euclidean traveling-salesman problem. Is a simplified version of the tsp solvable through dynamic programming in
O(n^2): http://en.wikipedia.org/wiki/Bitonic_tour