Premium
Depth‐First Branch‐and‐Bound versus Depth‐Bounded IDA: New Results
Author(s) -
Prieditis Armand E.
Publication year - 1998
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00060
Subject(s) - pruning , iterative deepening depth first search , heuristic , bounded function , computation , depth first search , algorithm , search tree , path (computing) , mathematics , computer science , upper and lower bounds , node (physics) , incremental heuristic search , search algorithm , mathematical optimization , beam search , mathematical analysis , structural engineering , agronomy , biology , programming language , engineering
In a real‐time task an action must be executed given limited computation. One approach to limited computation is to search a tree of possible action sequences to a fixed depth and then execute an action with the lowest associated backed‐up cost. The standard algorithm for such a search is Depth‐First Branch‐and‐Bound (DFBB), also known in the Artificial Intelligence literature as Minimin with Alpha Pruning . This article shows that a depth‐bounded extension of a popular iterative algorithm called IDA has a surprisingly large range of search trees on which it outperforms DFBB—something previous analytical results do not predict. We prove that the extended algorithm, which we call DIDA , is correct, is guaranteed to terminate, and is asymptotically (i.e., on its last iteration) as efficient as DFBB—assuming a consistent heuristic is used. We also prove that both algorithms are guaranteed not to decrease their accuracy with a deeper search, assuming a consistent heuristic. Because accuracy is generally correlated with decision quality, the time saved by visiting fewer states translates to deeper searches which translates to better decisions. Results from random search trees show that DIDA is most efficient when the path cost + leaf node heuristic value is distributed with low variance; as branching factor increases, the range for which DIDA is more efficient also increases. Results with Eight, Fifteen, Twenty‐four, and Ninety‐nine Puzzle implementations of both algorithms—all domains with low variance of path cost + leaf node heuristic value—show that DIDA significantly outperforms DFBB.