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

• 作者: 崔杜武 费蓉
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 动态规划 最优路径 CPDPA算法 最优性
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 算法理论
• 页码范围: 294-299
• 页数: 6页
• 分类号: TP312|TP18
• 字数: 5171字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔杜武	西安理工大学计算机科学与工程学院	136	1718	19.0	35.0
2	费蓉	西安理工大学计算机科学与工程学院	21	117	6.0	10.0