附录---MATLAB代码

function [pmin,pvmin]=tspdp(D)

%TSPDP旅行销售员问题(TSP)的动态规划(Dynamic Programming)算法的递推实现

%

%[pmin, pvmin] = tspdp( D )

%输入参数：D --- 两两城市之间的距离矩阵，双精度二维数组

%输出参数：pmin --- 最短路线双精度，一维行数组

%pvmin --- 最短距离，双精度数

%

%Example: [pmin,pvmin]=tspdp(rand(5))

%

%注意：经分析，其时间复杂度为O(n*2^n)，也就是说n 每增大1，运行时间大致上变成

%原来的2 倍。因此，n不能太大，当取在12以内时，速度很快。若用C++等实现,在20以

%内都可以接受。

n=length(D);

pasmat=pascal(n+1);

fP=calfP(D,pasmat);

pvmin=inf;

for j=1:n-1

v=fP{n-1}(j,1)+D(j,n);

if pvmin>v

pvmin=v;

jmin=j;

end

end

pmin=zeros(1,n+1);

pmin(n:n+1)=[jmin, n];

C=1:n-1;

for j=n-1:-1:1

Csn=combineseqnum(C,n-1,j,pasmat);

I=find(pmin(j+1)==C);

pmin(j)=fP{j}(I,2,Csn);

C(I)=[];

end

%------------------------------------------------------------------------

function fP=calfP(D,pasmat)

n=length(D);

for k=1:n-1

fP{k}=zeros(k,2,pasmat(k+1,n-k));

end

for Csn=1:n-1

fP{1}(:,:,Csn)=[D(n,Csn),n];

end

for k=2:n-1

C=zeros(1,k);

Csn=0;

curi=1;

while curi

if C(curi)>=n-1-k+curi

curi=curi-1;

else

C(curi:end)=C(curi)+1:C(curi)+1+k-curi;

curi=k;

Csn=Csn+1;

S=C(2:k);

for I=1:k

CI=C(I); %后面要重复使用

Ssn=combineseqnum(S,n-1,k-1,pasmat);

vmin=inf;

for j=1:k-1

v=fP{k-1}(j,1,Ssn)+D(S(j),CI);

if vmin>v

vmin=v;

jmin=S(j);

end

end

fP{k}(I,:,Csn)=[vmin, jmin];

if I

S(I)=CI;

end

end

end

end

end

%-----------------------------------------------------------------------

function sn=combineseqnum(p,n,r,pasmat)

%COMBINESEQNUM求{1,2,...,n}中抽取r个数构成的组合在所有组合(升序)按字典序排

%序后所处的序号(从1开始编号)。

%

%sn = combineseqnum(p , n)

%输入参数：p --- {1,2,...,n}的一个组合，用数值向量表示，行或列均可，要求按

%升序排列

%n --- 元素的个数，即{1,2,...,n}中的 n

%r --- p中元素的个数

%pasmat --- 帕斯卡矩阵

%输出参数：sn --- p在所有组合中的按字典序排序后的编号

%

%Example: sn=combineseqnum([1 3],4)

%

if r>1

sn=pasmat(r+1,n-r+1);

for I=1:r

nn=n-p(I);

rr=r+1-I;

if nn>=rr

sn=sn-pasmat(rr+1,nn-rr+1);

end

end

else

sn=p;

end