TSP旅行商问题的常用解法Matlab代码（1）穷举法 |
您所在的位置：网站首页 › jdg线管国标 › TSP旅行商问题的常用解法Matlab代码（1）穷举法 |
TSP旅行商问题的常用解法Matlab代码（1）穷举法
|
一、TSP问题
旅行商要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。具体案例采用已有案例，四个城市之间双向路程不同，可相同。 将所有结果都列举出来，每一种路径都进行计算，然后将所有的结果进行比较，时间复杂度为 能够看到其将所有可能存在的路径都列举出来，共4*3*2*1=24种情况，然后依次对其进行计算即可得到TSP问题的最优解。由此看来生成遍历矩阵是关键。 1.1遍历矩阵的生成对于数量较少的可以采用下面的方式： clc; close all; clear all; n=4; P=[]; for i=1:n for j=1:n if j~=i for k=1:n if k~=j&&k~=i for l=1:n if l~=k&&l~=j&&l~=i a=[i,j,k,l]; P=[P;a]; end end end end end end endmatlab中提供了全排列函数perms，同样能够得到相应的结果，更加简洁。 clc; close all; clear all; n=1:4; perms(n) 1.2各个方案总距离的计算计算好遍历矩阵V之后，就能够求得各方案的总距离 C=[0,3,6,7;5,0,2,3;6,4,0,2;3,7,5,0]; V=[V,V(:,1)]; for i=1:size(V,1) for j=1:size(V,2)-1 d(i,j)=C(V(i,j),V(i,j+1)); end end 1.3完整代码 clc; close all; clear all; n=1:4; V=perms(n); %得到全排列遍历矩阵 C=[0,3,6,7;5,0,2,3;6,4,0,2;3,7,5,0]; %输入距离矩阵 V=[V,V(:,1)]; %将第一列放到矩阵最后一列形成环路 for i=1:size(V,1) %计算每一条环路的各段长度 for j=1:size(V,2)-1 d(i,j)=C(V(i,j),V(i,j+1)); end end D=sum(d,2); %将各段长度加和 [d,position]=min(D); %找到最短环路 d_min=d; %最短环路的长度 path_min=V(position,:); %最短环路的路径 N=length(path_min); p = num2str(path_min(1)); %将路径加上-> for i=2:N p=[p,'->',num2str(path_min(i))]; end disp('深度遍历优先算法DFS得到的最优路径为:') disp(p) fprintf('深度遍历优先算法DFS得到的最优路径的长度为:%d\n',d_min)输出为： |
【本文地址】
今日新闻 |
推荐新闻 |