An Analysis of Consecutively Bounded Depth-First Search with Applications in Automated Deduction

1 Introduction

In this paper, we investigate the properties of conucutively bounded depth-firat 1earch. In this method, exhaustive depth-first search is repeatedly performed with increasing depth bounds of 1, 2, 3, and so on. The effect is similar to that of breadth-first search, but, instead of retaining the results at Ievel n- 1 for use in computing Ievel n, earlier results are recomputed. 2

Although this may appear to be a naive and costly search method, it is not necessarily so. lt is sometimes advantageaus to perform consecutively bounded depth-first search instead of the breadth-first search it imitates. One reason for this is that depth-first search requires much less memory.

Consecuti.vely bounded depth-first search can also make use of heuristic information, in cantrast to unbounded breadth- and depth-first search-the latter are uninformed search strategies that do not take into account heuristic estimates of the remain­ ing distance to a solution. Informed search strategies such as the A * algorithm use such heuristic information to order the

1 This research wu oupported by the Defenoe Advanced Research Projects Agency under Contract N00039-84-K-0078 with the Naval Electronic Sys· tems Command. The views and eonclu1ions contained in this document are those of the authon and should not be interpreted u representative of the official policie1, either expre11ed or implied, of the Defense Advanced Research Projects Agency or the United Stateo government. Approved for public releue. Diatribution unlimited.

2 We assume a buic familiarity with 1tandard breadth-flrst, depth-first, and

A · search strategieo (e.g., oee Ni111on 141).

An Analysis of Consecutively Bounded Depth-First Search with Applications in Automated Deduction

Mark E. Stickel and W. Mabry Tyson

Artificial Intelligence Center SRI International

Menlo Park, California 94025

search space. Consecutively bounded depth-first search docs not do that , but can usc an estimate of the minimum number of re­ maining steps to a solution to perform cutoffs if the estimate ex­ ceeds the number of Ievels left before the depth bound is reached. If the number of remaining Ievels is uniformly exceeded by these estimates by more than one Ievel, then one or more Ievels can be skipped when the next depth bound is set. As with the A * algo­ rithm, admissability- the guarantee of finding a shortest solution path first- is preserved provided the heuristic estimate never ex­ ceeds the actual number of remaining steps to a solution.

Another advantage of consecutively botmded dcpth-first search stems from the fact that, in some applications, depth­ first search can be implemented with much higher efficiency than breadth-first search; consecutively bounded depth-first search combines this elliciency with the completeness of breadth-first search. In these applications, the greater efficiency of depth­ first search more than compensates for the effort of recomputing earlier-level results in consecutively bounded depth-first search.

A specific instance of this is PROLOG-style automated deduc­ tion. PROLOG's use of depth-first search contributes significant ly to its performance. If depth-first search were not. used, more than one derived clause would have to be represent.ed simultaneously and variables would have more than a single value simultane­ ously, i.e., different values in different clauses. This would imply the need for a more complex and less efficient representation for variable bindings than the one PROLOG currently uses.

One of our interests is in adapting PROLOG implementation technology to the design of high-performance general automated­ deduction systems [6]. For generat deduction, PROLOG's depth­ first search is incomplete and of limited utility. But to adopt breadth-first search would result in losing the efficiency advan­ tages of PROLOG's representation for variable bindings. Per­ forming bounded depth-first search would preserve the depth­ first character of the search while allowing exhaustive searching of the space to a specified Ievei.

There is still the problern of selecting the depth bound. In an exponential search space, searching with a higher- than-necessary depth bound can waste an enormaus amount of effort before the solution is found. This is because the cost of searching Ievei n in an exponential search space is generally !arge compared with the cost of searching earlier Ievels.

But this also makes it practical to perform consecutively bounded depth-first search. The depth bound is set successively at 1, 2, 3, etc., until a solution is found . If a uniform brauehing factor bis assumed, this results in only about b~l times as many operations as are necessary for breadth-first search to the same depth.

Another potential application in automated deduction and logic programming is in systems like EQLOG [1]. EQLOG extends PROLOG by replacing the standard unification algorithm with an al gori thm based on narrowing that unifies terms in equational theories. Because the narrowing process is not necessarily finite, it may be necessary for completeness to interleave computation of unifiers by narrowing with the Horn-clause-resolution backtrack­ ing search. Here the use of consecutively bounded depth-first search would be beneficial both for its representational efliciency and for its low space consumption-the latter is particularly im­ portant because there may be a large number of unification at­ tempts that are simultaneously aetive.

Consecutively bounded depth-first search is similar to the tree-searching strategy of iterative deepening used in chess [5] . In iterat ive deepening, search is repeatedly performed with in­ creasing depth bounds until a time Iimit is reached. Insofar as these chess searches can be modeled by breadth-first seareh with a uniform brauehing faetor, our analysis reveals that iterative deepening seareh in chess is only marginally more expensive than a single seareh to the maximum depth.

Despite this use of eonsecutively bounded depth-first seareh in cbess and its obvious utility, it has surprisingly remained un­ analyzed and unargued for- until now. Our proposal of a PRO­ LOG technology theorem prover [6] included a deseription of this search strategy (which we implemented) and a very rough analy­ sis on which this work builds. 1\orf [2,3] has independently eome to similar conclusions on the value of this search strategy and has clone his own analysis that emphasizes its asymptotic optimality in space and time among brute-force searches and, with the use of cutoffs, its optimality among admissable best-first searches.

2 Consecutively Bounded Depth-First Search Versus Breadth-First Search

We now present a comparison of the the effort required to per­ form consecutively bounded depth-first search and breadth-first search. The analysis ignores the effeets of using heuristic infor­ mation in consecutively bounded depth-first seareh, which would yield even more favorable results for that strategy.

Worst-ease behavior for eonseeutively bounded depth-first search, as compared with breadth-first search, oeeurs when the brauehing faetor is 1, i.e., when no searching is required. In this ease, if the solution is found at depth n, the eost of breadth­ first search with uniform brauehing factor 1 is BFSt(n) = n , while the eost of eonseeutively bounded depth-first seareh is CBDFS!(n) = 1 + 2 + · ·· + n = n(n 2 +tl .

For larger brauehing faetors, eonsecutively bounded depth­ first search will be shown tobe the generally small eonstant faetor b~l times as expensive as breadth-first search (i.e., 6 extra effort). This is true regardless of whether consecutively bounded depth-first seareh is used to search exhaustively to some depth or only until the first solution is found.

2.1 Exhaustive Search

The number of operations B F Sb( n) performed in searching a space exhaustively wi th uniform brauehing factor b to depth n, using breadth-first seareh, is given by

We will also use the approximation

Beeause searehing a spaee exhaustively with breadth-first or depth-first search differs only in the order of Operations, the num­ ber of operations DFSb(n) for depth-first search is given by

The number of operations C B D F Sb( n) performed in search­ ing a spaee exhaustively with uniform brauehing factor b to depth n, using consecutively bounded depth-first search, i.e., searching exhaustively to depth 1, 2, . . . , n, is given by

Thus, the ratio of the eosts of searching exhaustively to depth n, using eonsecutively bounded depth-first search, compared with searehing to depth n by using breadth-first seareh can be approx­ imated by

2.2 Search to First Solution

Assurne that the there are no solutions below Ievel n and that the first solution is found at fraction r of the way through searehing Ievel n- e.g., r = 0.5 if half of the Ievel n operations have been clone when the first solution is found .

We now define the approximate number of operations BFSb(n, r) and C BDFSb(n, r) , eorresponding to BFSb(n) and C BDFSb(n) , performed in searching a space to the first solution found at point r on Ievel n:

Thus, the ratio of the costs of searching to the first solution at point r on Ievel n, using eonsceutively bounded depth-first seareh eompared with using breadth-first search, ean be approximated, by use of Equations (5) and (2) , by

2.3 Memory Requirements

An advantage of consecutively bounded depth-first search is that it needs only an amount of memory that is linear in the depth of the tree. When the seareh rout ine is at some node in thc t.ree, it needs to remernher only the node's anccstors ur, somet. inH'S for convenience, the node's and ancestor~' si hlings HS weil. Even in the latter case, the memory required is only bn nodes wherc b is the branching factor and n is the depth. For ordinary breadth­ first search, the memory required is O(bn), since each node in the tree at the current depth must be stored. Consequently, much less memory is needed for eonseeutively bounded depth­ first search.

3 Evenly Bounded Depth-First Search

At first it appears that consecutively bounded depth-first search wastes effort by redoing the same steps too often. In fact only l of thc effort is wasted, but for small branching factors , when the waste is greatest , the amount of wasted effort can be decreased by modifying the strategy.

Consider using even bounds (2, 4, . . . ) instead of consecutive bounds (1 , 2, ... ) when searching for the first solution.

If the solution occurs on one of the bounding Ievels (i .e., at an even depth) , evenly bounded depth-first search is a clear win­ ner. But if the solution occurs on another Ievel, it may be worse. Since we probably do not know the parity of the depth of the first solut ion any more than we know the depth itself, a comparison of evenly bounded with consecutively bounded depth-first search is difficult for any set ofproblems. One way to compare them would be to determine under what conditions the savings (when a solu­ t ion is found at an even depth) outweigh the extra effort (when the solution could have been found at the preceding odd depth) . For this analysis, we will assume that the solution that could have been found at the previous odd depth will still be the first solution found when searching to the next greater even depth. A contrary assumption would make evenly bounded depth-first search more favorable. We shall first compute the nurober of op­ erations for evenly bounded depth-first search when the solution is found at even or odd depths.

Similarly to Equation (4),

As a result of the even bounds,

Likewise, similarly to Equation (7) ,

and again

For solutions at even Ievels, the difference between finding the fi rst solution by consecutively bounded and evenly bounded depth-first search is

For solutions at odd Ievels,

lf the sum of the diffcrenccs is positive, then t.he addcd cf­ ficiency in dealing wi th problems whose lirst. solution is on an even Ievel outweighs any extra ovcrhead expended upon prob­ lems whose first solution is on an odd Ievel. lf that is so, evenly bounded depth-first search is clearly more efficicnt than conscc­ utively bounded depth-first search. Analysis reveals that evenly bounded depth-first search is always preferable for a braueh­ ing factor of 2 (or less), while consecut ively bounded depth- first search is preferable for a brauehing factor of 4 or more. For a branching factor of 3, the advant ages of find ing solu tions on even Ievels are approximately equal to the disadvantagcs of finding solutions on odd Ievels.

4 Conclusion

We have analyzed the behavior of consecutively bounded depth­ first search. This strategy is useful whenever a complete search strategy is needed, and either it is desirable to minimize memory requirements or depth-first search can be implemented partic­ ularly efficiently. Moreover, consecutively bounded depth-fi rst search, in contrast to the unbounded breadth- first search it al­ most emulates, can take advantage of heuristic est imates of the minimum nurober of steps remaining on a solution path to per­ form cutoffs if that nurober excceds the nurober of Ievels left be­ fore the depth bound is reached. Even if the possibil ity of such cutoffs is disregarded, we have found the pcrformance penalty re­ sulting from the use of consecutively boundcd depth-first search to be small when compared with breadth-first search- the for­ mer performs only 6 times as many operat ions as the latter, where b is the branching factor.