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 applyin 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.