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

摘要：

在动态规划的决策过程思想基础上,针对无向中国邮递员问题,提出了一个新的搜索算法CPDPA(Chinese postman decision process algorithm),首次实现了中国邮递员问题的动态规划求解.针对中国邮递员问题不能直接应用于决策思想,提出了弧点转换算法CEPA(convert edge to point algorithm),建立了该问题适用于决策的模型.进而针对这一模型,提出了多阶段决策过程模型转换算法MDPMCA(multistep decision process model convert algorithm),转换所得模型符合多阶段决策过程需求,可用CPDPA算法求解中国邮递员问题.对每一算法都给出了其网络应用实例.对算法的正确性和理论性做出了证明,并对最优性原理在中国邮递员问题上做了一定扩展.

关键词：动态规划、最优路径、CPDPA算法、最优性

所属期刊栏目：42

分类号：TP312;TP18(计算技术、计算机技术)

在线出版日期：2005-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：294-299