组合{2,4}的序号为5。一般而言,令
则可得如下递推公式:
令
因此递推公式可重新表述为
反复用这个公式可得
它可以被用在动态规划法求TSP之中,借助于它就能够实现一般参考书上所说的时间复杂度。TSP的具体实现见附录1。
附录---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<k
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
联系客服