%函数作用说明：起点与终点为同一个点的旅行商问题通用算法
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空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
