读-对称型TSP下界的快速估算法

最近受困于无法找到一种简单快捷的TSP下界求解方法，找到了一篇老文章，方法十分简单，效果十分优良。文献名称等如图1

图1 文献详情

论文中定义了以下变量：

图2 论文定义的若干变量  

TSP问题本身是求解全局的最短路径的，因此一般情况下，点通常会跟与其相邻最近的点间构成路径。根据上面这条经验，论文作者将每个点和离此点最近的两个点间距离之和最为过此点的两条路径下界估计值，而TSP问题的总路径也就是所有的路径点和其最近的两个点间距离之和的一半（加了两次）如图3。此种方式确实很粗糙，但是确实是一种快速求解下界的土法。

图3 快速估计下界方法

在这个粗糙的估计值基础上，论文作者加了一个修正量，用于进一步逼近下界值。其对TSP闭合路径产生的可能情况做了分类讨论。其中定义了两个变量，如图4。

图4 定义了i的两个最短边长

1.1当在TSP回路中

此种情况下，节点i不用调整，因为其计算下界值时将已经算入了。但是与其相连的j点并不是算的，而是算的自己的一条最短边，因此至少会增加

1.2当不在TSP回路中

此种情况下，节点i得调整，说明为了保证TSP路径的生成，i节点并没有全选最短路径，因此在原来的基础上至少会增加

图5 e(i)1在base(T)基础上增加量

同样对于来说也分这两种情况

2.1当在TSP回路中

2.2当不在TSP回路中

图6 e(i)2在base(T)基础上增加量

因此

图7 修正量公式

因此，估计的下界为.

论文作者将此算法运用在公布的最优数据集中，得出实验结果如图8所示。其准确率精度十分高，具有十分重要的工程意义。

图8 此算法计算结果

为了证明此算法的估计真实准确性，笔者使用matlab复现了一遍，如图9所示，x为数据序号，笔者使用了一个1000组的TSP数据集进行验证。可见其误差率分布均匀，误差率标准差为6.038，估值较为均匀准确，误差率符合正态分布如图10。

图9 笔者验证此算法估计的准确性

图10 估计误差率概率密度分布图

将matlab中的函数发布如下：

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

xy.in_point=AA;

[xy.num,~]=size(xy.in_point);      %获得输入点的数量

xy.real_path=zeros(xy.num,xy.num);  %初始化路径布尔变量矩阵

xy.dmat=[];  %初始化路径点的距离矩阵

if isempty(xy.dmat)    %计算路径点之间的距离矩阵

    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点最小值序列

xy.dmini2=zeros(1,xy.num);%距离i点第二小值序列

xy.dmini3=zeros(1,xy.num);%距离i点第三小值序列

xy.lowbound_gu=0;

for i=1:xy.num      %base(T)计算

    xy.bb=unique(xy.dmat(i,:));%对距离向量排序

    xy.dmini1(1,i)=xy.bb(2);%距离i点最小值

    xy.dmini2(1,i)=xy.bb(3);%距离i点第二小值

    xy.dmini3(1,i)=xy.bb(4);%距离i点第三小值

    xy.lowbound_gu=xy.lowbound_gu+0.5*(xy.bb(2)+xy.bb(3));%计算base(T)

end

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

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

for i=1:xy.num      %Adjust(T)计算

    [~,m]=find(xy.dmat==xy.dmini1(1,i)); %求出距离i点最小值的序号  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);  %得到修正后的估计值

end

for i=1:xy.num      %Adjust(T)计算

    [~,m]=find(xy.dmat==xy.dmini2(1,i)); %求出距离i点最小值的序号  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);  %得到修正后的估计值

end

kk= xy.lowbound_gu;

end

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