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

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

Research on Chinese Postman Problem Decision Process Algorithm

Chinese postmen problem was presented by professor GUAN Mei-Gu in 1960s, and solved by J.Edmonds and E.L.Johnson in 1970s. Being a mature theory system, dynamic programming has two essences: the thought of ruling separately and the solution of redundancy. It has been used in many domains. In this paper, a system of algorithms is proposed for solving Chinese postmen problem. In the system, a new algorithm CPDPA(Chinese postman decision process algorithm)is presented at the first time, which makes it possible to solve Chinese postman problem with decision process thought. First of all, the system gives algorithm CEPA(convert edge to point algorithm)for making the model of Chinese postman problem apply in decision-making, then, it gives MDPMCA(multistep decision process model convert algorithm)to make this model according to the demand of the multistep decision process. In this way, CPDPA can be used to solve Chinese postman problem. Additionally, the accuracy of this system is verified by the experimental results, the theories of these algorithms are proved, and principle of optimality is broadened in Chinese postman problem.