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

!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中的(’#，?!##-，当’#

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

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

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