Matlab中可能的“旅行推销员”功能？

我正在寻找解决使用矩阵旅行推销员类型问题，以找到过渡之间的最短时间。矩阵看起来像这样：Matlab中可能的“旅行推销员”功能？

A = [inf 4 3 5; 
     1 inf 3 5; 
     4 5 inf 3; 
     6 7 1 inf]

y轴代表“从”节点，而x轴代表“到”节点。我试图找到从节点1到节点4的最佳时间。我被告知有一个称为“TravellingSalesman”的Matlab函数。这是真的，如果不是，我将如何去解决这个矩阵？

谢谢！

来源

2014-10-10 Jenn

我发现了一些东西[这里]（http://people.sc.fsu.edu/~jburkardt/m_src/tsp_brute/tsp_brute.html），还有一些关于[文件交换]的东西（http：// www .mathworks.com/matlabcentral/fileexchange /索引？UTF8 =％E2％9C％93＆术语=行进+推销员）。 – MeMyselfAndI 2014-10-10 17:11:33

这里的蛮力算法的轮廓解决TSP的路径从节点1到节点n：

C = inf 
P = zeros(1,n-2) 
for each permutation P of the nodes [2..n-1] 
    // paths always start from node 1 and end on node n 
    C = A(1,P(1)) + A(P(1),P(2)) + A(P(2),P(3)) + ... + 
     A(P(n-3),P(n-2)) + A(P(n-2),n) 
    if C < minCost 
     minCost = C 
     minPath = P 
    elseif C == minCost   // you only need this part if you want 
     minPath = [minPath; P] // ALL paths with the shortest distance 
    end 
end

注意的是，在和第一个和最后一个因素是不同的，因为你事先什么知道第一个和最后一个节点是，所以你不必将它们包含在排列中。所以在给出的例子中，n=4实际上只有2!=2可能的路径。

排列列表可使用perms(2:n-1)预先计算，但可能涉及存储大型矩阵（n! x n）。或者，您可以在生成每个排列时计算成本。 Mathworks文件交换中有几个文件，名称如nextPerm应该适合您。无论哪种方式，随着n的增长，你将会产生大量的排列，你的计算将花费很长时间。

来源

2014-10-10 20:08:02 beaker

Matlab中可能的“旅行推销员”功能？

回答

相关问题