最近受困于無法找到一種簡單快捷的TSP下界求解方法，找到了一篇老文章，方法十分簡單，效果十分優(yōu)良。文獻(xiàn)名稱等如圖1

圖1 文獻(xiàn)詳情

論文中定義了以下變量：

圖2 論文定義的若干變量??

TSP問題本身是求解全局的最短路徑的，因此一般情況下，點(diǎn)通常會跟與其相鄰最近的點(diǎn)間構(gòu)成路徑。根據(jù)上面這條經(jīng)驗(yàn)，論文作者將每個點(diǎn)和離此點(diǎn)最近的兩個點(diǎn)間距離之和最為過此點(diǎn)的兩條路徑下界估計(jì)值，而TSP問題的總路徑也就是所有的路徑點(diǎn)和其最近的兩個點(diǎn)間距離之和的一半（加了兩次）如圖3。此種方式確實(shí)很粗糙，但是確實(shí)是一種快速求解下界的土法。

圖3 快速估計(jì)下界方法

在這個粗糙的估計(jì)值基礎(chǔ)上，論文作者加了一個修正量，用于進(jìn)一步逼近下界值。其對TSP閉合路徑產(chǎn)生的可能情況做了分類討論。其中定義了兩個變量，如圖4。

圖4 定義了i的兩個最短邊長

1.1當(dāng)在TSP回路中

此種情況下，節(jié)點(diǎn)i不用調(diào)整，因?yàn)槠溆?jì)算下界值時將已經(jīng)算入了。但是與其相連的j點(diǎn)并不是算的，而是算的自己的一條最短邊，因此至少會增加

1.2當(dāng)不在TSP回路中

此種情況下，節(jié)點(diǎn)i得調(diào)整，說明為了保證TSP路徑的生成，i節(jié)點(diǎn)并沒有全選最短路徑，因此在原來的基礎(chǔ)上至少會增加

圖5 e(i)1在base(T)基礎(chǔ)上增加量

同樣對于來說也分這兩種情況

2.1當(dāng)在TSP回路中

2.2當(dāng)不在TSP回路中

圖6 e(i)2在base(T)基礎(chǔ)上增加量

因此

圖7 修正量公式

因此，估計(jì)的下界為.

論文作者將此算法運(yùn)用在公布的最優(yōu)數(shù)據(jù)集中，得出實(shí)驗(yàn)結(jié)果如圖8所示。其準(zhǔn)確率精度十分高，具有十分重要的工程意義。

圖8 此算法計(jì)算結(jié)果

為了證明此算法的估計(jì)真實(shí)準(zhǔn)確性，筆者使用matlab復(fù)現(xiàn)了一遍，如圖9所示，x為數(shù)據(jù)序號，筆者使用了一個1000組的TSP數(shù)據(jù)集進(jìn)行驗(yàn)證?？梢娖湔`差率分布均勻，誤差率標(biāo)準(zhǔn)差為6.038，估值較為均勻準(zhǔn)確，誤差率符合正態(tài)分布如圖10。

圖9 筆者驗(yàn)證此算法估計(jì)的準(zhǔn)確性

圖10 估計(jì)誤差率概率密度分布圖

將matlab中的函數(shù)發(fā)布如下：

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function kk = lowbound_cal(AA)

xy.in_point=AA;

[xy.num,~]=size(xy.in_point);? ? ? %獲得輸入點(diǎn)的數(shù)量

xy.real_path=zeros(xy.num,xy.num);? %初始化路徑布爾變量矩陣

xy.dmat=[];? %初始化路徑點(diǎn)的距離矩陣

if isempty(xy.dmat)? ? %計(jì)算路徑點(diǎn)之間的距離矩陣

? ? a = meshgrid(1:xy.num);

? ? xy.dmat = reshape(sqrt(sum((xy.in_point(a,:)-xy.in_point(a',:)).^2,2)),xy.num,xy.num);

end

xy.dmini1=zeros(1,xy.num);%距離i點(diǎn)最小值序列

xy.dmini2=zeros(1,xy.num);%距離i點(diǎn)第二小值序列

xy.dmini3=zeros(1,xy.num);%距離i點(diǎn)第三小值序列

xy.lowbound_gu=0;

for i=1:xy.num? ? ? %base(T)計(jì)算

? ? xy.bb=unique(xy.dmat(i,:));%對距離向量排序

? ? xy.dmini1(1,i)=xy.bb(2);%距離i點(diǎn)最小值

? ? xy.dmini2(1,i)=xy.bb(3);%距離i點(diǎn)第二小值

? ? xy.dmini3(1,i)=xy.bb(4);%距離i點(diǎn)第三小值

? ? xy.lowbound_gu=xy.lowbound_gu+0.5*(xy.bb(2)+xy.bb(3));%計(jì)算base(T)

end

add_nodei1=zeros(1,xy.num);%i中最小邊的修正值

add_nodei2=zeros(1,xy.num);%i中第二小邊的修正值

for i=1:xy.num? ? ? %Adjust(T)計(jì)算

? ? [~,m]=find(xy.dmat==xy.dmini1(1,i)); %求出距離i點(diǎn)最小值的序號? xy.dmini2(1,m(2))就是dmin(j,2)

? ? add_nodei1(1,i)=0.5*min(abs(xy.dmini3(1,i)-xy.dmini1(1,i)),abs(xy.dmini1(1,i)-xy.dmini2(1,m(2))));%求出dmin(j,2)

? ? xy.lowbound_gu= xy.lowbound_gu+add_nodei1(1,i);? %得到修正后的估計(jì)值

end

for i=1:xy.num? ? ? %Adjust(T)計(jì)算

? ? [~,m]=find(xy.dmat==xy.dmini2(1,i)); %求出距離i點(diǎn)最小值的序號? xy.dmini2(1,m(2))就是dmin(j,2)

? ? add_nodei2(1,i)=0.5*min(abs(xy.dmini3(1,i)-xy.dmini2(1,i)),abs(xy.dmini2(1,i)-xy.dmini2(1,m(2))));%求出dmin(j,2)

? ? xy.lowbound_gu= xy.lowbound_gu+add_nodei2(1,i);? %得到修正后的估計(jì)值

end

kk= xy.lowbound_gu;

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%