Reducing reexpansions in iterative-deepening search by controlling cutoff bounds

Sarkar, U. K. ; Chakrabarti, P. P. ; Ghose, S. ; De Sarkar, S. C. (1991) Reducing reexpansions in iterative-deepening search by controlling cutoff bounds Artificial Intelligence, 50 (2). pp. 207-221. ISSN 0004-3702

Full text not available from this repository.

Official URL:

Related URL:


It is known that a best-first search algorithm like A* [5, 6] requires too much space (which often renders it unusable) and a depth-first search strategy does not guarantee an optimal cost solution. The iterative-deepening algorithm IDA* [4] achieves both space and cost optimality for a class of tree searching problems. However, for many other problems, it takes too much of computation time due to excessive reexpansion of nodes. This paper presents a modification of IDA* to an admissible iterative depth-first branch and bound algorithm IDA*_CR for trees which overcomes this drawback of IDA* and operates much faster using the same amount of storage. Algorithm IDA*_CRA, a bounded suboptimal cost variation of IDA*_CR is also presented in order to reduce the execution time still further. Results with the 0/1 Knapsack Problem, Traveling Salesman Problem, and the Flow Shop Scheduling Problem are shown.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Branch and Bound; Heuristic Search; A*; IDA*; Traveling Salesman Problem; 0/1 Knapsack Problem
ID Code:5911
Deposited On:19 Oct 2010 10:14
Last Modified:20 May 2011 09:51

Repository Staff Only: item control page