Backtracking: Set and Solution Space
Backtracking
General method • Useful technique for optimizing search under some constraints • Express the desired solution as an n-tuple (x1 , . . . , xn ) where each xi ∈ 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 = m1 m2 · · · 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 xi 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 ∗ xi ≥ 0, or all nonnegative real numbers ∗ xi = {0, 1} ∗ li ≤ xi ≤ ui 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 xi s must relate to each other. • Determine problem solution by systematically searching the solution space for the given problem instance
General method • Useful technique for optimizing search under some constraints • Express the desired solution as an n-tuple (x1 , . . . , xn ) where each xi ∈ 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 = m1 m2 · · · 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 xi 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 ∗ xi ≥ 0, or all nonnegative real numbers ∗ xi = {0, 1} ∗ li ≤ xi ≤ ui 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 xi s must relate to each other. • Determine problem solution by systematically searching the solution space for the given problem instance