algorithm - Traveling salesman problem when not all cities are connected and with the possibility of multiple visits
问题描述
I have a problem to solve that I think is the Traveling Salesman type. I know that the traveling salesman problem most commonly discussed restricts the number of visits in each city to just one visit and that the city must all be accessible from any point. However, in the real world, this is not always possible. For example, let's examine the figure below. Solving this problem via the problem of the usual traveling salesman (using the TSP library of R) I have a travel cost of 440 km (A -> B -> C -> D -> A), for example. However, in the second image (trying to simulate the real world) I find a smaller path, with a cost of 400 km (A -> B -> C -> B -> D -> B -> A).
What I would like to do is visit all cities with the shortest possible distance, regardless of the number of visits. There must be something ready about it, but I couldn't find it. Does anyone have any suggestions?
Thanks in advance.
解决方案
TSP as you describe it is reducible to "real" TSP.
You have a graph, with the problems being that not every vertex is connected to every other vertex, and the triangle inequality does not hold. That is, even if two vertices are connected, their connection is not necessarily the shortest path between them. Note here that if your graph was complete, and if the triangle inequality held, then we can easily prove that the shortest path never requires visiting the same city twice.
So, how to transform your problem into the "proper" problem? We simply need to calculate the actual shortest path distance between every two vertices, and set that to be the distance between the two vertices. We can then use any TSP solver, and if we also remembered the shortest paths, we can then transform it back into a solution to the original problem.
To find the shortest paths I'd recommend Floyd-Warshall. This may not be entirely optimal depending on the exact graph, but that doesn't really matter as solving TSP will be significantly more complex anyway.
Example for your graph:
First, we find the shortest paths between every pair of vertices in the graph:
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
Now we put these distances into a new graph, feed that into a TSP solver, and we get (for example) the following result:
A -> B -> C -> D -> A
Now, we know the shortest paths between any two vertices in our original graph, so we can just substitute these paths for the paths in the TSP result:
A -> B -> C -> B -> D -> B -> A
and this is then the actual shortest path that visits all cities, or one of the shortest paths if there are multiple.
推荐阅读
- angular - 动态插入组件时 ControlValueAccessor 不起作用
- c# - 如何在 C# 中打开新窗口而不丢失 xml 布局
- mysql - 如何查询表内相同数据但输出行位置不同
- php - 使用参考问题将 Python 代码改编为 PHP
- c# - 如何以编程方式添加/修改/删除可用的显示设置(宽度、高度、刷新率)?
- spotfire - 无参数按需数据
- javascript - 运行“npm run prod”会导致“未定义要求”
- ansible - 在具有不同值的父角色中调用 Ansible 任务
- c - 在标头中使用 ifdef linux 等有意义吗?
- python - 在python中处理unicode字符串