最小距离哈密尔顿路径的Javascript [英] Minimal Distance Hamiltonian Path Javascript

问题描述

我知道这是一个相当常见的问题（TSP一般），但我已经难住了它一段时间了。我希望找到给定一组x的最小距离哈密尔顿路径，y坐标。开始和结束点完全是任意的，但决不能循环，所以标准TSP超出（尽管据说加入了虚点0距离到所有其他节点，然后删除它后来的作品，我不知道我会怎么做）。

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).

有大量的链接，数学试卷之类的讨论算法来解决类似的问题，但我宁愿用code比复杂的公式工作，我真的不想另起炉灶。

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.

当然，还有一个重要的语言的Java，C＃，C ++，红宝石，JavaScript的，PHP等，可以解决我的问题的〜20节点版本的一个相当简单的实现。

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.

编辑：我也在寻找尽可能准确，这显然不能完全准确，因为20！很多排列，但小于或等于什么人可以做在一两分钟更好的将是完美的。

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：同时澄清，我正与标准的二维坐标上的加权图。距离A-> B == B-> A

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最长的区间（红线）

TSP Minus Longest Segment (red line)

所需的输出

推荐答案

您可以解决双调欧几里得旅行推销员问题。是TSP的解，通过动态规划的简化版本为O（n ^ 2）： http://en.wikipedia.org/wiki/Bitonic_tour

You 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

这篇关于最小距离哈密尔顿路径的Javascript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！