9

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

所以..

假设我要去一次有 n 个兴趣点的徒步旅行。这些点都由远足径相连。我有一张地图，显示所有路径及其距离，给我一个有向图。

我的问题是如何估计从 A 点开始并访问所有 n 个兴趣点的旅行，同时在除我开始的点之外的任何地方结束旅行，并且我希望旅行尽可能短。

由于徒步旅行的性质，我认为这很遗憾不是一个对称问题（或者我可以将我的不对称图转换为对称图吗？），因为从高海拔到低海拔显然比相反的方式更容易。

此外，我相信它必须是一种适用于非度量图的算法，其中不满足三角形不等式，因为从 a 到 b 到 c 可能比走一条从 a 到 c 的漫长而奇怪的道路更快直接地。我确实考虑过三角不等式是否仍然成立，因为对于我访问每个点的次数没有限制，只要我访问所有这些点，这意味着我总是会选择从 a 到 c 的两条不同路径中最短的一条，因此永远不会走上漫长而怪异的道路。

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

我真正想要的是一些关于如何提出近似算法的指示，该算法将在所有 n 点中找到接近最优的路径

4

2 回答 2

5

为了将您的问题简化为非对称 TSP，请引入一个新节点 u 并制作从 u 到 A 以及从除 A 之外的所有节点到 u 的长度为 L 的弧，其中 L 非常大（足够大以至于没有最优解重新访问 u）。从游览中删除 u 以获得从 A 通过所有其他节点到某个其他节点的路径。不幸的是，这种减少只是附加地保留了目标，这使得近似保证因常数因子而变得更糟。

Evgeny 指出的缩减目标是非度量对称 TSP，因此缩减对您没有用处，因为已知的近似值都需要度量实例。假设轨迹的集合形成一个平面图（或接近它），由于Gharan 和 Saberi存在一个常数因子近似，不幸的是，这可能很难实现，并且在实践中可能无法给出合理的结果。Frieze、Galbiati 和 Maffioli给出了一般图的简单对数因子近似。

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

于 2012-04-28T17:02:06.220 回答
4

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

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

于 2012-04-28T11:07:13.947 回答