Bidirectional Search That Is Guaranteed to Meet in the Middle: Extended Version
作者： Nathan R. Sturtevant , Ariel Felner , Robert C. Holte , Guni Sharon
DOI: 10.7939/R3348GJ05
关键词:
摘要: We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to “meet in middle”, i.e. never expand a node beyond solution midpoint. also novel framework for comparing A*, brute-force search, identify conditions favoring each algorithm. Finally, we experimental results that support our theoretical analysis.
ualberta.ca
sci-hub.st 参考文章(30)
Richard E. Korf, Best-first frontier search with delayed duplicate detection national conference on artificial intelligence. pp. 650- 657 ,(2004)
Hermann Kaindl, Gerhard Kainz, Roland Steiner, Andreas Auer, Klaus Radda, Switching from Bidirectional to Unidirectional Search international joint conference on artificial intelligence. pp. 1178- 1183 ,(1999)
Jürgen Eckerle, An Optimal Bidirectional Search Algorithm KI '94 Proceedings of the 18th Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence. pp. 394- 394 ,(1994) , 10.1007/3-540-58467-6_37
Hermann Kaindl, Andreas Auer, A case study of revisiting best-first vs. depth-first search european conference on artificial intelligence. pp. 141- 145 ,(2004)
A. Kazi, Shamsul Arefin, B. Aloke, Kumar Saha, A New Approach of Iterative Deepening Bi- Directional Heuristic Front-to-Front Algorithm (IDBHFFA) ,(2010)
H. Kaindl, G. Kainz, Bidirectional heuristic search reconsidered Journal of Artificial Intelligence Research. ,vol. 7, pp. 283- 317 ,(1997) , 10.1613/JAIR.460
Carlos Linares López, Andreas Junghanns, Perimeter Search Performance annual conference on computers. pp. 345- 359 ,(2002) , 10.1007/978-3-540-40031-8_23
Ira Sheldon Pohl, Bi-directional and heuristic search in path problems Stanford University. ,(1969)
Judea Pearl, Heuristics : intelligent search strategies for computer problem solving ,(1984)
Malte Helmert, Gabriele Röger, How good is almost perfect national conference on artificial intelligence. pp. 944- 949 ,(2008)