相关疑难解决方法(0)

我知道这是一个相当频繁的问题(一般来说是tsp),但我已经被它困住了一段时间了.我希望在给定一组x,y坐标的情况下找到最小距离哈密顿路径.起点和终点完全是任意的,但它不能循环,所以标准的tsp出来了(虽然假设在0距离处向所有其他节点添加一个虚拟点,然后在以后删除它有效,我不知道我是怎么做的).

有很多链接到数学论文等讨论算法来解决类似的问题,但我宁愿使用代码而不是复杂的方程式,我真的宁愿不重新发明轮子.

当然,在主要语言java,c#,c ++,ruby,javascript,php等中有一个相当简单的实现,它可以解决我的问题的~20节点版本.

编辑:我也在寻找尽可能准确,显然它不能完全准确为20!有很多排列,但是等于或优于人类在几分钟内可以做的事情将是完美的.

编辑2:另外澄清一下,我正在使用未加权图上的标准二维坐标.距离A-> B == B-> A.

编辑3: 为了消除混淆,这里有一个视觉示例,只有几个点来说明tsp如何不是最理想的(这种情况是一个简单的修复,但有更多的节点,它可能更极端).

TSP减去最长段(红线)

期望的输出

给定具有n个顶点的加权无向图,我面临着找到连接线中每个顶点的最小权重路径的问题.起初,我认为这是找到最小生成树的问题,但事实并非如此.在生成树的情况下,在顶点处可能存在分支,或者该程度可以大于2.我需要找到的是一个线性路径,即除了端点之外的所有顶点都有两个度数.起点和终点顶点可以是n个顶点中的任何一个.

我是一个贪婪的方法,即

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors
    mark this neighbor as visited
    add the cost to sum
repeat the procedure above until all the points have been visited.

我必须以所有顶点为起点进行此操作.我不确定这个算法是否正确,而且它的复杂性也很高.对这个问题应该采取什么更好的方法？