TSP变量的近似算法,固定开始和结束任何地方但起点+允许每个顶点多次访问

Question

注意:由于旅行不是在它开始的同一个地方结束的事实,而且只要我仍然访问所有这些点,每个点都可以被访问多次这一事实,这不是真正的TSP变体,而是我之所以说是因为缺乏对问题的更好定义.

所以..

假设我正在徒步旅行,有n个兴趣点.这些景点都通过远足径相连.我有一张地图显示了所有距离的路径,给我一个有向图.

我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游,同时结束旅行的任何地方,但我开始的点,我希望旅游尽可能短.

由于远足的性质,我认为这可能不是一个对称问题(或者我可以将我的不对称图转换为对称图？),因为从高海拔到低海拔显然比其他方式更容易.

另外我认为它必须是一种适用于非度量图的算法,其中不满足三角不等式,因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直.我确实考虑过三角不等式是否仍然存在,因为对于我访问每个点的次数没有限制,只要我访问所有这些,这意味着我总是选择从a到c的两条不同路径中最短的路径,从而永远不会抓住漫长而奇怪的道路.

我相信我的问题比TSP更容易,因此这些算法不适合这个问题.我考虑过使用最小生成树,但我很难说服自己可以将它们应用于非度量非对称有向图.

我真正想要的是关于如何能够提出近似算法的一些指示,该算法将通过所有n个点找到近乎最佳的旅行

Answer 1

为了将问题减少到非对称TSP,引入一个新节点u并制作长度为L的弧从u到A以及从A到u的所有节点,其中L非常大(足够大,没有最佳解决方案重新访问u).从巡视中删除u以获取从A到其他节点的路径.不幸的是,这种减少仅仅是附加地保留了目标,这使得近似保证通过恒定因子变得更糟.

Evgeny指出的减少目标是非度量对称TSP,因此减少对您没有用,因为已知的近似值都需要度量实例.假设路径的集合形成平面图(或接近它),由于Gharan和Saberi,存在恒定因子近似,遗憾的是,这可能很难实现,并且在实践中可能无法给出合理的结果.Frieze,Galbiati和Maffioli给出了一般图的简单对数因子近似.

如果有合理数量的路径,分支和绑定可能会为您提供最佳解决方案.G&S和分支机构都需要为ATSP解决Held-Karp线性程序,这可能对评估其他方法本身很有用.对于在实践中出现的许多对称TSP实例,它给出了在真实值的10%内的最优解决方案的成本的下限.

Answer 2

您可以将此问题简化为具有 n+1 个顶点的普通 TSP 问题。为此，请获取节点“A”和所有感兴趣的点，并计算每对这些点之间的最短路径。您可以在原始图上使用全对最短路径算法。或者，如果 n 明显小于原始图大小，则对这 n+1 个顶点使用单源最短路径算法。此外，您还可以将所有以“A”结尾的路径的长度设置为某个常数，大于任何其他路径，这允许在任何地方结束行程（这可能仅适用于寻找往返路径的 TSP 算法） 。

结果，您得到一个完整的图表，它是公制的，但仍然不对称。您现在所需要做的就是解决该图上的正常 TSP 问题。如果您想将此非对称图转换为对称图，维基百科解释了如何操作。