function [BestShortcut,theMinDistance]=SimulateAnneal4(dislist,Clist,cnod)
%TSP问题的模拟退火算法malab程序
clc;
close all;
% clear all;
f=inf;
% dislist=[f 2 3 2 f f f f f;
% 2 f 2 3 3 f f f f;
% 3 2 f 2 1 f f 1 f;
% 2 3 2 f f 3 f 4 f;
% f 3 1 f f f 3 2 f;
% f f f 3 f f 2 2 4;
% f f f f 3 2 f 2 3;
% f f 1 4 2 2 2 f 3;
% f f f f f 4 3 3 f];
% Clist=[0 1;0 0;1 0;1 1;1 -1;2 1;2 -1;1.5 0;3 0];
NodeNum=size(Clist,1);%TSP问题的规模,即城市数目
n=size(Clist,1);
d=dislist;
q=zeros(n,n);
for j=1:n
q(:,j)=j;
end
for k=1:n
for i=1:n
for j=1:n
if d(i,j)>d(i,k)+d(k,j)
d(i,j)=d(i,k)+d(k,j);
q(i,j)=q(i,k);
end
end
end
end
for j=1:n
d(j,j)=0;
end
x=[2:NodeNum];
need=3-mod((NodeNum-1),3);
x=[x,zeros(1,need)];
circlenum=floor((NodeNum-1)/3);
x=x(randperm(length(x)));
for i=1:circlenum
x=[x(1:4*i-1),1,x(4*i:length(x))];
end
x=[1,x];
x(x==0)=[];
NodeNum=length(x);
%d=rand(100,100);
[~,n]=size(d);
t0=100; %t0初始温度=100K
t=t0;
tf=1; %tf最终温度=100K
%x=randperm(n); %领域初始解表示第i个人做i个事
xbest=x;
xrealbest=x; %领域最优解
c=1;
fmin=fun(d,x);
frealmin=fun(d,x);%将初始可行解下的目标函数设为当前最优目标值
num=1;
figure(1);
stop = uicontrol('style','toggle','string'...
,'stop','background','white');
tic;
cc=0;
while t>tf && num<2000
for k=1:500; %内循环停止准则5000次
fx=fun(d,x); %计算新解的函数值。
fb=fx-frealmin;
if fb<=0 && cc<=3
xbest=x;
fmin=fx;
xrealbest=x;
frealmin=fx;%无条件跳转，取最优值与最优解。
elseif fb>0
p=exp(-fb/t);
if p>rand
xbest=x;
fmin=fx; %有条件跳转，取最优值与最优解。
elseif p<=rand
x=x; %不处理
end
end
x=[2:n];
need=3-mod((n-1),3);
x=[x,zeros(1,need)];
circlenum=floor((n-1)/3);
x=x(randperm(length(x)));
for i=1:circlenum
x=[x(1:4*i-1),1,x(4*i:length(x))];
end
x=[1,x];
x(x==0)=[];
%以下是添加约束：到c点路程不能超过3，cc为s到c的路程
cc=0;
snod=1;
add1=find(x==snod);
add2=find(x==cnod);
cha=add2-add1;
cha=cha(cha>0);
i=1;
while i<=min(cha)
if i==n
cc=cc+d(x(i),x(1));
i=1;
else
cc=cc+d(x(i),x(i+1));
i=i+1;
end
end
end
t=0.997*t; %模拟退火操作
BestL=frealmin;
ArrBestL(num)=BestL;
NodeNum=n;
BSF=xrealbest;
ArrBestL(num)=BestL;
for i=1:NodeNum-1
plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'bo-');
hold on;
end
plot([Clist(BSF(NodeNum),1),Clist(BSF(1),1)],[Clist(BSF(NodeNum),2),Clist(BSF(1),2)],'ro-');
title(['迭代次数:',int2str(num),' 优化最短距离:',num2str(BestL)]);
hold off;
pause(0.005);
if get(stop,'value')==1
break;
end
%存储中间结果为图片
% if (p==1||p==5||p==10||p==20||p==60||p==150||p==400||p==800||p==1500||p==2000)
% filename=num2str(p);
% fileformat='jpg';
% saveas(gcf,filename,fileformat);
% end
num=num+1; %迭代次数加1
end
len=length(BSF);
add=find(BSF==cnod);
bs=BSF(add:len);
bs=[bs,BSF(1:add-1)];
BSF=bs;
add=find(BSF==snod, 1, 'last' );
bs=BSF(add:len);
bs=[bs,BSF(1:add-1)];
BSF=bs;
toc %用来保存完成时间
BestShortcut=BSF; %最佳路线
theMinDistance=BestL; %最佳路线长度
set(stop,'style','pushbutton','string','close', 'callback','close(gcf)');
figure(2);
plot(ArrBestL,'b');
xlabel('迭代次数');
ylabel('目标函数值');
title('适应度进化曲线');
grid;
hold on;
% function fmin=fun(d,x)
% fmin=0;
% n=length(x);
% for i=1:n
% fmin=fmin+d(i,x(i)); %计算第i个人做x（i）任务时总时间。
% end
function fmin=fun(d,x)
fmin=0;
n=length(x);
for i=1:n-1
fmin=fmin+d(x(i),x(i+1)); %计算第i个人做x（i）任务时总时间。
end
fmin=fmin+d(x(n),x(1));
