摘要: We introduce a model for predicting the performance of IDA* using pattern database heuristics, as function branching factor problem, solution depth, and size databases. While it is known that larger database, more efficient search, we provide quantitative analysis this relationship. In particular, show single goal state, number nodes expanded by fraction (logb s + 1)/s brute-force where b factor, database. also taking maximum at least two databases, node expansions decreases linearly with compared to search. compare our theoretical predictions empirical data on Rubik's Cube. Our conservative, overestimates actual expansions.
aaaipress.org 参考文章(13)
Richard E. Korf, Heath Hohwald, Ignacio Thayer, Comparing best-first search and dynamic programming for optimal multiple sequence alignment international joint conference on artificial intelligence. pp. 1239- 1245 ,(2003)
A. Felner, R. Meshulam, R. C. Holte, David Furcy, Jack Newton, Multiple pattern databases international conference on automated planning and scheduling. pp. 122- 131 ,(2004)
Robert C. Holte, István T. Hernádvölgyi, A space-time tradeoff for memory-based heuristics national conference on artificial intelligence. pp. 704- 709 ,(1999)
Stefan Edelkamp, Planning with Pattern Databases Sixth European Conference on Planning. ,(2014)
Richard E. Korf, Ariel Felner, Recent progress in heuristic search: a case study of the four-peg towers of Hanoi problem international joint conference on artificial intelligence. pp. 2324- 2329 ,(2007)
Richard E. Korf, Ariel Felner, Disjoint pattern database heuristics Artificial Intelligence. ,vol. 134, pp. 9- 22 ,(2002) , 10.1016/S0004-3702(01)00092-3
Peter Hart, Nils Nilsson, Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Transactions on Systems Science and Cybernetics. ,vol. 4, pp. 100- 107 ,(1968) , 10.1109/TSSC.1968.300136
Richard E. Korf, Michael Reid, Stefan Edelkamp, Time complexity of iterative-deepening-A Artificial Intelligence. ,vol. 129, pp. 199- 218 ,(2001) , 10.1016/S0004-3702(01)00094-7
Richard E. Korf, Michael Reid, Complexity analysis admissible heuristic search national conference on artificial intelligence. pp. 305- 310 ,(1998)
Robert C. Holte, Ariel Felner, Jack Newton, Ram Meshulam, David Furcy, Maximizing over multiple pattern databases speeds up heuristic search Artificial Intelligence. ,vol. 170, pp. 1123- 1136 ,(2006) , 10.1016/J.ARTINT.2006.09.002