The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Generalized best-first search strategies and the optimality of A*
Open accessAbstract
This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h . It is shown that several known properties of A* retain their form (with the minmax of f playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm for achieving it. The main results of this paper relate to the class of algorithms that, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., h ≤ h *). On this class, A* is shown to be not optimal and it is also shown that no optimal algorithm exists, but if the performance tests are confirmed to cases in which the estimates are also consistent, then A* is indeed optimal. Additionally, A* is also shown to be optimal over a subset of the latter class containing all best-first algorithms that are guided by path-dependent evaluation functions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Principles of Artificial Intelligence
Nilsson, N. J. (1982) · doi:10.1007/978-3-662-09438-9 · Cited by 3,457
Branch-and-Bound Methods: A Survey
Lawler, E. L., & Wood, D. E. (1966) · Operations Research · doi:10.1287/opre.14.4.699 · Cited by 1,997
The Handbook of Artificial Intelligence
(1982) · Elsevier eBooks · doi:10.1016/c2013-0-07691-8 · Cited by 1,695
Problem-Solving Methods in Artificial Intelligence
Nilsson, N. J. (1971) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,607
Heuristics: Intelligent Search Strategies for Computer Problem Solving
(1986) · Telematics and Informatics · doi:10.1016/s0736-5853(86)80081-8 · Cited by 1,072
The Art and Theory of Dynamic Programming
(1977) · Mathematics in Science and Engineering · doi:10.1016/s0076-5392(08)x6068-0 · Cited by 474
Review of "Problem-Solving Methods in Artificial Intelligence by Nils J. Nilsson", McGraw-Hill Pub.
Bledsoe, W. W. (1971) · ACM SIGART Bulletin · doi:10.1145/1056578.1056583 · Cited by 356
Studies in Semi-Admissible Heuristics
Pearl, J., & Kim, J. H. (1982) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1982.4767270 · Cited by 205
Self-citationOn the complexity of admissible search algorithms
Martelli, A. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90002-9 · Cited by 178
Cited by
Conflict-based search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.006 · Cited by 1,242
A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance
Goerzen, C., Kong, Z., & Mettler, B. (2010) · Journal of Intelligent and Robotic Systems · doi:10.1007/s10846-009-9383-1 · Cited by 779
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning
Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016) · Discrete Optimization · doi:10.1016/j.disopt.2016.01.005 · Cited by 563
Artificial intelligence: foundations of computational agents
(2010) · Choice Reviews Online · doi:10.5860/choice.48-2130 · Cited by 415
Neo: a learned query optimizer
Marcus, R., Negi, P., Mao, H., Zhang, C., Alizadeh, M., Kraska, T., Papaemmanouil, O., & Tatbul, N. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3342263.3342644 · Cited by 389
LAO∗: A heuristic search algorithm that finds solutions with loops
Hansen, E. A., & Zilberstein, S. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00106-0 · Cited by 388
Path planning and obstacle avoidance for AUV: A review
Cheng, C., Sha, Q., He, B., & Li, G. (2021) · Ocean Engineering · doi:10.1016/j.oceaneng.2021.109355 · Cited by 378
Dynamic programming approaches for the traveling salesman problem with drone
Bouman, P., Agatz, N., & Schmidt, M. (2018) · Networks · doi:10.1002/net.21864 · Cited by 360
Developing serious games for cultural heritage: a state-of-the-art review
Anderson, E. F., McLoughlin, L., Liarokapis, F., Peters, C., Petridis, P., & de Freitas, S. (2010) · Virtual Reality · doi:10.1007/s10055-010-0177-3 · Cited by 357
An agent-based model for risk-based flood incident management
Dawson, R. J., Peppe, R., & Wang, M. (2011) · Natural Hazards · doi:10.1007/s11069-011-9745-4 · Cited by 334
Hajek, P., & Henriques, R. (2017) · Knowledge-Based Systems · doi:10.1016/j.knosys.2017.05.001 · Cited by 334
Juan, Y.-K., Gao, P., & Wang, J. (2010) · Energy and Buildings · doi:10.1016/j.enbuild.2009.09.006 · Cited by 332
The increasing cost tree search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2013) · Artificial Intelligence · doi:10.1016/j.artint.2012.11.006 · Cited by 323
Linear-space best-first search
Korf, R. E. (1993) · Artificial Intelligence · doi:10.1016/0004-3702(93)90045-d · Cited by 305
Diagnosis of Chronic Kidney Disease Based on Support Vector Machine by Feature Selection Methods
Polat, H., Danaei Mehr, H., & Cetin, A. (2017) · Journal of Medical Systems · doi:10.1007/s10916-017-0703-x · Cited by 297
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges
Abraham, D. J., Blum, A., & Sandholm, T. (2007) · Proceedings of the 8th ACM conference on Electronic commerce · doi:10.1145/1250910.1250954 · Cited by 280
Rich Vehicle Routing Problem: Survey
Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A. A. (2015) · ACM Computing Surveys · doi:10.1145/2666003 · Cited by 280
A comprehensive review of current local features for computer vision
Li, J., & Allinson, N. M. (2008) · Neurocomputing · doi:10.1016/j.neucom.2007.11.032 · Cited by 280
Hansen, E. A., & Zhou, R. (2007) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2096 · Cited by 259
Anytime search in dynamic graphs
Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., & Thrun, S. (2008) · Artificial Intelligence · doi:10.1016/j.artint.2007.11.009 · Cited by 254
SWAN: System for Wearable Audio Navigation
Wilson, J., Walker, B. N., Lindsay, J., Cambias, C., & Dellaert, F. (2007) · 2007 11th IEEE International Symposium on Wearable Computers · doi:10.1109/iswc.2007.4373786 · Cited by 200
Metadata
- Authors
- Dechter, R., & Pearl, J.
- Venue
- Journal of the ACM
- Published
- 1985-07
- Volume
- 32
- Issue
- 3
- Pages
- 505-536
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2134634502
- Cited by
- 1,071
- References
- 17
- FWCI
- 2.56
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.