Iterative-Deepening-A*: An Optimal Admissible Tree Search

Korf, Richard E.

Iterative-Deepening-A*: An Optimal Admissible Tree Search

Download BibTeX Cite

Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 1034-1035.

Abstract

A serious Iimitation of the A * algorithm is that in prac ti ce it requires space which is exponential in the so lu t ion cost. We propose an JteratJve-deepemng ex tension to A * which only requires linear space. The algori t hm JS admJssJble and expands the same number of nodes, asymptotically, as A* for exponent1al tree search es. This algorithm is the only known algonthm th at Js capable of finding optimal solutions to randomly gener ated instances of the Fifteen Puzzle within pra ctical r es ource Iimits.

Richard E. Korf. 1985. Iterative-Deepening-A*: An Optimal Admissible Tree Search. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85. IJCAI, 1034–1035. https://ijcai.org/proceedings/1985/208

@inproceedings{ijcai1985p208,
  title     = {Iterative-Deepening-A*: An Optimal Admissible Tree Search},
  author    = {Korf, Richard E.},
  booktitle = {Proceedings of the Ninth International Joint Conference on
               Artificial Intelligence, {IJCAI-85}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Aravind Joshi},
  pages     = {1034--1035},
  year      = {1985},
  note      = {Planning and Search},
  url       = {https://ijcai.org/proceedings/1985/208},
}

TY  - CPAPER
TI  - Iterative-Deepening-A*: An Optimal Admissible Tree Search
AU  - Korf, Richard E.
T2  - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1985
SP  - 1034
EP  - 1035
UR  - https://ijcai.org/proceedings/1985/208
ER  -