Bidirectional search that is guaranteed to meet in the middle
作者： Nathan R. Sturtevant , Ariel Felner , Robert C. Holte , Guni Sharon
DOI:
关键词:
摘要: 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 
acm.org 参考文章(22)
Richard E. Korf, Best-first frontier search with delayed duplicate detection national conference on artificial intelligence. pp. 650- 657 ,(2004)
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
Ira Sheldon Pohl, Bi-directional and heuristic search in path problems Stanford University. ,(1969)
Malte Helmert, Gabriele Röger, How good is almost perfect national conference on artificial intelligence. pp. 944- 949 ,(2008)
Richard E Korf, Joseph K Barker, Limitations of front-to-end bidirectional heuristic search national conference on artificial intelligence. pp. 1086- 1092 ,(2015)
T. A. J. Nicholson, Finding the Shortest Route between Two Points in a Network The Computer Journal. ,vol. 9, pp. 275- 280 ,(1966) , 10.1093/COMJNL/9.3.275
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge, The Diameter of the Rubik's Cube Group Is Twenty SIAM Journal on Discrete Mathematics. ,vol. 27, pp. 1082- 1105 ,(2013) , 10.1137/120867366