一类多投递员中国邮路问题动态规划模型研究

Motion Planning Algorithms for Certain Many Postmen Chinese Postmen Problems

采用动态规划决策思想,针对KPCPP问题,建立了一套算法体系.该类问题不能直接应用于决策思想,通过弧点转换算法,构建了该问题适用于决策的模型.在此模型基础上,提出了多阶段决策过程模型转换算法,得到的模型符合多阶段决策过程需求;在动态规划的基础上,提出了一个新的搜索算法KMDPA,首次实现了该类问题的动态规划模型求解,并对该算法体系的理论性和有效性做出了证明.

A motion planning algorithm KMDPA（k postmen decision process algorithm） is presented in order to solve a kind of many postmen Chinese problems in which k is equal to the number of the edges of start vertex. The CEPA（convert edge to point algorithm） that makes the model of this many postmen Chinese postmen problem apply to decision-making is given, and then, MDPMCA（multistep decision process model convert algorithm） is given to make this model meet the demand of the multistep decision process. KMDPA can be used to solve the problem. In the end,the validity and theory of this algorithm are proved.