并非所有城市都相连且可能多次访问时的旅行商问题
Traveling salesman problem when not all cities are connected and with the possibility of multiple visits
我有一个问题要解决，我认为是旅行商类型的。我知道最常讨论的旅行推销员问题将每个城市的访问次数限制为一次访问，并且该城市必须可以从任何位置访问。然而，在现实世界中，这并不总是可能的。例如，让我们检查下图。
通过通常的旅行推销员的问题（使用 R 的 TSP 库）解决这个问题，例如，我有 440 公里的旅行成本（A -> B -> C -> D -> A）。然而，在第二张图片中（试图模拟现实世界）我找到了一条更小的路径，成本为 400 公里（A -> B -> C -> B -> D -> B -> A）。
我想做的是尽可能以最短的距离访问所有城市，而不考虑访问次数。一定有什么东西准备好了，但我找不到。有人有什么建议吗？
提前致谢。
您描述的 TSP 可还原为“真实”TSP。
你有一个图，问题是不是每个顶点都连接到每个其他顶点，三角不等式不成立。即即使两个顶点相连，它们的连接也不一定是它们之间的最短路径。注意这里 if 你的图是完整的，并且 if 三角不等式成立，那么我们可以很容易地证明最短路径永远不需要访问相同的城市两次。
那么，如何将你的问题转化为“合适的”问题呢？我们只需要计算每两个顶点之间的实际最短路径距离，并将其设置为两个顶点之间的距离。然后我们可以使用任何 TSP 求解器，如果我们还记得最短路径，我们就可以将其转换回原始问题的解决方案。
要找到最短路径，我建议 Floyd-Warshall。根据确切的图表，这可能不是完全最优的，但这并不重要，因为解决 TSP 无论如何都会复杂得多。
图表示例：
首先，我们找到图中每对顶点之间的最短路径：
A-B: 100; A,B
A-C: 150; A,B,C
A-D: 150; A,B,D
B-C: 50; B,C
B-D: 50; B,D
C-D: 100; C,B,D
现在我们将这些距离放入一个新图形中，将其输入到 TSP 求解器中，我们得到（例如）以下结果：
A -> B -> C -> D -> A
现在，我们知道了原始图中任意两个顶点之间的最短路径，因此我们可以将这些路径替换为 TSP 结果中的路径：
A -> B -> C -> B -> D -> B -> A
然后这是访问所有城市的实际最短路径，如果有多个，则为最短路径之一。
我有一个问题要解决，我认为是旅行商类型的。我知道最常讨论的旅行推销员问题将每个城市的访问次数限制为一次访问，并且该城市必须可以从任何位置访问。然而，在现实世界中，这并不总是可能的。例如，让我们检查下图。
我想做的是尽可能以最短的距离访问所有城市，而不考虑访问次数。一定有什么东西准备好了，但我找不到。有人有什么建议吗？
提前致谢。
您描述的 TSP 可还原为“真实”TSP。
你有一个图，问题是不是每个顶点都连接到每个其他顶点，三角不等式不成立。即即使两个顶点相连，它们的连接也不一定是它们之间的最短路径。注意这里 if 你的图是完整的，并且 if 三角不等式成立，那么我们可以很容易地证明最短路径永远不需要访问相同的城市两次。
那么，如何将你的问题转化为“合适的”问题呢？我们只需要计算每两个顶点之间的实际最短路径距离，并将其设置为两个顶点之间的距离。然后我们可以使用任何 TSP 求解器，如果我们还记得最短路径，我们就可以将其转换回原始问题的解决方案。
要找到最短路径，我建议 Floyd-Warshall。根据确切的图表，这可能不是完全最优的，但这并不重要，因为解决 TSP 无论如何都会复杂得多。
图表示例：
首先，我们找到图中每对顶点之间的最短路径：
A-B: 100; A,B
A-C: 150; A,B,C
A-D: 150; A,B,D
B-C: 50; B,C
B-D: 50; B,D
C-D: 100; C,B,D
现在我们将这些距离放入一个新图形中，将其输入到 TSP 求解器中，我们得到（例如）以下结果：
A -> B -> C -> D -> A
现在，我们知道了原始图中任意两个顶点之间的最短路径，因此我们可以将这些路径替换为 TSP 结果中的路径：
A -> B -> C -> B -> D -> B -> A
然后这是访问所有城市的实际最短路径，如果有多个，则为最短路径之一。