An Expected-Cost Analysis of Backtracking and Non-Backtracking Algorithms

1 INTRODUCTION

Many algorithms considered in operations research, com­ puter science and artificial intelligence may be repre­ sented as searches or partial searches through rooted trees. Such algorithms typically involve backtracking but try to minimize the time spent doing so (e.g. [Bit­ ner and Reingold, 1975; Brown and P. W. Purdom, 1981; Brown and P. W. Purdom, 1982; Dechter , 1990; Haralick and Elliott, 1980; Karp, 1976; Knuth, 1975; Nudel, 1983; P. W. Purdom, 1983; Stone and Stone, 1986]). Indeed for some problems it may be best to avoid backtracking [de Kleer, 1984] .

The paper extends work of [Karp and Pearl, 1983], and gives a probabilistic analysis of backtracking and non-backtracking search algorithms in certain trees with random branch costs. We thus cast some light on the question of when to backtrack: it seems that backtrack­ ing is valuable just for problems with "dead-ends" (or G.M.A. Provan

Department of Computer and Information Science University of Pennsylvania

Philadelphia PA 19104-6389 USA

email: provan@cis.upenn.edu

outcomes with prohibitively high costs).

Let us review briefly the model and results of Karp and Pearl [1983]. They consider an infinite search tree in which each node has exactly two sons. The branches have independent (0, I)-valued random costs X, with p = P(X = 0). 1 The problem is to find an optimal (cheapest) or nearly optimal path from the root to a node at depth n.

The problem changes nature depending on whether the expected number 2p of zero-cost branches leaving a node is > 1, = 1 or < 1. When 2p > 1 a sim­ ple uniform cost breadth-first search algorithm Al finds an optimal solution in expected time O(n); and when 2p = 1 this algorithm takes expected time O(n 2 ). When 2p < 1 any algorithm that is guaranteed to find a solu­ tion within a constant factor of optimal must take expo­ nential expected time. However, in this case a "bounded­ lookahead plus partial backtrack" algorithm A2 usually finds a solution close to optimal in linear expected time. This successful performance of the backtracking algo­ rithm A2 for the difficult case when 2p < 1 seems to suggest that similar backtrack-based heuristics should be of more general use for attacking N P-hard problems.

This paper shows that a simple non-backtracking bounded-lookahead algorithm A3 performs as success­ fully as the backtracking algorithm A2, on the basis of this search model. Similar comments hold if we allow more general finite random costs on the branches.

However, there is a qualitative difference if we allow nodes to have no sons (or allow branches to have infinite costs) so that there are "dead-ends". We extend Karp and Pearl's work by considering search in random trees generated by a branching process, where the branches have independent random finite costs X. (This model includes the case of infinite costs-nodes would just pro­ duce fewer sons). In this extended model, let m be the mean number of sons of a node, let p0 be the probability that a node has no sons, and as before let p = P(X = 0) .

Our results concerning algorithms Al and A2 are nat­ ural extensions of Karp and Pearl's results. Thus the uniform cost algorithm Al finds an optimal solution in linear expected time if mp > 1 and in quadratic expected time if mp = 1. If mp < 1 then any algorithm with a constant performance guarantee must take exponential expected time, but the backtracking algorithm A2 finds a nearly optimal solution in linear expected time.

1 We have swapped p and 1 - p from the original paper.

However, the performance of the non-backtracking al. gorithm A3 depends critically on the parameter po . Sup­ pose that mp < 1, so that optimal search is hard. If p0 = 0, so that as in the Karp and Pearl model there are no dead-ends, then algorithm A3 usually finds a nearly optimal solution in linear expected time; that is, it per­ forms as successfully as the backtracking algorithm A2. However, if Po > 0 then algorithm A2 usually fails to find a solution. Thus our model suggests that backtracking becomes attractive when there is the possibility of dead­ ends.

In the next section we give details concerning the search model and the algorithms A1, A2 and A3, and then in section 3 we present our results . Section 4 briefly discusses the effect of noise on the algorithmic perfor­ mance. In section 5 we make a few comments on proofs.

2 MODEL AND ALGORITHMS

We suppose that the search tree is the family tree of a branching process. For an introduction to the theory of such processes see for example (Harris, 1963; Athreya and Ney, 1972; Karp and Pearl, 1983] . Thus the search tree has a root node, at depth 0. Each node at depth n independently produces and is joined to a random num­ ber Z of sons at depth ( n + 1). We shall assume that the mean number m of sons produced satisfies 1 < m < oo. Thus the expected number of nodes at depth n is mn and grows exponentially with n.

The Karp and Pearl model is the special case when each node always has exactly two sons. On the other hand our search model here is a special case of the more complicated model considered in (McDiarmid, 1990], namely an age-dependent branching process of Crump­ Mode type (Crump and Mode, 1968] . For such a model the implications concerning backtracking are just the same.

Let q denote the extinction probability for the branch­ ing process, that is the probability that the search tree is finite. Since m > 1 it follows that q < 1. Let Po be the probability a node has no sons. Clearly q > 0 if and only if Po > 0, and these conditions correspond to the existence of "dead-ends" in the search tree.

We suppose that the branches have independent non­ negative random costs X with finite mean. A simple translation allows us to assume without loss of generality that small costs can occur; that is, for any 6 > 0 we have P(X < 6) > 0. The distinction between zero and non­ zero costs turns out to be important. We let p = P(X = 0) 2: 0.

The co.st of a path is the sum of its branch costs. We want to find an optimal (cheapest) or nearly optimal path from the root to a node at depth n, for large n. Let c~ denote the random optimal cost of such a path, where C~ = oo if there is no such path. Thus P( C~ = oo) - q as n - oo. The interesting case is when the search tree is infinite, and we shall usually condition on this happening, so that almost surely c~ is finite.

We shall discuss the performance of three algorithms, A1 ,A2 and A3, the first two of which are taken from

(Karp and Pearl, 1983] . Algorithm Al is a uniform cost breadth-first search algorithm and will be analyzed for the cases mp > 1 and mp = 1, when there are many zero-cost branches and search is easy. Algorithm A2 is a hybrid of local and global depth-first search strategies and will be analyzed for mp < 1. Algorithm A3 consists of repeated local optimal searches, and will be analyzed also for mp < 1. Note that A1 is an exact algorithm, whereas A2 and A3 are approximation algorithms.

For each algorithm Aj, we let the random cost of the solution found be c:j (= 00 if no solution is found) , and the random time taken be r:i . We measure time by the number of nodes of the search tree encountered.

The three algorithms are as follows :

Algorithm A1: At each step, expand the leftmost node among those frontiers nodes of minimum cost. The algorithm halts when it tries to expand a node at depth n. That node then corresponds to an optimal solution.

Algorithm A2: Algorithm A2 has three parameters: d, L, and a. An (a, £)-regular path is a path which con­ sist of segments each of length L and cost at most o:L (except that the last segment may have length < L) . A2 conducts a depth-first search to find an (a, £)-regular path from a depth d node to a depth n node. In other words, A2 is a depth-first strategy which stops at regular intervals of L levels to appraise its progress. If the cost increase from the last appraisal is at most aL, the search continues; if that cost increase is above aL, the current node is irrevocably pruned, the program backtracks to a higher level, and the search resumes. If it succeeds in reaching depth n , A2 returns the corresponding path as a solution: if it fails, the search is repeated from another depth d node. If all the nodes at depth d fail to root an (a, L )-regular path to a depth n node, A2 terminates with failure .

Algorithm A3: The simple bounded-lookahead or "horizon" heunstlc is a staged-search algorithm which avoids backtracking. It has one parameter L . Starting at the root it finds an optimal path to a node at depth L, makes that node the new starting point and repeats. If L is a constant clearly A3 takes linear expected time.

3 RESULTS

We summarize our results in six theorems. Theorem 1 concerns the region mp > 1, theorem 2 concerns mp = 1 and theorems 3 - 6 concern mp < 1. When mp 2: 1, there are many zero costs, and the main distinction is between zero and non-zero costs.

Theorem 1 If mp > 1 then:

(a) conditional on non-extinction, the random variable

is finite almost surely, and indeed E[C*] is finite; and (b) the time r: 1 taken by algorithm A 1 satisfies

Thus, if the search tree is infinite, the optimal cost C~ remains bounded as n -+ oo, and algorithm A 1 finds an optimal path in linear expected time.

By restricting ourselves to 0,1 costs and uniform r-ary trees (so that each node has r sons) we may obtain a tighter result than in part (a) above, namely

The case r = 2 is a slight improvement on theorem 3.1 of Karp and Pearl [1983], and our proof(given below) is simpler and easier to generalise.

Next we consider the critical case mp = 1. It is con­ venient to make some simplifying assumptions on the typical random family size Z and cost X. We assume roughly that Z is not too big, and that the cost 0, which occurs with probability p, is "isolated", i.e. for some l > 0, P(X < l) = 0.

Theorem 2 Let mp = 1:

(a) If E[Z 2 +6] < oo for some 8 > 0,

then, conditional on non-extinction

(b) If E[Z 2 ] < oo then the time r: 1 taken by algo­ rithm A1 satisfies

Part (a) shows that if the optimal cost C~ is finite then it is usually close to log 2 log 2 n. This result _is a special case of theorem 2 of [Bramson, 1978): see also theorem 3.2 of [Karp and Pearl, 1983). Part (b) states that the algorithm A1 finds an optimal solution in quadratic ex­ pected time.

Our main interest is in the case mp < 1, when we cannot quickly find optimal solutions and thus it is of interest to analyze heuristic approximation methods.

Theorem 3 If mp < 1, then any algorithm that is guaranteed to find a solution within a constant factor of optimal must take exponential average time.

Theorem 4 Let mp < 1. For a 2: 0 let

Then there is a unique solution a· to the equation p(a) = 1/m; a· > 0 and conditional on non-extinction,

almost surely and in mean.

Thus if the optimal cost C~ is finite then it is usually close to a· n. For discussion concerning this result see [Hammersley, 1974; Kingman, 1975).

Theorem 5 Let mp < 1, and consider the random cost c: 2 yielded by the "bounded lookahead plus par­ tial backtrack" algorithm A2. For any l > 0 there are parameters d, a, L such that algorithm A2 runs in linear expected time, and almost surely

Thus algorithm A2 usually finds a nearly optimal so­ lution (whether dead-ends can occur or not). This seems to be very successful performance, but in one sense it is not. For given any sensible parameters there will be a positive probability of failing to produce a solution (even when Po = 0 so that there are no dead-ends), and thus of course E[C: 2 J = oo.

However, returning "failure" (as in Karp and Pearl's algorithm A2) rather than a _path of greater than near­ optimal cost may possibly be too extreme. Failure of A2 to find a near-optimal solution can be easily avoided by adding a suitable "second phase" if the present algorithm fails . A possible second phase could be a depth-first search for a root-leaf path (ignoring costs) .

Theorem 6 Let mp < 1, and consider the random cost c: 3 yielded by the bounded lookahead but non­ backtracking algorithm A3:

(a) If Po = 0 then for any f: > 0 there is a (constant) parameter L such that the algorithm A3 runs in linear expected time; and almost surely

and further

• (b) If Po > 0, and if the lookahead parameter L = o( n) (as is only reasonable) then almost surely

Part (a) above shows that if no dead-ends can occur then the simple non-backtracking heuristic A3 usually finds a nearly optimal solution and does so quickly. Part (b) show that A3 is hopeless if dead-ends can occur. Fur­ ther, suppose that L = O(log n) so that each stage can be performed in polynomial average time. Then even if we consider a polynomial number of different start­ ing points as with algorithm A2, still almost surely each search will fail if n is sufficiently large. This will follow from the proof of theorem 6.

4 EFFECTS OF READING ERRORS

In this section we discuss briefly the interesting effect of noise (i .e. reading errors) in the basic Karp and Pearl model. Suppose that the algorithm A1 may make oc­ casional independent random reading errors. Thus , for the case of (0, 1 )-costs, there is a probability 8o ~ 0 that a 0-cost is read as a 1, and a probability 81 ~ 0 that a 1-cost is read as a 0; and so the probability that a 0 is read is:

It is easy to see that if 8o and 81 are small then there will be a correspondingly small change in ~ times the expected solution value obtained by an error-prone al­ gorithm A1 (compared with the value obtained by an error-free algorithm A1).

However, near the critical value p = ~ there may be a dramatic change in the expected running time. If p is just greater than ~, small reading errors could make p < ~ . 2 Then although an error-free algorithm (A1) runs in linear expected time, an error-prone version takes ex­ ponential expected time. Conversely, if p is iust less than ~, small reading errors could make p > 2 . Then although an error-free algorithm A1 takes exponential expected time, an error-prone algorithm A1 runs in lin­ ear expected time. Thus although the optimal value is robust with respect to reading errors, the time taken by algorithm A1 to compute the optimal cost is certainly not robust when p is near ~.

2 Recall that pis the probability that a random cost equals

0.

5 COMMENT ON PROOFS

This section presents the following two proofs: (1) in­ equality 1, which has appeared before only in [Provan, 1985]; and (2) theorem 6, a proof of the performance of the simple bounded-lookahead algorithm A3-this the­ orem is not like anything from [Karp and Pearl, 1983], and it is also quick and easy to prove. Theorems 1-6 can be deduced from the corresponding results in (McDi­ armid, 1990] by specialising to the model discussed here and using standard truncation arguments. The proofs of theorems 1-5 can follow roughly similar lines to the proofs of the corresponding results in Karp and Pearl (1983].

Proof of inequality 1: Consider a branching process in which the number of sons of an individual has the bino­ mial distribution with parameters r and p. Let q be the extinction probability. Then

since if c~ > k then each of the rk subtrees rooted at the nodes at depth k must fail to have an infinite path of zero-cost branches. We shall show that (for rp > 1) we have

and then inequality 1 will follow. Using standard branch­ ing processes theory, q is the least positive root s of f(s) = s, where the generating function f(s) = (1p + ps t . Since f is convex it suffices to demonstrate that

But

and so this is equivalent to showing that

To do this, introduce

Finally, put y = x to obtain, as required,

• (a) We have already noted that for any constant looka­ head L the algorithm A3 runs in linear expected time. By theorem 5,

Let f: > 0 and choose L so that

Now C~ 3 is at most the sum of r'[l independent random variables each distributed like C£. Hence, by the strong law of large numbers, almost surely

But again by theorem 4, almost surely:

and part (a) of theorem 6 now follows. 3

• (b) To prove part (b) we need only observe that

6 CONCLUSIONS

This paper has studied the performance of both back­ tracking and non-backtracking tree search algorithms in finding a least-cost root-leaf path in random trees with random non-negative costs. The investigations extend the work of Karp and Pearl in several ways, but in par­ ticular through the introduction of dead-ends . This anal­ ysis suggests the following conclusions:

1. When the possibility of "catastrophe" (dead ends or prohibitive costs) can be ignored then backtracking methods do not seem attractive, and a far simpler approach like that of the "horizon heuristic" A3 is preferable.
2. When catastrophe looms then a backtracking method like Karp and Pearl's bounded-lookahead plus partial backtrack algorithm A2 does seem an attractive option.

This conclusion lends some mathematical support to certain empirical studies which show that, under given conditions, backtracking algorithms do not perform as well as non-backtracking algorithms. Examples are the empirical analysis of (Dechter and Meiri, 1989; Haral­ ick and Elliott, 1980] in binary constraint satisfaction problems, and the analysis of (de Kleer, 1984] in reason maintenance systems.