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

摘要：

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

关键词：最短路径树、马尔可夫决策过程、有限阶段模型、反转图、分布式并行计算

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

资助基金：美国国家科学基金NSF EIA-0103709;山东省科技攻关项目2005GG1101001

在线出版日期：2007-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：266-270