A linear algorithm for optimal probabilistic planning

Wu, Lijun, Wang, Kai and Li, Jiajun (2015) A linear algorithm for optimal probabilistic planning. Journal of Computational Information Systems, 11 15: 5353-5362. doi:10.12733/jcis13602

Author Wu, Lijun
Wang, Kai
Li, Jiajun
Title A linear algorithm for optimal probabilistic planning
Journal name Journal of Computational Information Systems
ISSN 1553-9105
Publication date 2015-08-01
Sub-type Article (original research)
DOI 10.12733/jcis13602
Open Access Status Not Open Access
Volume 11
Issue 15
Start page 5353
End page 5362
Total pages 10
Place of publication Norwalk, CT, United States
Publisher Binary Information Press
Language eng
Subject 1710 Information Systems
1706 Computer Science Applications
Abstract The maximum probability path problem has been applied in many real fields. However, the problem of computing a path of maximum probability often is transformed into a shortest path problem so as to use suitably the existed shortest path algorithm such as Dijkstra's algorithm. We propose a new algorithm for maximum probability path problem, which is linear in size of a system and does not need to transform. The algorithm mainly exploits probability-first strategy, a probability ordered queue and some FIFO (First In First Out) queues. We prove our algorithm's soundness and completeness with respect to optimal probability problem, and take project application as an example to show our algorithm's application.
Keyword Maximum probability path
Probability-first strategy
Shortest path problem
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID 61073033
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2016 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 05 Jan 2016, 11:20:22 EST by System User on behalf of Learning and Research Services (UQ Library)