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

• 全文链接
• 请求原文

作   者：

费蓉;  崔杜武; 

作者机构：

西安理工大学计算机科学与工程学院; 

关键词：

最优路径;  最优性;  动态规划;  CPDPA算法; 

期刊名称：

计算机研究与发展

i s s n：

1000-1239

年卷期：

2005 年 42 卷 02 期

页   码：

294-299

摘   要：

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