ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm
Abstract
This paper describes a new admissible tree search algorithm called Iterative Threshold Search (ITS). ITS can be viewed as a much-simplified version of MA* [1], and a generalized version of MREC [12]. We also present the following results: 1. Every node generated by ITS is also generated by IDA*, even if ITS is given no more memory than IDA*. In addition, there are trees on which ITS generates O(N) nodes in comparison to O(N log N) nodes generated by IDA*, where N is the number of nodes eligible for generation by A*. 2. Experimental tests show that if the node-generation time is high (as in most practical problems), ITS can provide significant savings in both number of node generations and running time. Our experimental results also suggest that in the average case both IDA* and ITS are asymptotically optimal on the traveling salesman problem. Introduction Although A* is usually very efficient in terms of number of node expansions [2], it requires an exponential amount of memory, and...
Cite
Text
Ghosh et al. "ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm." AAAI Conference on Artificial Intelligence, 1994.Markdown
[Ghosh et al. "ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm." AAAI Conference on Artificial Intelligence, 1994.](https://mlanthology.org/aaai/1994/ghosh1994aaai-efficient/)BibTeX
@inproceedings{ghosh1994aaai-efficient,
title = {{ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm}},
author = {Ghosh, Subrata and Mahanti, Ambuj and Nau, Dana S.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1994},
pages = {1353-1358},
url = {https://mlanthology.org/aaai/1994/ghosh1994aaai-efficient/}
}