Delayed Duplicate Detection: Extended Abstract

Korf, Richard E.

Delayed Duplicate Detection: Extended Abstract

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1539-1540.

Abstract

Best-first search is limited by the memory needed to store nodes in order to detect duplicates. Disks can greatly expand the amount of storage available, but randomly accessing a disk is impractical. Rather than checking newlyge nerated nodes as soon as they are generated, we append them to a disk fil e, then sort the file, and finally scan the sorted file in one pass to detect and remove duplicate nodes. This also speeds up such searches that fit entirely in memory, by improving cache performance. We implement this idea for breadth-first search, performing the first complete searches of the 2 x 7 sliding-tile puzzle, and the 18-disk, 4-peg Towers of Hanoi puzzle.

Richard E. Korf. 2003. Delayed Duplicate Detection: Extended Abstract. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1539–1540. https://ijcai.org/proceedings/2003/265

@inproceedings{ijcai2003p265,
  title     = {Delayed Duplicate Detection: Extended Abstract},
  author    = {Korf, Richard E.},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {1539--1540},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/265},
}

TY  - CPAPER
TI  - Delayed Duplicate Detection: Extended Abstract
AU  - Korf, Richard E.
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 1539
EP  - 1540
UR  - https://ijcai.org/proceedings/2003/265
ER  -