algorithm - 访问有向完全加权图中所有顶点的最短路径

Question

给定:完整的有向加权图。所有的权重都是正的。是否有任何简单的方法(启发式？)找到访问所有顶点的最短(就权重而言)路径？顶点数约为25。这个问题好像和Asymmetric Travellering Salesman很接近，但是我不要求这个路径是循环。

Answer 1

我会推荐 K 最短路径方法:

http://www.mathworks.com/matlabcentral/fileexchange/32513-k-shortest-path-yen-s-algorithm

我认为这是您最好的选择...这是一个示例:假设您有 8 个节点，并且需要以尽可能短的路径从节点 1 到达节点 8。假设所有节点都相互连接(即节点 1 连接到节点 2:8，依此类推)。您将必须根据您的问题生成“成本矩阵”。

costMatrix = rand(8);
[shortestPath, cost] = dijkstra(costMatrix,1,8);

% Alternatively, return the 10 shortest paths from point 1 to 8:
[shortestPaths, costs] = kShortestPath(costMatrix,1,8,10);

成本矩阵中的位置 (i,j) 是从节点 i 到节点 j 的旅行成本。如果 costMatrix(i,j) = inf; 节点 i 和节点 j 之间没有连接。

在研究了隐马尔可夫模型之后，我发现了一些潜在的问题——排放矩阵很难定义，而且您可能会遇到在一条“路线”中两次或多次进入“状态”的问题。 “使用 k-最短路径，不会发生此错误。