旅行商问题变体的近似算法，起点和终点可以固定在任何地方，但起点不能更改 + 允许多次访问每个顶点

Question

注意：由于旅行的结束点与起始点不同，并且只要我仍然访问所有点，每个点都可以被访问多次，因此这实际上不是TSP变体，但由于缺乏更好的问题定义，我将其放在这里。

假设我要去n个景点的徒步旅行。这些点都通过徒步小道连接。我有一张地图，显示了所有小径及其距离，给我一个有向图。

我的问题是如何近似地完成一次旅行，从A点开始访问所有n个景点，同时结束旅行的任何地方，而且我希望旅行路线尽可能短。

由于徒步旅行的性质，我认为这个问题可能不是对称问题（或者我能把非对称图转换成对称图吗？），因为从高海拔到低海拔显然比另一种方式容易。

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

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

我真正想要的是一些指针，告诉我如何设计一个近似算法，以找到通过所有n个点的近似最优旅行路线。

- Casper

---

你应该将这个问题发布到http://cs.stackexchange.com/上。 - Vitaly Olegovitch

由于您不介意多次访问同一节点，因此可以转换权重，使三角不等式成立。例如，如果在最优解中a->c的距离比a->b->c还远，那么您在计算中永远不会使用直接的a->c路径。因此，最好将a->c替换为a->b->c的值，以使您的度量满足三角不等式（这样您可以获得更好的结果）。 - ElKamina

这个问题似乎在这里没有得到太多关注。我投票将其移动到cs.stackexchange.com - 希望它能在那里得到一些答案。 :) - Li-aung Yip

Answer 1

为了将问题简化为非对称TSP，引入一个新节点u，并从u到A和除A以外的所有节点之间建立长度为L的弧，其中L非常大（足够大，以至于最优解不会回到u）。从旅游中删除u，以获得从A通过所有其他节点到达某个其他节点的路径。不幸的是，这种约简只能保持目标的加性，这使近似保证恶化了一个常数因子。

该约简的目标是非度量对称TSP，因此该约简对您没有用，因为已知的近似都需要度量实例。假设路径集合形成平面图（或接近平面图），由于Gharan and Saberi，可以得到一个常数因子的近似，但很难实现，并且在实践中可能无法给出合理的结果。Frieze, Galbiati, and Maffioli针对一般图提供了一个简单的对数因子逼近。

如果存在合理数量的路径，分支定界可能能够给出最优解。无论是G&S还是分支定界，都需要解决Held-Karp线性规划问题以解决ATSP，这本身可能对评估其他方法有用。对于许多实际中出现的对称TSP实例，它可以给出一个最优解成本的下限，该下限在真实值的10％内。

- oqi

---

感谢指出我的回答中的错误。现已修正为公制单位。 - Evgeny Kluev

首先感谢您抽出时间回答我的问题。我已经尝试过分支定界法，但是未能得出符合我的要求的结果。这只是因为我的无能（:)），而不是您的回答有误。然而，我成功地使用了其他文章中的方法，所以我自行标记那篇文章作为答案，还是非常感谢您的帮助！ - Casper

Answer 2

你可以将这个问题简化为一个有n+1个顶点的普通TSP问题。为此，选择节点'A'和所有感兴趣的点，并计算这些点之间的最短路径。您可以在原始图上使用全对最短路径算法。或者，如果n远小于原始图的大小，则可以使用单源最短路径算法来处理这n+1个顶点。另外，您可以将以'A'结尾的所有路径长度设置为某个常数，大于任何其他路径的长度，从而使旅行可以在任何地方结束（这可能仅适用于TSP算法寻找往返路径的情况）。

因此，您将得到一个完整的图形，该图形是度量的但仍然是不对称的。现在您只需要解决这个图形上的普通TSP问题。如果您想将这个不对称图形转换为对称图形，则可以在维基百科上了解如何操作。

- Evgeny Kluev

---

这似乎是一个可行的路线，保持简单的同时给出一个合理的结果。我选择了这个，并将您的帖子标记为答案。非常感谢你的时间。 - Casper

这似乎是在尝试找到一条（哈密顿）路径，所以在我看来，这个答案是正确的，因为解决一个问题将解决另一个问题。对我来说，你的问题似乎并不比TSP更容易。也许你也可以接受重复（TSP-R），但这并没有不同的复杂度。 - ntg