)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)##(!