%0 Journal Article
%T Markov Finite Horizon Decision Algorithm of Shortest Path Tree<br>最短路径树的马尔可夫有限阶段决策算法
%A LIU Tian-Tian
%A JIA Zhi-Ping
%A Edwin H-MSha
%A <br>刘甜甜
%A 贾智平
%A Edwin H.-M.Sha
%J 计算机科学
%D 2007
%I 
%X The idea of decision-making is focused on in this paper.Combining with Markov decision process theory,a SPT finite horizon decision model is established.A new auxiliary graph:Reverse Graph is introduced,combining with which the theoretical solving algorithm of the model is modified,a SPT reverse recursion iterative algorithms is proposed and its validity is proved.Base on these,an improved model and algorithm without Reverse Graph are also put forward,and time and space complexity of the two algorithms are analyzed.The theoretical analysis results show that these algorithms are characteristic by distributed parallel computation,which can balance workload between all nodes,reduce time and space complexity,and is loop-free.So it can be effectively applied in the embedded connection environment with limited resources and the peer-to-peer network environment.
%K Shortest path tree
%K Markov decision process
%K Finite horizon model
%K Reverse graph
%K Distributed parallel computation<br>最短路径树
%K 马尔可夫决策过程
%K 有限阶段模型
%K 反转图
%K 分布式并行计算
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=1E8759907DE654782720A00179DA303E&yid=A732AF04DDA03BB3&vid=339D79302DF62549&iid=5D311CA918CA9A03&sid=4FE459D71E3BF8EB&eid=B7BFA4B351E4C682&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=13