可多次访问顶点的TSP [英] TSP Where Vertices Can be Visited Multiple Times

问题描述

我正在解决一个有加权有向图，并且我必须从原点开始，至少访问所有顶点一次并以尽可能短的路径返回原点的问题.从本质上讲，这将是TSP的经典示例，除了我请勿有一个约束，即每个顶点只能被访问一次.在我的情况下，沿路径可以多次访问除原点以外的任何顶点，如果这样做会使路径更短.因此，例如在包含顶点V1, V2, V3的图形中，这样的路径将是有效的，因为它是最短的路径:

I am looking to solve a problem where I have a weighted directed graph and I must start at the origin, visit all vertices at least once and return to the origin in the shortest path possible. Essentially this would be a classic example of TSP, except I DO NOT have the constraint that each vertex can only be visited once. In my case any vertex excluding the origin can be visited any number of times along the path, if this makes the path shorter. So for example in a graph containing the vertices V1, V2, V3 a path like this would be valid, given that it is the shortest path:

ORIGIN -> V1 -> V2 -> V1 -> V3 -> V1 -> ORIGIN

因此，我有点想采取什么方法来解决这个问题，因为通常用于指数时间解决TSP问题的经典动态编程算法方法是不合适的.

As a result, I am a bit stuck on what approach to take in order to solve this, as a classic dynamic programming algorithm approach which is usually used to solve TSP problems in exponential time is not suitable.

推荐答案

典型的方法是创建一个距离矩阵，该矩阵给出任意两个节点之间的最短路径距离.因此，d(i,j) =从i到j的最短路径(沿着网络的边缘).这可以使用Dijkstra的算法来完成.

The typical approach is to create a distance matrix that gives the shortest-path distance between any two nodes. So d(i,j) = shortest path (following the edges of the network) from i to j. This can be done using Dijkstra's algorithm.

现在只需求解距离为d(i,j)的经典TSP.您的TSP并不知道"遵循的实际路线可能涉及多次访问节点.同时，这将确保车辆在每个节点处停止.

Now just solve a classical TSP with distances d(i,j). Your TSP doesn't "know" that the actual route followed might involve visiting a node multiple times. At the same time, it will ensure that the vehicle stops at every node.

现在，关于效率:正如@Codor所指出的，TSP是NP难的，它的变体也是如此，因此您将不会找到可证明的最佳多项式时间算法.但是，对于TSP仍然有很多很好的算法(启发式算法和精确算法)，其中大多数应该适合您的问题. (通常，DP不是不是使用TSP的方法.)

Now, as for efficiency: As @Codor points out, TSP is NP-hard and so is your variant of it, so you are not going to find a provably optimal, polynomial-time algorithm. However, there are still many, many good algorithms (both heuristic and exact) for TSP, and most of them should be suitable for your problem. (In general, DP is not the way to go for TSP.)

这篇关于可多次访问顶点的TSP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！