BACKTRACKING

General method

• Useful technique for optimizing search under some constraints
• Express the desired solution as an n-tuple (x1, . . . , xn) where each xi 2 Si, Si being a finite set
• The solution is based on finding one or more vectors that maximize, minimize, or satisfy a criterion function P(x1, . . . , xn)
• Sorting an array a[n]

Ø      Find an n-tuple where the element xi is the index of ith smallest element in a

Ø      Criterion function is given by a[xi] _ a[xi+1] for 1 _ i < n

Ø      Set Si is a finite set of integers in the range [1,n]

• Brute force approach

Ø      Let the size of set Si be mi

Ø      There are m = m1m2 · · ·mn n-tuples that satisfy the criterion function P

Ø      In brute force algorithm, you have to form all the m n-tuples to determine the optimal solutions

• Backtrack approach

Ø      Requires less than m trials to determine the solution

Ø      Form a solution (partial vector) and check at every step if this has any chance of success

Ø      If the solution at any point seems not-promising, ignore it

Ø      If the partial vector (x1, x2, . . . , xi) does not yield an optimal solution, ignore mi+1 · · ·mn possible test vectors even without looking at them

• All the solutions require a set of constraints divided into two categories: explicit and implicit constraints

Definition 1 Explicit constraints are rules that restrict each x_i to take on values only from a given set.

Ø      Explicit constraints depend on the particular instance I of problem being solved

Ø      All tuples that satisfy the explicit constraints define a possible solution space for I

Ø      Examples of explicit constraints

§         x_i ≥ 0, or all nonnegative real numbers

§         x_i = {0, 1}

§         l_i  ≤ x_i ≤ u_i

Definition 2 Implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the criterion function.

Ø      Implicit constraints describe the way in which the x_is must relate to each other.

• Determine problem solution by systematically searching the solution space for the given problem instance

Ø      Use a tree organization for solution space

• 8-queens problem

Ø      Place eight queens on an 8 × 8 chessboard so that no queen attacks another queen

 

Ø      Identify data structures to solve the problem

v     First pass: Define the chessboard to be an 8 × 8 array

v     Second pass: Since each queen is in a different row, define the chessboard solution to be an 8-tuple (x1, . . . , x8), where x_i is the column for i^th queen

Ø      Identify explicit constraints

v     Explicit constraints using 8-tuple formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 ≤ i ≤ 8

v     Solution space of 88 8-tuples

Ø      Identify implicit constraints

v     No two xi can be the same, or all the queens must be in different columns

§         All solutions are permutations of the 8-tuple (1, 2, 3, 4, 5, 6, 7, 8)

§         Reduces the size of solution space from 88 to 8! tuples

v     No two queens can be on the same diagonal

Ø      The solution above is expressed as an 8-tuple as 4, 6, 8, 2, 7, 1, 3, 5