节约里程法matlab.doc

clear
clc
A=[0 15 5 10 5 20;0 30 30 20 5 10;0 85 162 26 140 110];
rong=300;
m=6;
c=zeros(6,6);
for i=1:m
for j=1:m
c(i,j)=sqrt((A(1,i)-A(1,j))^2+(A(2,i)-A(2,j))^2);
end
end

p=zeros(6,6);
for i=2:(m-1)
for j=(i+1):m
p(i,j)=c(1,i)+c(1,j)-c(i,j);
end
end

s=p(:);
[hs,wz]=sort(s,1,'descend');

for i=1:(m^2)
[x,y]=ind2sub(size(p),wz(i));
if A(3,x)+A(3,y)<=rong
solut=[x,y];
n(1)=2;
zhuang(1)=A(3,x)+A(3,y);
ii=i;
break
else
continue
end
end

for rr=(ii+1):(m^2)
[x,y]=ind2sub(size(p),wz(rr))
if hs(rr)==0
break
end

[xa,ya]=find(x==solut)
[xb,yb]=find(y==solut)
[sa,sb]=size(solut)
if isempty(xa)==0 && isempty(xb)==0
if xa==xb
continue
end

if n(xa)~=2
if 1<ya<n(xa)
continue
end
end

if n(xb)~=2
if 1<yb<n(xb)
continue
end
end

zh1=zhuang(xa)
zh2=zhuang(xb)
if zhuang(xa)+zhuang(xb)<=rong
if ya==1&&yb==1
newm=[solut(xb,n(xb):-1:1) solut(xa,1:n(xa))]
elseif ya==1&&yb==n(xb)
newm=[solut(xb,1:n(xb)) solut(xa,1:n(xa))]
elseif ya==n(xa)&&yb==1
newm=[solut(xa,1:n(xa)) solut(xb,1:n(xb))]
elseif ya==n(xa)&&yb==n(xb)
newm=[solut(xa,1:n(xa)) solut(xb,n(xb):-1:1)]
end

solut(xa,:)=[]
solut(xb,:)=[]

n(xa)=[]
n(xb)=[]
zhuang(xa)=[]
zhuang(xb)=[]

[qa,qb]=size(solut)

solut((qa+1),1:length(newm))=newm
n(qa+1)=length(newm)

zhuang(qa+1)=zh1+zh2

else
continue
end

elseif isempty(xa)==0

if n(xa)~=2
if 1<ya<n(xa)
continue
end
end

zh3=zhuang(xa)+A(3,y)
if zhuang(xa)+A(3,y)<=rong
if ya==1
newm=[y solut(xa,1:n(xa))]
elseif ya==n(xa)
newm=[solut(xa,1:n(xa)) y]
end
solut(xa,:)=[]
n(xa)=[]
zhuang(xa)=[]
[qa,qb]=size(solut)

solut((qa+1),1:length(newm))=newm
n(qa+1)=length(newm)
zhuang(qa+1)=zh3
end

elseif isempty(xb)==0

if n(xb)~=2
if 1<yb<n(xb)
continue
end
end

zh4=zhuang(xb)+A(3,x)
if zhuang(xb)+A(3,x)<=rong
if yb==1
newm=[x solut(xb,1:n(xb))]
elseif yb==n(xb)
newm=[solut(xb,1:n(xb)) x]
end
solut(xb,:)=[]
n(xb)=[]
zhuang(xb)=[]
[qa,qb]=size(solut)
solut((qa+1),1:length(newm))=newm
n(qa+1)=length(newm)
zhuang(qa+1)=zh4
end

else
zh5=A(3,x)+A(3,y)
if zh5<=rong
newm=[x y]
[qa,qb]=size(solut)
solut((qa+1),1:length(newm))=newm
n(qa+1)=length(newm)
zhuang(qa+1)=zh5
end
end
end

if sum(n)<(m-1)
for i=2:m
[qqqa,qqqb]=size(solut)
kk=find(i==solut)
if isempty(kk)
solut(qqqa+1,1)=i
n(qqqa+1)=1
zhuang(qqqa+1)=A(3,i)
end
end
end

[op,ok]=size(solut)
for i=1:op
solut(i,n(i)+1)=1
end
solut=[ones(op,1) solut]

opt=0;
for i=1:op
for j=2:(n(i)+2)
med=c(solut(i,j-1),solut(i,j))
opt=opt+med
end
end

solut=solut-1