Reducing reexpansions in iterative-deepening search by controlling cutoff bounds

Abstract

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.