GEODUAL软件说明书之完美匹配问题

软件下载：

链接：https://pan.baidu.com/s/1ypyIxnNngk-8XcqkcXSLQA 提取码：rpe6 复制这段内容后打开百度网盘手机App，操作更方便哦

1前言

Geodual软件包，它是由德国科隆大学的Mike Jünger研究团队开发的。该软件能够为20座城市左右规模的TSP题目，最小生成树问题和完美匹配问题给出最优解，同时还会提供一幅优美的护城河（moat）和控制区(control zone)分布图，用图的方式进行最优解证明，使用示例见图1。

图1 使用Geodual求解TSP问题并证明

2基础理论

2.1完美匹配问题

平面上有n个点的点集P（n为偶数），p，q点在笛卡尔坐标系下的坐标为(xp，yp)，(xq，yq)，它们之间的欧几里得距离为 $d_{pq} =\sqrt{\vert x_{p}-x_{q} \vert ^2+\vert y_{p}-y_{q} \vert ^2 }$ .

一个完美匹配问题是将n个点分割成 $\frac{n}{2}$ 对,使得 $\frac{n}{2}$ 对点两两之间组成的路径和最小。

下面讨论6个点的完美匹配问题。

图2 6个点的一组匹配结果

匹配问题的总路径和等于每对线段长度的总和，图2显示的是一组匹配结果，这不是最优的，因为可以给出更短的一组结果。

图3 6个点的完美匹配结果

如图3显示了此6个点的完美匹配结果。下面对其进行证明。以点p为圆心( $p\in P$ )， $r_{p}$ 为半径，画圆，每个圆之间可以相切但不能相交，如图4。进一步扩大圆的半径，可以得到图5.

图4 6个点分别做圆

图5 6个点的完美匹配问题图的证明

每组匹配点p和q的距离 $d_{pq}$ 为p圆和q圆两者半径之和 $r_{p} +r_{q}$ 。图中所有圆的半径之和就是匹配问题的总路径和。图5的解是最优解，通过图可以证明。图5中每对匹配点所产生的圆都处于相切的状态，若更换一组匹配点，得到其他解。例如将AD,BC的匹配换成AB,CD的匹配，则匹配的总结过会在原结果的基础上加上 $CD-r_{c} -r_{d}$ ，显然路径增加，因此可知图5的解为最优解。

然而，这种方法并不是万金油的。有另外一种情况如图6所示

图6 所有圆无法相切的情况

图6的匹配情况确实是完美匹配，但是无法使得所有圆的半径和等于匹配值的结果，据图中观察可知，上述奇数点的子集都会有一条单独的线端伸出子集范围。引入护城河（moat）的概念。

图7 引入护城河概念后的完美匹配证明

如图7，将护城河围绕着奇数点子集向外等距延申，最终两条护城河同样会相切于一点，这样点集中所有相切圆半径加上每条护城河的宽度就仍然是完美匹配问题的最优解值。这种方式使得可以为任何完美点匹配问题的实例构造图形的最优性证明。设 $p\in P$ ， $r_{p}$ 是以p为圆心的相切圆的半径，对于任意一个奇数子集 $S\subset P其中3\leq \vert S \vert\leq \frac{n}{2}$ ，使 $w_{s}$ 为S周边的护城河宽度值。那么，找到一个可行的相切圆和护城河布局，从而得到任何完美点匹配总长度的最佳可能下界的问题可以写成线性规划问题如下: