[算法]巡回售货员问题

blackuhlan

今天在看时间复杂度的时候看见有个据说是著名的巡回售货员问题，据说目前的算法都是指数级的，我随便想了想，搞了个算法，当然纰漏可能是大大的存在。各位牛哥、牛姐、牛弟、牛妹给拍拍砖，俺们讨论讨论。
1.将所有路径倒排序。
2.尝试删除长度最大的路径，如果有同样长度路径（按顺序尝试）。
2.1 如果要删除的路径的两个端点中有一个的路径数小于2，返回不允许删除。
2.2 如果删除该路径后，图中还存在哈密尔顿路径（即回路），返回允许删除。否则返回不允许删除。
简单吧。拍砖欢迎，证明的没想到。

blackuhlan

再给介绍点背景资料吧：
巡回售货员问题也称为货郎担问题。有一个售货员，从他所在城市出发去访问n-1个城市，要求经过每个城市恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济（即线路最短）？就是求最短的哈密尔顿路径。
如果将所有城市以及所有路径用图表示出来就是赋值完全图。每个城市作为节点，每两个城市之间的路线长度作为赋值路径（任意两个城市之间都有路径）。

blackuhlan

怎么没人给提提意见，牛都不知道跑哪去吃草去了吗？

blackuhlan

唉，牛儿还在山坡吃草，晚上再来看看吧

haohao06

贪心法么?
我举个反例不知道对不对
ab=6,bc=1,cd=1,da=1,ac=5,bd=5.
这样最短是abcda=9,
如果用你的算法岂不是第一次就把ab删除了.

blackuhlan

原帖由 haohao06 于 2009-6-3 17:00 发表
贪心法么?
我举个反例不知道对不对
ab=6,bc=1,cd=1,da=1,ac=5,bd=5.
这样最短是abcda=9,
如果用你的算法岂不是第一次就把ab删除了.

谢谢这位兄的，我再想想，想好了再卷土重来