Reducing reexpansions in iterative-deepening search by controlling cutoff bounds

It is known that a best-first search algorithm like A* 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* 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, Travelling Salesman Problem, and the Flow Shop Scheduling Problem are shown.