Partial Move A*
Cazenave, Tristan (2010), Partial Move A*, 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010 - proceedings, IEEE, p. 25-31
TypeCommunication / Conférence
Conference title22th International Conference on Tools with Artificial Intelligence
Book title22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010 - proceedings
MetadataShow full item record
Abstract (EN)Some shortest path problems that can be solved using the A* algorithm have a large branching factor due to the combination of multiple choices at each move. Multiple sequence alignment and multi-agent pathﬁnding are examples of such problems. If the search can be stopped after each choice instead of being stopped at each combination of choices, it takes much less memory and much less time. The goal of the paper is to show that Partial Move A* is much better than A* for these problems when the branching factor is large due to a large combination of choices at each move. When there is such a large combination of choices at each move, Partial Move A* can yield large memory gains and speedups over regular A*.
Subjects / KeywordsA*; Partial Move A*; shortest path problem
Showing items related by title and author.