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

摘要

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