摘要
在动态规划的决策过程思想基础上 ,针对无向中国邮递员问题 ,提出了一个新的搜索算法CPDPA(Chinesepostmandecisionprocessalgorithm) ,首次实现了中国邮递员问题的动态规划求解 针对中国邮递员问题不能直接应用于决策思想 ,提出了弧点转换算法CEPA (convertedgetopointalgo rithm) ,建立了该问题适用于决策的模型 进而针对这一模型 ,提出了多阶段决策过程模型转换算法MDPMCA (multistepdecisionprocessmodelconvertalgorithm) ,转换所得模型符合多阶段决策过程需求 ,可用CPDPA算法求解中国邮递员问题 对每一算法都给出了其网络应用实例 对算法的正确性和理论性做出了证明 。
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2005年第2期294-299,共6页
Journal of Computer Research and Development
