中国邮递员问题算法

邮递员问题求解算法
若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求；关于非Euler图，1973年，Edmonds和Johnson给出下边的解法：
设G是连通赋权图，则
（i）求V0
{v|v
V(G),
d(v)
1(mod2)}；
（ii）对每对极点
u ,v V0，求
d(u,v)（
d
(u,v)
是
u
与v的距离，
可用
Floyd
算法求得）；
iii）结构完整赋权图K|V0|，以V0为极点集，以d(u,v)为边uv的权；
iv）求K|V0|中权之和最小的完满对集M；
v）求M中边的端点之间的在G中的最短轨；
vi）在（v）中求得的每条最短轨上每条边增添一条等权的所谓“倍边”（即共端点共权的边）；
vii）在（vi）中得的图G'上求Euler回路即为中国邮递员问题的解。

多邮递员问题求解
邮局有k(k2)位送达员，同时送达信函，全城街道都要送达，达成任务返回邮局，怎样分派送达路线，使得达成送达任务的时间最早？我们把这一问题记
成kPP。

KPP的数学模型以下：
G(V,E)是连通图，v0
V(G)，求G的回路
C1,
,C k，
使得
（i ）v0
V(C i)
，i1,2,,k，
（ii）max
(
)min，
w
e
ik e
E(C)
（ii i）
k
E
(C i)E(G)
1。

§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。

1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。

2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。

城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。

3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。

伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。

对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。

我们将这些重复的边组成的集合称可行集，即找最小的可行集。

命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。

中国邮递员数学问题
中国邮递员数学问题是一个著名的数学问题，也称为"中国邮递员问题"。

这个问题源于邮递员在担任邮递员工作时，需要沿着不同的街道进行投递。

邮递员必须走遍每一条街道至少一次，然后回到出发地点。

问题的目标是寻找一条最短的路径，使得邮递员能够满足投递的要求。

具体问题描述如下：给定一个城市的街道网络图，每条街道上都有一个正整数表示街道的长度。

邮递员需要从一个特定地点出发，沿着街道网络进行投递，然后回到出发地点。

要求邮递员经过的路径总长度最短。

这个问题属于旅行商问题的变种，是一个NP-完全问题。

因为问题规模较大，难以找到一个最优解。

因此，通常采用近似算法进行求解，如TSP（Traveling Salesman Problem）等。

邮递员问题在实际中有很多应用，比如快递员的路线规划、物流配送等。

解决这个问题可以提高物流效率，减少成本。

中国邮递员问题解法中国邮递员问题是一个著名的组合优化问题，实际上是一个旅行商问题（Traveling Salesman Problem，TSP）的变种。

问题描述：给定一个城市集合和城市之间的距离矩阵，求解一个最短的邮递员路径，使邮递员能够从出发城市出发，经过每个城市恰好一次，最后回到出发城市。

解法：1.暴力搜索暴力搜索是最简单直观的解法。

遍历所有可能的路径，计算每个路径的总距离，最后选择最短的路径。

这种解法的时间复杂度为O(n!)，随着城市数量的增加而急剧增加，效率非常低，只适用于小规模问题。

2.动态规划动态规划是一个更高效的解法。

使用一个二维数组dp[i][j]表示从城市i出发经过城市集合j的最短路径长度，其中j是一个二进制数，表示哪些城市已经访问过。

动态规划的转移方程为：dp[i][j] = min{dp[k][j XOR (1 << k)] + distance[i][k]}，其中k表示已经访问的最后一个城市。

利用这个递推关系，可以逐步计算出dp[0][1<<n-1]，即从城市0出发经过所有城市的最短路径。

最后，将此路径与每个城市的距离相加，得到最终的最短路径长度。

3.贪心算法贪心算法是一种更简单的解法。

首先选择一个起始城市，然后每次选择距离最近且未被访问过的城市，将其加入路径中。

重复此过程，直到访问完所有城市，然后回到起始城市。

这种解法的时间复杂度为O(n^2)，但由于贪心策略的局限性（可能会出现回头或死胡同），所以得到的解并不一定是最优解。

以上是三种常用的解决中国邮递员问题的方法，具体可以根据实际情况选择合适的算法进行求解。

中国邮递员问题的求解实例前面已经讲过，对于欧拉图，可以直接用Fleury算法找出一条欧拉巡回路线；对于半欧拉图，可以先求出奇点u和v之间的最短路径P,令G =G P，贝U G *为欧拉图，然后用Fleury算法来确定一个G *的欧拉巡回，它就是G的最优巡回。

当G有2n个奇点(n>1),可以用Edmonds算法解决，步骤如下：(1) 用Floyd算法求出所有奇点之间的最短路径和距离矩阵。

(2) 用匈牙利法或0-1规划法求出所有奇点之间的最佳配对。

(3) 在原图上添加最佳配对所包含的两两顶点之间的最短路得到欧拉图G *。

⑷用Fleury算法确定一个G *的欧拉巡回，这就是G的最优巡回。

以上步骤的关键是找出2n个奇点的最佳配对，举例如下。

例图3是某区街道示意图，各边的长度数据如下表所示。

现在需要对每条街道找最优巡回，需要先求26个奇点的最佳配对。

先用Floyd算法求出所有42个顶点之间的最短路距离和路径。

程序如下：E=[1 2 10261 4 402........ 注：每一行代表一条边(两个顶点和边长)，此处省略59行40 39 198];for i=1:42for j=1:42if j==ia(i,j)=0; elsea(i,j)=inf; end end endfor k=1:62 i=E(k,1);j=E(k,2);a(i,j)=E(k,3);a(j,i)=E(k,3); end[D,R]=floyd(a);图3某区街道示意图然后求26个奇点的最优配对，这可以用Lin go 求解，编写程序如下:MODEL: SETS:4U12°26"30 O3539 40413*27 21 4128* 3338仆2934O114251015• 1724，25201922 23 32313637dot/2,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20,22,24,25,26,28,29,30,36,40,41/;LINKS(dot,dot)| &2 # GT # & 1:C,X;ENDSETSDATA:C=1319 1065 651 650 939 1228 1463 1500 1213 617 895 1590 1709 1377 1033 1112 1652 1761 1853 1418 1832 2124 2151 2479 1687254 668 1173 1462 1751 198 181 402 1140 1418 2113 453 601 945 1635 2175 2284 597 1941 2355 868 1463 1498 2104414 919 1208 1497 1732 435 148 886 1164 1859 679 347 691 1381 1921 2030 823 1687 2101 1094 1689 1724 1850505 794 1083 1318 849 562 472 750 1445 1058 726 382 967 1507 1616 1202 1273 1687 1473 2005 2103 1541289 578 813 1354 1067 471 245 940 1563 1231 887 462 1002 1111 1707 768 1182 1978 2005 2333 1541 289 524 1643 1356 760 534 651 1852 1520 1176 504 828 886 1996 594 1008 2267 2197 2525 1733235 1932 1645 1049 823 362 2141 1809 1465 793 706 597 2285 883 890 2556 2486 2814 20222167 1880 1284 1058 163 2376 2044 1700 1028 507 398 2520 1105 691 2766 2658 2986 2194306 1321 1599 2294 272 505 849 1571 2111 2220 416 1877 2291 687 1282 1317 20081034 1312 2007 531 199 543 1265 1805 1914 675 1571 1985 946 1541 1576 1702360 1411 1203 871 527 577 1117 1226 1347 883 1297 1618 1534 1862 10701101 1563 1231 887 217 757 866 1707 523 937 1978 1894 2222 14302282 1950 1606 884 344 235 2426 942 528 2603 2495 2823 2031332 676 1398 1938 2047 144 1704 2118 415 1010 1045 1824344 1066 1606 1715 476 1372 1786 747 1342 1377 1503722 1262 1371 820 1028 1442 1091 1623 1721 1159540 649 1542 306 720 1813 1729 2057 1265109 2082 598 184 **** **** 2479 16872191 707 293 2368 2260 2588 17961848 2262 271 866 901 1680414 1711 1603 1931 11392075 1967 2295 1503595 630 1409360 832792;ENDDATA图4 26个奇点的最优配对MIN=@SUM(LINKS:C *X);@FOR(LINKS:@BIN(X));@FOR(dot(l):@SUM(LINKS(J,K)| J #EQ# I #OR# K #EQ# I:X(J,K))=1);END运行以上程序，得到最优配对结果为：2与6、4与12、5与13、8与9、10与11、14 与15、17 与25、18 与26、19 与20、22 与28、24 与29、30 与36、40 与41。

一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。

请为他选择一条路线，使其所行路程尽可能短。

如何找到这条最短的路线，本文将逐步分析讨论这个问题。

与上述问题类似的是一个哥尼斯堡七桥问题。

在18世纪，东普鲁士有个城市叫哥尼斯堡，普瑞格尔河横贯其境，河中有两个美丽的小岛，全城有七座桥将河的两岸与河中两岛沟通，市民们喜欢四处散步，于是便产生这样的问题：是否可以设计一种方案，使得人们从自己家里出发，经过每座桥恰好一次，最后回到家里。

热衷于这个有趣问题的人们试图解决它，但没有人能给出答案，后来数学家欧拉证明了这样的散步是不可能的。

下面我们把上述七桥问题转化为图论问题：一个连通图G由有限结点与连接这些结点的若干条互不相交的边组成，能否做一条连续的曲线，使得这条曲线走过所有的边恰好一次。

定义经过图G的每条边恰好一次的迹称为图G 的欧拉迹。

图 G 的环游是指经过图 G 每条边至少一次的闭途径，欧拉环游是指经过图 G 每条边恰好一次的环游。

一个图若包含欧拉环游，则这个图称为欧拉图。

定理 1 一个非空连通图是欧拉图当且仅当它没有奇点。

证明必要性：设图 G 是一个欧拉图，C 是图 G 中一个欧拉环游，其起点(也是终点)为 u。

对于 Av∈V(G)，v 必在 C 上出现。

因 C 每经过 v 一次，就有两条与 v 关联的边被使用。

因为欧拉环游包含图 G 的每条边，所以对于所有的v≠u，d(v)都是偶数。

类似的，由于 C 开始终止于u，所以d(u)也是偶数。

所以，图 G 没有奇点。

充分性：无妨设ν(G)>1．因 G 连通且无奇点，故δ(G)≥2，因而必含有圈．当ν(G)=2 时，设仅有的两点为 u、v，则 u、v 间必有偶数条边，它们显然构成欧拉回路．假设ν(G)=k 时，结论成立．当ν(G)=k＋1 时，任取 v∈V(G)．令 S={v 的所有关联边}．记S 中的边为e1、e2、…、em，其中 m=d(v)为偶数．记 G'= G \ v。

1. 邮递员问题求解算法
若此连通赋权图是Euler 图，则可用Fleury 算法求Euler 回路，此回路即为所求；对于非Euler 图，1973年，Edmonds 和Johnson 给出下面的解法：
设G 是连通赋权图，则
（i ）求)}2(m od 1)(),(|{0=∈=v d G V v v V ；
（ii ）对每对顶点0,V v u ∈，求),(v u d （),(v u d 是u 与v 的距离，可用Floyd 算法求得）；
（iii ）构造完全赋权图||0V K ，以0V 为顶点集，以),(v u d 为边uv 的权； （iv ）求||0V K 中权之和最小的完美对集M ；
（v ）求M 中边的端点之间的在G 中的最短轨；
（vi ）在（v ）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）；
（vii ）在（vi ）中得的图'G 上求Euler 回路即为中国邮递员问题的解。

2. 多邮递员问题求解
邮局有)2(≥k k 位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP 。

KPP 的数学模型如下：
),(E V G 是连通图，)(0G V v ∈，求G 的回路k C C ,,1 ，使得
（i ） )(0i C V v ∈，k i ,,2,1 =，
（ii ） min )(max )(1=∑∈≤≤i C E e k
i e w ，
（iii ）
k i i G E C E 1)()(==。