%函數作用說明：起點與終點為同一個點的旅行商問題通用算法
function [mintsp1,path]=TSP1(distance,n,start)
%輸入
%distance 任意兩個地點的距離 n 地點數目 start 起點及終點
%輸出
%min_tsp 最短路程 path 最短路線
%%
%%首先構造所有的可能路線矩陣luxian
p=n+1;
q=factorial(n-1);%階乘
luxian=zeros(p,q);%路線矩陣luxian
line=[1:n];
line(start)=[];% 刪去起點后的其余地點
%%%%%%%%找出所有的排列組合，即起點確定情況下的所有的路線
f=perms(line); %所有的排列組合
f1=f';% 除起點之外的排列組合
%%%%%%將起點，終點位置增加到排列組合的第1行和最后1行，得到構造路線矩陣luxian
luxian=[start*ones(1,q);f1;start*ones(1,q)];
%%
%%%%%%%%計算每個組合下的路線
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
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
