图与网络——中国邮递员问题的R实现

中国邮递员问题是邮递员在某一地区的信件投递路程问题。邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短。这个问题由中国学者管梅谷在1960年首先提出，并给出了解法——“奇偶点图上作业法”，被国际上统称为“中国邮递员问题”。用图论的语言描述，给定一个连通图G，每边e有非负权)，要求一条回路经过每条边至少一次，且满足总权最小。比如：扫雪车、处理垃圾车、散水车、送信员等路线规划。

一、中国邮递员问题

一个邮递员从邮局出发，要走完他所管辖范围内的每一条街道至少一次再返回邮局，如何选择一条尽可能短的路线？这就是中国邮递员问题(Chinese Postman Problem)，简称CPP问题。

欧拉回路:给定一个连通多重图$G$，若存在一条链，过每边一次，且仅一次，则称为这条链为欧拉链。若存在一个简单图，过每边一次，且仅一次，称为这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。

中国邮递员问题可用图论语言叙述为：在一个具有非负权的带权连通图$G$中，找出一条总权重最小的环游，这种环游称为最优环游。
① $G$是欧拉图，则$G$的任意欧拉回路都是最优环游。
②$G$不是欧拉图，则$G$的任意一个环游必定通过某些边不止一次。将边$e$的两个端点再用一条权为$w(e)$的新边连接时，称边$e$为重复的。此时CPP问题与下述问题等价：
若$G$是给定的有非赋权的赋权连通图，用添加重复边的方法求欧拉回路$G$的一个欧拉赋权母图$G^*$，满足

\[min\sum_{e\in E(G^*)-E(G)} w(e)
\]

求$G^*$的欧拉回路。

1.1 奇偶点图上作业法

1960年我国管梅谷发表于数学学报上的论文“奇偶点图上作业法”，是针对于中国邮递员问题的最早论文，将关于“一笔画”问题的一些已知结果与物资调拨中的图上作业法的基本思想相结合，得到了CPP问题中添边策略的一种方法。

奇偶点:根据顶点连接边的次数划分。

①生成初始可行方案：
若图中有奇点，则把它配成对，每一对奇点之间必有一条链，把这条链的所有边作为重复边加到图中去，新图中必无奇点。便给出了第一个可行方案。
②调整可行方案：
使重复边总长度下降.当边$(w,v)$上有两条或两条以上的重复边时，从中去掉偶数条，得到一个总长度较小的方案。于是有：
1)在最优方案中，图的每条边上最多有一条重复边。
2)在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半。
③判断最优方案的标准：
一个最优方案一定是满足上述1)和2)的可行方案。反之，一个可行方案若满足上述1)和2)，则这个可行方案一定是最优方案。
根据判断标准，对给定的可行方案，检查它是否满足上述条件1)和2)。若满足，所得方案即为最优方案；若不满足，则对方案进行调整，直至上述条件1)和2)均得到满足时为止。

1.2 最小二分匹配法

奇偶点图上作业法是全球范围内研究CPP问题的先驱，他提出了一种添边策略，其中最关键的是指出了一非欧拉图向欧拉图转化的实质是奇点之间的两两匹配，联想到图论二分匹配中的最大权匹配，本文提出最小权匹配法来完成非欧拉图向欧拉图的转换。

设$G=(V,E)$为一简单无向连通图， $D$为使用floyd算法求得的图的最短路程矩阵，$P$为对应的路径矩阵。$V_1$为图$G$的奇点集，由图论基础知识可证明一简单图的奇点个数为偶数，记其为$n$。构建二分图 $B=(S,T,E^{'})$，其中 $S = T =V_1$， $E^{'}$的构建如下：

\[w\left(e_{i j}^{\prime}\right)= \begin{cases}D_{S_i T_j}^{\prime}, & \text { if } S_i =T_j \\ \infty, & \text { if } S_i=T_j\end{cases}
\]

求该二分图的最小权匹配，引入决策变量 $x_{i j}=0,1$ 来表示 $S_i$ 与 $T_j$ 的匹配关系，若 $x_{i j}=1$ 则表示与匹配，反之则不匹配，可建立数学规划模型如下:

\[\begin{gathered}
\min w\left(e_{i j}^{\prime}\right) x_{i j} \\
\text { s.t. } \begin{cases}\sum_{i=1}^n x_{i j}=1, & j=1,2, \ldots, n \\
\sum_{j=1}^n x_{i j}=1, & i=1,2, \ldots, n \\
x_{i j}=x_{j i}, & i=1,2, \ldots, n ; j=1,2, \ldots, n \\
x_{i j} \in\{0,1\}, & i=1,2, \ldots, n ; j=1,2, \ldots, n\end{cases}
\end{gathered}
\]

由该模型求出奇点集的两两匹配，再结合floyd算法得到的最短路程矩阵对应的路径矩阵，可得到 $G$ 由生成的最小权欧拉图 $G^*=\left(V, E^*\right)$ 。则此时CPP问题的最优目标值已可求出，即是将的边集中的每一条边都走一遍，其值为

\[L=\sum_{i \in E^*} w\left(e_i\right)
\]

二、fleury算法

无论是无向图还是有向图，皆通过上述模型求解奇点的最小权匹配并由此构造出对应于原图的最小权欧拉图，由中国邮递员问题中的图论语言描述中推导出的等价问题可知，原问题已转化为求欧拉图的一条欧拉回路。
故本段对如何求欧拉图中的欧拉回路进行研究，fleury算法是一种常用的求欧拉图中一条欧拉回路的算法。

设$G=(V,E)$为一欧拉图，下为fleury 算法的算法流程：
STEP1 任取$v_0\in V $ ，令 $C_0 =v_0$ ；
STEP2 假设当前已沿迹$C_i =v_0e_1v_1e_2v_2 \cdots e_iv_i $来到顶点 $v_i$，按照如下规则从边集 $E-\{e_1,e_2,\cdots,e_i\}$中选取$e_{i+1}$：
⑴ $e_{i+1}$与 $v_i$关联；
⑵ 除非无其他可选边，否则$ e_{i+1}不为图$G_i=G-\{e_1,e_2,\cdots ,e_i\}$的割边。
STEP3 当 STEP2 无法继续进行时停止算法。

当算法停止时，得到的迹$ C_m =v_0e_1v_1e_2v_2 \cdots e_mv_m $为图 $G$的一条欧拉回路。

定理: 由fleury 算法求得的迹必为欧拉回路。

三、Python算法

案例：点F是邮局所在地点，该邮局由邮递员进行派件，尝试给出合理的派件路线（每条道路需来回各送一次）。这样的图必为欧拉图，所以我们无需考虑生成欧拉图的部分，直接对图进行划分。

代码进行时，可参看链接博客

总结

中国邮路问题（Chinese Postman Problem）是一个非常经典的图论问题：一个邮递员送信，要走完他负责投递的全部街道（所有街道都是双向通行的且每条街道可以经过不止一次），完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短呢？如果将这个问题抽象成图论的语言，就是给定一个连通图，每条边的权值就是街道的长度，本问题转化为在图中求一条回路，使得回路的总权值最小。
如果街道的连通图为欧拉图，则只要求出图中的一条欧拉回路即可。否则，邮递员要完成任务就必须在某些街道上重复走若干次。如果重复走一次，就加一条平行边，于是原来对应的图形就变成了多重图。只是要求加进的平行边的总权值最小就行了。于是，我们的问题就转化为，在一个有奇度数结点的赋权连通图中，增加一些平行边，使得新图不含奇度数结点，并且增加的边的总权值最小。求所增加边总权值最小的方案，需要我们找出所有奇度顶点（偶数个）来两两分组，对每小组中的两个点求其最短路径，进而求出每分组的总权值。对所有分组情况，找出最小权值即是最佳方案。