注意：由于旅行不是在它开始的同一个地方结束的事实，而且只要我仍然访问所有这些点，每个点都可以被访问多次这一事实，这不是真正的TSP变体，而是我之所以说是因为缺乏对问题的更好定义 .
所以..
假设我正在徒步旅行，有n个兴趣点 . 这些景点都通过远足径相连 . 我有一张 Map 显示了所有距离的路径，给我一个有向图 .
我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游，同时结束旅行的任何地方，但我开始的点，我希望旅游尽可能短 .
由于远足的性质，我认为这可能不是一个对称问题（或者我可以将我的不对称图转换为对称图？），因为从高海拔到低海拔显然比其他方式更容易 .
另外我认为它必须是一种适用于非度量图的算法，其中不满足三角不等式，因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直 . 我确实考虑过三角不等式是否仍然存在，因为对于我访问每个点的次数没有限制，只要我访问所有这些，这意味着我总是选择从a到c的两条不同路径中最短的路径，从而永远不会 grab 漫长而奇怪的道路 .
我相信我的问题比TSP更容易，因此这些算法不适合这个问题 . 我考虑过使用最小生成树，但我很难说服自己可以将它们应用于非度量非对称有向图 .
我真正想要的是关于如何能够提出近似算法的一些指示，该算法将通过所有n个点找到近乎最佳的旅行
2 回答
为了将问题减少到非对称TSP，引入一个新节点u并制作长度为L的弧从u到A以及从A到u的所有节点，其中L非常大（足够大，没有最佳解决方案重新访问u） . 从巡视中删除u以获取从A到其他节点的路径 . 不幸的是，这种减少仅仅是附加地保留了目标，这使得近似保证通过恒定因子变得更糟 .
Evgeny指出的减少目标是非度量对称TSP，因此减少对您没有用，因为已知的近似值都需要度量实例 . 假设路径的集合形成平面图（或接近它），由于Gharan and Saberi存在恒定因子近似，遗憾的是，这可能很难实现，并且在实践中可能无法给出合理的结果 . Frieze, Galbiati, and Maffioli给出了一般图的简单对数因子近似 .
如果有合理数量的路径，分支和绑定可能会为您提供最佳解决方案 . G＆S和分支机构都需要为ATSP解决Held-Karp线性程序，这可能对评估其他方法本身很有用 . 对于在实践中出现的许多对称TSP实例，它给出了在真实值的10％内的最优解决方案的成本的下限 .
您可以将此问题简化为具有n 1个顶点的正常TSP问题 . 为此，请获取节点“A”和所有感兴趣的点，并计算每对点之间的最短路径 . 您可以在原始图上使用全对最短路径算法 . 或者，如果n明显小于原始图形大小，则对这些n 1个顶点使用单源最短路径算法 . 您还可以将所有路径的长度（以'A'结尾）设置为某个常量，大于任何其他路径，这样可以在任何地方结束行程（这可能只需要TSP算法，找到往返路径） .
因此，您将获得一个完整的图表，该图表是指标，但仍然是非对称的 . 您现在需要的只是在此图上解决正常的TSP问题 . 如果要将此非对称图转换为对称图，Wikipedia解释了如何执行此操作 .