Backtracking Strategies

Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

Technically, for backtracking problems:

  1. The algorithm finds a solution by exploring all possible paths created by the choices in the problem. This solution begins with an empty set \(S = \{\}\).

  2. Each choice creates a new subtree '\(s\)' which we add into the set \(S\).

  3. Now there exists two cases:

    1. \(S + s\) is a valid set

    2. \(S + s\) is not a valid set

  4. In case the set is valid, we further make choices and repeat the process until a solution is found, otherwise we backtrack our decision of including \(s\) in \(S\) and explore other paths until a solution is found or all possible paths are exhausted.

Complexity Analysis

Since backtracking algorithm is purely brute force, therefore in terms of time complexity, it performs very poorly.

  • Exponential time complexity \(\rightarrow O(k^N)\)

  • Factorial time complexity \(\rightarrow O(N!)\)

These complexities are due to the fact that we have multiple choices due to which the number of paths increases and subtrees expand rapidly.

Recursive Procedure BACKTRACK(DATA)

In the following algorithm, DATA initializes to the global database.

  1. If TERM(DATA), return NIL

    TERM is a predicate true for arguments that satisfy the termination condition of the production system. Upon successful termination, the algorithm returns NIL (the empty list).

  2. If DEADEND(DATA), return FAIL

    DEADEND is a predicate true for arguments that are known not to be on a path to a solution. Upon reaching a dead end, the algorithm returns FAIL.

  3. RULES \(=\) APPRULES(DATA)

    APPRULES is a function that computes the rules applicable to DATA and orders them either arbitrarily or according to some heuristic merit.

  4. LOOP: if NULL(RULES) return FAIL

    if no rules are present to apply, the procedure fails

  5. R \(=\) FIRST(RULES)

    Best of the applicable rule is applied/selected

  6. RULES \(=\) TAIL(RULES) List of applicable rules is diminished by removing the one just selected

  7. RDATA \(=\) R(DATA)

    Rule R is applied to produce a new database RDATA

  8. PATH \(=\) BACKTRACK(RDATA)

    Backtrack is called recursively with the new database RDATA.

  9. If PATH \(=\) FAIL GOTO LOOP

    If the recursive call fails, try another rule

  10. Return CONS(R, PATH)

    Otherwise, return the successful list of rules, by adding R to the front of the list PATH

The above procedure may never terminate as it may generate new non-terminal databases indefinitely or it may cycle. Both of these cases can be arbitrarily prevented imposing a depth bound on the recursion. Cycling can be avoided by maintaining a list of the databases produced so far and by checking new ones to see if they do not match any on the list.

Backtracking forgets all databases whose paths lead to failures; only the path currently being extended is stored explicitly.

A more flexible approach would involve the explicit storage of all trial paths so that any one of them could be a candidate for further extension.

An Example of Backtracking

Consider an initial database DB1 to which two rules \(R_1\) and \(R_2\) are applicable.

@TODO: add diagram for this backtracking scenario

Suppose the control system selects the rule \(R_1\) which produces DB2 and then suppose the control system selects the rule \(R_3\) which produces DB3

At this point, suppose the control system decides that this path is not promising and backs up to apply \(R_2\) on DB1 to produce DB4.

In case of backtracking, the strategy would erase the records of DB2 and DB3, but if the control strategy would maintain this record, then it could resume work immediately from either DB2 or DB3.

In order to achieve this sort of flexibility, a control system must keep an explicit record of a graph of databases linked by rule application.

The control systems that operate in this manner use graph-search strategies.

Depth Bound

In the context of backtracking algorithm, a depth bound or depth limit is a predefined limit on the depth of a search tree (or recursion depth) that the algorithm is allowed to explore.

It is a technique used to limit the search space and avoid infinite recursion or excessive computation in problems where the search space can grow exponentially.

When a depth bound is applied:

  • The algorithm will only explore the state space upto a certain depth in the search tree

  • If the search reaches the depth limit, it stop exploring further down that branch

  • If the solution is not found at that depth, the algorithm backtracks to the previous level and tries another possibility

An Example of Depth Bound

Let us consider an example of a depth bound in the context of a backtracking algorithm. In the following diagram, the search tree is explored upto a depth of 4.

@TODO: add diagram for this depth bound backtracking scenario

After reaching node \(F\), it explores its neighbour \(C\). As depth of \(C\) is 5, which is more than the depth bound of 4, the algorithm backtracks.

While backtracking to \(F\), it explores no new neighbours, so it backtracks again to \(E\). Once again, it explores no new neighbours, so it backtracks to \(B\).

Now, since \(B\) has a new neighbour \(G\), it explores \(G\) and finds that \(G\) is the solution. Hence, the algorithm stops.

← Previous: Commutative Production Systems | ↑ Up: Advanced Artificial Intelligence | Next: General Graph Search Algorithm →