摘要: Many studies in heuristic search suggest that the accuracy of used has a positive impact on improving performance search. In another direction, historical research perceives algorithms, such as A* and IDA*, can be improved by requiring heuristics to consistent – property satisfied any perfect heuristic. However, few recent show inconsistent also achieve large improvement these algorithms. These results raise natural question: which heuristics, or consistency/inconsistency, should we focus when building heuristics?
springer.com
sci-hub.st 参考文章(20)
Richard E. Korf, Iterative-deepening-A: an optimal admissible tree search international joint conference on artificial intelligence. pp. 1034- 1036 ,(1985)
Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer, Dual lookups in pattern databases international joint conference on artificial intelligence. pp. 103- 108 ,(2005)
Richard E. Korf, Recent Progress in the Design and Analysis of Admissible Heuristic Functions symposium on abstraction reformulation and approximation. pp. 45- 55 ,(2000) , 10.1007/3-540-44914-0_3
Hang Dinh, Hieu Dinh, Laurent Michel, Russell, Alexander, The time complexity of A * with approximate heuristics on multiple-solution search spaces Journal of Artificial Intelligence Research. ,vol. 45, pp. 685- 729 ,(2012) , 10.1613/JAIR.3779
Malte Helmert, Gabriele Röger, How good is almost perfect national conference on artificial intelligence. pp. 944- 949 ,(2008)
Nathan R. Sturtevant, Ariel Felner, Robert Holte, Zhifu Zhang, Jonathan Schaeffer, A* search with inconsistent heuristics international joint conference on artificial intelligence. pp. 634- 639 ,(2009)
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
Nam Huyn, Rina Dechter, Judea Pearl, Probabilistic analysis of the complexity of A Artificial Intelligence. ,vol. 15, pp. 241- 254 ,(1980) , 10.1016/0004-3702(80)90045-4
Oscar H. Ibarra, Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems Journal of the ACM. ,vol. 22, pp. 463- 468 ,(1975) , 10.1145/321906.321909
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