中国邮递员问题的动态规划算法研究

计算机研究与发展

./01234/5*/60891:9;931<=32>?9@94/692877

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

／／,!""#$%%%&$’()*#$$&$+++-（）：A’’’)A!’))，’%%B

中国邮递员问题的动态规划算法研究

费蓉

崔杜武

西安+）$%%AE

（西安理工大学计算机科学与工程学院（32259G"=/863G4H</6）F

!"#"$%&’()*’+)"#",(#-.$),%(/0".1"&+#+(),%(&"##20(%+-’.3

I9G:/22>*0G?0K0J3

（!）"##$$""’)*$+,-.$/-$0/12/./$$+./3.’0/)/.4$+5.**$-7/"#"3.’0/+$%%AE%&!(%%，6"&%6，

，2/#-%$&-*=G29;97/;869271/L496K3;719;9289>L1/59;;/1MNO#P9G&M0G2$)D%;32>;/4@9>LF7F

>236G<71/1366G23;8K/.HQ>6/2>;32>QHRH./=2;/2G2$)+%;HS9G2380198=9/1;896，FJJ=J36F;F：9;;92<9;8=98=/0=8/5104G293138942>8=9;/408G/2/519>02>32<H!8=3;L9920;9>G2632JJ;7F3FF

，>/63G2;H!28=G;73913;;896/534/1G8=6;G;71//;9>5/1;/4@G2=G29;97/;869271/L496H!28=97FJ7J*（*;;896，329K34/1G8=6*-?-O=G29;97/;8632>9<G;G/271/<9;;34/1G8=6）G;719;9289>388=95G1;8FJJ

，，8G69K=G<=63T9;G8/;;GL498/;/4@9*=G29;97/;863271/L496KG8=>9<G;G/271/<9;;8=/0=8HIG1;8/53447J（<8=9;;896JG@9;34/1G8=6*Q-O/2@9189>98/7/G2834/1G8=6）5/163TG2=96/>94/5*=G29;9FJJJJ8

，，（6/;863271/L496342>9<G;G/2&63TG28=92G8JG@9;P?-P*O048G;899<G;G/271/<9;;6/>94777FGJ7></2@91834/1G8=6）8/63T98=G;6/>943<</1>G2/8=9>9632>/58=96048G;899<G;G/271/<9;;H!28=G;JJ87>

，，*-?-O<32L90;9>8/;/4@9*=G29;97/;863271/L496HO>>G8G/23448=93<<013<58=G;;;896G;K3FFF/F，，@91G5G9>L=99U91G69283419;048;8=98=9/1G9;/58=9;934/1G8=6;31971/@9>32>71G2<G49/5/8G634G8F87J77FG;L1/3>929>G2*=G29;97/;863271/L496H

；4"(%7#>9<G;G/271/<9;;L9;8738=；*-?-O34/1G8=6；L9;8J56摘

要

在动态规划的决策过程思想基础上，针对无向中国邮递员问题，提出了一个新的搜索算法

（*，首次实现了中国邮递员问题的动态规划求解*-?-O=G29;97/;8632>9<G;G/271/<9;;34/1G8=6）H针对J

中国邮递员问题不能直接应用于决策思想，提出了弧点转换算法*（<Q-O/2@9189>98/7/G28J

，建立了该问题适用于决策的模型提出了多阶段决策过程模型转换算34/1G8=6）H进而针对这一模型，J

（6，转换所得模型符合多阶段决策过程需法P?-P*O048G;899<G;G/271/<9;;6/>94</2@91834/1G8=6）7>J

求，可用*-?-O算法求解中国邮递员问题H对每一算法都给出了其网络应用实例H对算法的正确性和理论性做出了证明，并对最优性原理在中国邮递员问题上做了一定扩展H

关键词

动态规划；最优路径；最优性*-?-O算法；

,-($’；,-$E

中图法分类号

法之一，可看做求决策)，’，…，，使指标函数)$)/

8引

言

（$，，’，…，）达到最优的极值问题4))H在客$/8$)/观世界中存在着大量动态规划问题，如最短路线问

［$］

题等H应用动态规划方法对最优路径问题进行求

动态规划是求解决策过程的有效最优化数学方

收稿日期：修回日期：CCCC’%%($’%)；’%%A%)%D

费蓉等：中国邮递员问题的动态规划算法研究

!DC

解已成为现代应用数学领域的重要研究方向!

［!，"］中国邮递员问题是管梅谷教授在!#世纪该问题具有很强的现实意义$#年代首先提出的，%

传统解决方案由&’()*’+与,)-*+)*于!#世纪.#年代给出，提出了构建欧拉图求解最优路径的思

［!］想%近年对中国邮递员问题新方法的探索集中于

（,）；+,?4/,+3

$

（,，，,3?，…，）1/+,$+,+$3?4

&4,

（&，）；/&+&$1

（,）4(［1（,，（,））（,3?）］，3*/322,+,+,+,?+3

…，,4$，?；（$3?）4#%2$3?+

［$］

定义’达到最优值的策略"使指标函数1,$

%是从,开始的后步子过程的最优策略，记做5,$@%，%｝%是全过程的最优策略从初始状｛…，，遗传算法等领域结合%本文针对中国邮递员问题，动态规划的决策过程思想，提出了一个新的搜索算法/0102（/-3*4+45)+6(7*’483+3)*59)84++

7:;

)936-(），首次实现了中国邮递员问题的动态规划求解%针对中国邮递员问题不能直接应用于决策思

想，本文提出了弧点转换算法/&02（8)*<4964’;46)5)3*67:;

)936-(），使邮递员问题模型能够转换为适用于决策的模型%对于求解可应用于决策的邮递员问题模型，提出了多阶段决策过程模型转换算法=10=/2（(>:63+645’

483+3)*59)84++()’4:8)*<4967:;

)936-(），使该模型符合多阶段决策过程需求，可适用于/0102算法求解中国邮递员问题%

中国邮递员问题

!"#定义基础

定义#"设"#

为结点，$为结点数，?!#!$，设结点集%@｛"?，"!，…，"$｝；若"#，"&之间有弧连接，定义该弧为’#&，设弧集(@｛’#&"?!##&!$｝；定义弧’#&长为)#&，设权值集合*@｛)#&

"?!#&!$｝

%定义!［A］

"设+,-

为第,阶段的状态变量，设.,为第,阶段的允许状态集合，即.,@｛+,-"

?!-!$｝%

定义$［A］

"设/,&（+,-）为第,阶段处于状态,-时的决策变量，设0,&（+,-）为+,-的允许决策集合，即0,&（+,-）@｛/,&（+,-）"?#&!$，?!-!$｝%

定义%"设+$B?为终端，.$B?

为终端集合，当+$B?可在.$B?

中变动时，称自由终端［C］%定义&［A］

"定义一个动态规划函数模型（,，+,

，/,（+,），1,，2,（+,）），其中，,为阶段数，按过程的演化划分；+,为状态数，由各段的位置确定；/,（+,）表示为从各个状态出发的走向；指标函数1,（+,，/,+,））为相邻两状态间的距离；最优值函数2,（+,）是由+,

出发到终点的最短距离%基本方程如下：/,/$5?$%态+?%（@+?%）出发，过程按照最优策略5?%$和状态转移方程演变经历所得的状态序列｛+?%，+!%，…，$%｝称最优轨线%

"!问题描述

根据上述定义基础，我们对中国邮递员问题做如下描述：

给定一个连通无向网络6@〈%，(，*〉，对每一弧’#&，有一权值)#&&#%从6中一个顶点出发，沿网络中的弧行走，使每条弧至少经过一次，然后回到出发点，这样一条路线称为投递路线%投递路线的长度定义为依次经过的弧长之和，长度最短的投递路线称为最优投递路线%

算法#（弧点转换算法()*+）

为使中国邮递员问题能够用动态规划思想处理，对于任何连通无向网络6，对6进行如下处理得到网络67：

（?

）将6中的弧定义为函数，保存其端点及权值，即对弧’#&，定义其为函数’,（"#，"&）@)#&，?

!!-，-为6中弧数目；

（!）取’,作为67中的一个顶点；找与其有公共顶点的弧函数’8（"#，"9）@)#9，连接两点，记做弧,8，权值:,8@

#；（"

）搜索所有的弧函数，执行步骤（!），直到所有具有公共顶点的弧函数被连接%

至此，模型建立完毕，我们重新定义网络67@(，%，;〉，其中，顶点集(@｛’,（"#，"&）"

?!#!，?!&!$，#’&，?!,!-｝，弧集%@｛"#&"?!!-，?!&!-，#’&｝，权值集;@｛:?8

"?!9!-，?!8!-，9’8｝

；定理#"对于网络67中的(’#，?!##-，当’#

与’&无公共端点时，必不存在弧"#&，?

!&#-，#’，连于结点’#与’&

之间%+!!#$+,"〈$#&（

）

证明!用反证法证明!已知在网络!中两弧"#

与"无公共端点，设存在弧%，#"&，"!$"#$$"!满足"与"对应在网络!&，##’中的两结点间$，#$有弧连接总有"与"对应!根据算法"的第#步，#$在!中的两弧相邻，即两个弧函数有公共顶点，这与已知相矛盾算法执行完毕，对于已调整好!所以，的网络!，!当"与"对应在网络’中$"#"&，#"#$必不存在弧%，!!中的弧无公共端点时，$"&，#$"

连于结点"与"之间证毕##!!$，#$

下面给出一个经过算法"

处理的实例：

费蓉等：中国邮递员问题的动态规划算法研究

!"!"个阶段#证明根据算法步骤%，对#算法$执行结束后，允许于任意多阶段决策过程模型#$的任意结点，状态集合共分为$（"!$）个，满足每个允许状态集合内部不存在通路，此外，根据算法步骤$，存在%个独立的允许状态集，共有$"个独立允许状态集，因此，根据多段决策分段原则，一定可以分成阶段数证毕$&$"!"的多阶段决策过程模型##

以图"为例，设%"为起点，则图$中的模型经过’()’*+算法处理，建成%个多段决策过程模型，分别为

#"：起始状态：&"，终态：&$，#$：起始状态：&"，终态：&"，#,：起始状态：&$，终态：&"，#%：起始状态：&$，终态：&$

#-./#$0123452671.81.9/4:;<43-./"=>*

?)+#

)10

计算机研究与发展)（）,,-，"))

而言也是最优策略!

定理"就是著名的最优性原理，通常略述为不论过去的状态和策略如何，对于前面的决策形成的当前状态而言，余下的各个决策必定构成最优策略!

对使用#最优性原理$%$&算法得到的结果，可做如下推广：

定理!在多阶段决策模型!""算法’结束后，中，已知最优策略，在中国邮递员问题基础上，对于前面的决策形成的当前状态而言，其子策略亦为#结束语

本文通过算法(，)建立起中国邮递员问题多阶段决策过程模型!，首次在动态规划基础上提出了"有效地解决了!模型的最优路径问#$%$&算法，"

题，可应用于计算机网络通信、交通运输等众多领

［0，1］该算法保证了模型转换过程中路径的完整域!

最优!

证明!设#(，#)，…，#$为最优投递路线，#%，%*(，…，#$为其子路线，针对中国邮递员问题，对%!#$，求其最优子策略，要求经过未遍历的所有状态变量再返回终端集合&$*(，综合该条件，根据最优性原理可知，其子策略必为使指标函数’%达到最小的最优策略!证毕!性质"!运行过程中()*不恒定，即权值在变化中!证明!对任意#)，#*，)!*，根据算法’决策过程，#)

的前一状态可能存在多个，每个状态产生的结果不同，导致#)结束顶点不同，所以可能存在)*+,或()*+#)两种状态，即运行过程中()*不恒定，权值在变化中!

证毕!

传统的中国邮递员算法通过加边构建欧拉图找

最优投递路线，算法’通过决策方式找出最优投递路线!

性质-!算法’可找出中国邮递员问题的所有最优轨线!

证明!根据定理)知，终端集合&$*(内所有状态变量均已做过第(阶段初始状态，即所有可能出现的情况均被建模，建好的所有!"模型包含了中国邮递员问题的所有路径，通过算法’可求得所有"模型满足’"$取最小值的决策及其对应轨线，综上，根据定义.最优轨线定义，算法’可找出中国邮递员问题的所有最优轨线!证毕!

经过#$%$&算法求解，所求实例的’"$+.，最优轨线结果如下：

#(/#’/#-/#"/#’/#)；#(/#"/#-/#’/#’/#)；#(/#"/#-/#"/#’/#)；#)/#’/#"/#-/#’/#(；#)/#’/#’/#-/#"/#(

；#)/#’/#"/#-/#"/#(

!性，但同时也存在着维数过大时不能提高速度的问题!在以后的研究中，我们将着重这一方面的分析和发展!

参

考

文

献

(

2!3!4566789，:!3!%;5<=>?!&@@6A5B%<987AC$;DE;877A9E!$;A9C5FD9，G5HI5;?5<：$;A9C5FD9J9AK5;?AF<$

;5??，(1.))

I!&!4D9B<，J!:!2!L>;F<!M;8@NON5D;<HAFN&@@

6AC8FAD9?!PD9BD9：ON5L8C7A6689$;5??PO%，(1Q.’3BAFD;A864D8;BD=LDB5;9L8FN578FAC?R89BSDDT!LDB5;9L8FN578FAC?

R89BSDDTU#D7@

>F5;L8FN578FAC?!

V>N89

：$>S6A?NA9ERD>?5D=R>8WND9EJ9AK5;?AF<D=:CA59C5XO5CN9D6DE<

，),,(!",1!"-1（A9#NA95?5）（《现代数学手册》编纂委员会!现代数学手册U计算机数学卷!武汉：华中科技大学出版社，),,(!",1!"-1）"

Y5A2D9E，#>A%>H>!G5HB<987AC86ED;AFN7D=B5CA?AD9@;DC5??D=>9=AZ5B?F5@9>7S5;!LAC;D565CF;D9AC?X#D7@>F5;，),,"，()（.）：(,!()（A9#NA95?5

）（费蓉，崔杜武!不定期决策过程优化模型的算法研究!微电子学与计算机，),,"，()（.）：(,!()）-2!3!4566789!%<987AC$;DE;877A9E!$;A9C5FD9，G5HI5;?5<：$;A9C5FD9J9AK5;?AF<$;5??，(1-Q.

3BAFD;A864D8;BD=LDB5;9&@@6A5BL8FN578FAC?R89BSDDT!LDB5;9&@@6A5BL8FN578FAC?R89BSDDTU[@5;8FAD98625?58;CNX[@FA786ON5D;<!45A\A9E：O?A9EN>8J9AK5;?AF<$;5??，(11Q!)-"!)..（A9#NA95?5

）（《现代应用数学手册》编委会!现代应用数学手册U运筹学与最优化理论卷!北京：清华大学出版社，(11Q!)-"!)..）Q

V89E:NAFD9E!Y>WW<N5>;A?FAC?58;CN86ED;AFN7Y%&"=D;=>WW<7>6FAU?F8E5B5CA?AD9@;DS657?!ID>;986D=#D7@>F5;25?58;CN89B%5K56D@

759F，(110，’-（Q）：.-)!.-.（A9#NA95?5）（王士同!多阶段模糊决策问题的模糊启发式搜索算法Y%&"!计算机研究与发展，(110，’-（Q）：.-)!.-.）0

MD6BS5;E%3!M595FAC86ED;AFN7?A9D@FA7AW8FAD989B78CNA95658;9A9E!G5H]D;T：&BBA?D9UV5?65<，(1011

#!R!$8@8BA7AFAD9，^!:F5AE6AFW!#D7SA98FD;A86[@FA7AW8FAD9，&6ED;AFN7?89B#D7@65ZAF<!G5HI5;?5<

：$;A9FAC5UR866，(10)##(!

费蓉等：中国邮递员问题的动态规划算法研究

，!"#$%&!"#$%$&’()*+,-,%.,/01$,#,,%$2/2’-"356,#7#"389%$,:,;%’<$5$%.,#:%674="6,-9$">"$?))?*@9,%:-5##,$6>*,$2=%=<A2-<$/%/<6,%$69,-"356,#"789%$,:,;%’<$4，9,##,:,<#-9%$6,#,:6:B$%.,#:%676,-9$">"="2=%$->5/,"6%3<>69,"#,3<$/C,-%:%"$@5"#6444

?’’

，!()#*)+)"#$%$&’DE*+,-,%.,/01$2/,#,,%$,>,-6#%-<>3<-9%$,%$&’FG<$/2

A*,$$69,"#,3"7,>,-6#"$%-,$%$,,#%$2%22’<$I%<"6"$$%.,#:%6*J,%$&’(H7#"3;%2B=’9<:!,,$4#"7,::"#"7-"356,#:-%,$-,%$;%4<$B$%.,#:%676,-9$">"*J%:#,:,<#-9="2=

，3%$6,#,:6:%$->5/,KL5>6%3,/%<6,-9$">"$/C,-%:%"$2=<（C），@@,6-*@5"#6@:6,344=

崔杜武，教授，博士生导师，主要研究方向为人工&’DE年生，智能、多媒体技术、供应链等*

（C）@:6,3@@*=

费蓉，硕士研究生，主要研究方向为决策分析与&’()年生，支持、最优化理论、虚拟现实*

$","-./01-/2.%)&3’

，89%$,:,M":63,$M#"!>,3:N<:4#,:,$6,/!#"7,::"#OBKPA,%QO5%$&’F):<$/:">.,/!*1/3"$/:<$/1*R*I"9$:"$%$=4=I，&’G):*L6%:N%/,>:,/%$.<#%"5:7%,>/::"69,/%:-5::%"$<!"563"/,><$/<>"#%6939<:4#<-6%-<>:%$%7%-<$-,*=522

：0,%$<65#,69,"#:6,3，/$<3%-4#"#<33%$<:6N",::,$-,:69,69"596"7#5>%$,<#<6,>$/69,:">56%"$"72<3=:==22922:4=<#,/5$/<$-*L69<:!,,$5:,/%$3<$"3<%$:*==/

S5##,:,<#-9"789%$,:,4":63<$4#"!>,3%:3<%$>!"569"N6":">.,%6!$<3%-4#"#<33%$9"596*K::6,3"7=<=/=2262=（8<>"#%693:%:4#"":,/7"#:">.%$9%$,:,4":63,$4#"!>,3:*L$69,::6,3，<$,N<>"#%6938MCMK9%$,:,4":63<$/,-%:%"$2428=2

，N#"-,::<>"#%693）%:4#,:,$6,/<669,7%#:66%3,9%-93<T,:%64"::%!>,6":">.,89%$,:,M":63<$M#"!>,3N%69C,-%:%"$M#"-,::42，（869"596*U%#:6"7<>>69,::6,32%.,:<>"#%69381MK"$.,#61/,6"M"%$6K>"#%693）7"#3<T%$69,3"/,>"789%$,:,M":63<$2=2222

，，（AM#"!>,3<>%$/,-%:%"$Q3<T%$69,$%62%.,:ACMA8K5>6%:6,,-%:%"$M#"-,::A"/,>8"$.,#6K>"#%693）3<T,69%:3"/,>44=24C2，<--"#/%$6"69,/,3<$/"769,A5>6%:6,,-%:%"$M#"-,::*L$69%:N<8MCMK-<$!,5:,/6":">.,89%$,:,M":63<$M#"!>,3*24C=，，，K//%6%"$<>>69,<--5#<-769%:::6,3%:.,#%7%,/!V,#%3,$6<>#,:5>6:69,69,"#%,:"769,:,<>"#%693:9<.,!,,$4#".,/<$/=="==,42M#%$-%>,"7S6%3<>%6%:!#"</,$,/%$89%$,:,M":63<$M#"!>,3*44=

，，W9%:<>"#%693:::6,3-<$!,5:,/%$-"356,#$,6N"#T-"335$%-<6%"$6#<77%-<$/6#<$:"#6,6-*L6,$:5#,:69,%$6,#<>%672=442="，’<69:/5#%$69,-"5#:,"73"/,>-"$.,#:%"$!56%6<>:"9<:69,4#"!>,369<669,:,,/-<$6!,,$9<$-,/N9,$69,/%3,$:%"$%:6""424，35-9*C5#%$9,7565#,#,:,<#-9N,:9"5>/4<"#,<66,$6%"$6"69%:/#<N!<-T*26=3

本文来源：https://www.bwwdw.com/article/tat1.html