|
|
%函數(shù)作用說明：起點(diǎn)與終點(diǎn)為同一個點(diǎn)的旅行商問題通用算法
function [mintsp1,path]=TSP1(distance,n,start)
%輸入
%distance 任意兩個地點(diǎn)的距離 n 地點(diǎn)數(shù)目 start 起點(diǎn)及終點(diǎn)
%輸出
%min_tsp 最短路程 path 最短路線
%%
%%首先構(gòu)造所有的可能路線矩陣luxian
p=n+1;
q=factorial(n-1);%階乘
luxian=zeros(p,q);%路線矩陣luxian
line=[1:n];
line(start)=[];% 刪去起點(diǎn)后的其余地點(diǎn)
%%%%%%%%找出所有的排列組合，即起點(diǎn)確定情況下的所有的路線
f=perms(line); %所有的排列組合
f1=f';% 除起點(diǎn)之外的排列組合
%%%%%%將起點(diǎn)，終點(diǎn)位置增加到排列組合的第1行和最后1行，得到構(gòu)造路線矩陣luxian
luxian=[start*ones(1,q);f1;start*ones(1,q)];
%%
%%%%%%%%計(jì)算每個組合下的路線
min_tsp=zeros(1,q);%最短距離初始化
for i=1:q %選擇路線
for j=1:n
i1=luxian(j,i);
j1=luxian(j+1,i);
min_tsp(1,i)=min_tsp(1,i)+distance(i1,j1);
end
end
%%
%%%確定最短路線、最短路程
mintsp1=min(min_tsp);%所有路線中的最短路程
path=[];
for i=1:q
if(min_tsp(i)==mintsp1)
path=[path;luxian(i,:)];%所有路線中的最短路線
end
end
|
|
