Execution of logic programs by iterative-deepening A\(^*\) SLD-tree search (Q688625)

The author presents several complete search strategies that are superior to PROLOG's depth-first SLD search. His first version is depth-first iterative-deepening \(A^*\) (called \(\text{IDA}^*)\). \(\text{IDA}^*\) is improved by adding extrapolation rules. This version, \(\text{IDA}^*E\), decides in advance how many nodes ought to be expanded if no goal node is found during an iteration and then computes a bound on the evaluation function using a quadratic extrapolation polynomial. He obtains several estimates relating the number of nodes expanded by \(\text{IDA}^*E\) to the number expanded by \(A^*\) or depth-first. Moreover, he describes some pruning rules to reduce the size of the search tree. Finally, the author describes how one could combine iterative deepening \(A^*\) and depth-first and presents some experimental results.