问题描述
例如，我们有一个图由顶点（市）和边缘（道路）和每条边（路）有一个特定的成本，找到最小的成本来参观所有城市的 ATLEAST ONCE 。成本是边缘的成本横过边缘的总和。部分ATLEAST ONCE抓到我。在TSP，我们可以访问一个节点只有一次，根据维基。考虑曲线图中，
A-B 11
A-C 5
B-C 2
B-E 4
C-E 3
C-D 20
D-E 100
在TSP，循环路径将是ABEDCA具有成本140（或）ACDEBA具有成本140.如果从我的问题描述，我们可以访问每一个顶点ATLEAST一次，以便我们能有一个循环路径ACDCEBA具有成本63为＆lt;＆LT ;一茶匙。这是我有一个问题。任何具体的算法在这里？我是pretty的TSP肯定不会很好地工作在这里。
指针或伪code将是非常有益的。
For example, we have a graph consisting of vertices (cities) and edges (roads) and each edge(road) has a particular cost, find the minimal cost to visit all cities ATLEAST ONCE. Cost is the sum of the edge costs of the edges traversed.The part "ATLEAST ONCE" caught me. In a TSP we can visit a node only once according to Wiki. Consider the graph,
A-B 11
A-C 5
B-C 2
B-E 4
C-E 3
C-D 20
D-E 100
In a TSP, The cyclic path would be A-B-E-D-C-A cost- 140 (or) A-C-D-E-B-A cost- 140. Where as from my problem description we can visit each vertex ATLEAST ONCE so we can have a cyclic path A-C-D-C-E-B-A cost- 63 which is << a TSP. This is where I had a problem. Any specific algorithm here? I'm pretty sure TSP wont work well here.
Pointers or pseudo code will be very helpful.
推荐答案
对于每一对节点，您可以应用的并计算出最短距离。这将是新的成本矩阵的每对
For each pair of nodes, you can apply the shortest path algorithm and calculate the shortest distance. This will be the new cost matrix for each pair.
现在则减少到旅行商问题。
那么你可以申请TSP解决方法。
Then you can apply TSP solving technique.
这篇关于最低成本的循环路径图 - TSP的一个变种的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！