最短路径树的马尔可夫有限阶段决策算法

• 作者: Edwin H.-M.Sha 刘甜甜 贾智平
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 最短路径树 马尔可夫决策过程 有限阶段模型 反转图 分布式并行计算
• 年，卷（期）: 2007,（8）
• 所属期刊栏目: 软件工程及其他
• 页码范围: 266-270
• 页数: 5页
• 分类号: TP3
• 字数: 8116字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2007.08.074

摘要

本文从决策的角度出发,结合马尔可夫决策过程理论,建立了计算最短路径树(SPT)的有限阶段决策模型.引入一个辅助图:反转图,结合它修改了模型的理论求解算法,提出了SPT反转递归迭代算法,并证明了算法的正确性.在此基础上,又提出了不使用反转图的改进模型和算法.算法的时间和空间复杂度分析表明:本文提出的算法具有分布式并行计算的特点,可以均衡各节点的工作负载,降低时间和空间复杂度,并可以有效防止环路的产生,因此可以有效应用于资源匮乏的嵌入式互连环境和对等网络环境中.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贾智平	山东大学计算机科学与技术学院	58	1109	15.0	32.0
2	刘甜甜	山东大学计算机科学与技术学院	24	96	6.0	8.0