13-04-2012, 02:46 PM
Backtracking
backtracking.doc (Size: 209 KB / Downloads: 70)
Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v1, ..., vm) of values and by traversing, in a depth first manner, the domains of the vectors until the solutions are found.
When invoked, the algorithm starts with an empty vector. At each stage it extends the partial vector with a new value. Upon reaching a partial vector (v1, ..., vi) which can’t represent a partial solution, the algorithm backtracks by removing the trailing value from the vector, and then proceeds by trying to extend the vector with alternative values.
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]
The 0-1 Knapsack
Consider of size K and we want to select from a set of n objects , where the ith object has size si and value vi, a subset of these objects to maximize the value contained in the knapsack with the contents of the knapsack less than or equal to K.
Suppose that K = 16 and n = 4, and we have the following set of objects ordered by their value density.
Run-time Efficiency of the Dynamic Programming Algorithm
For n objects, there are 2n possible solution sets -- the ith object is either in or out of the solution set. The state space, therefore, is represented as a complete binary tree with 2n leaves. Such a tree will have a total of 2n+1 - 1 nodes. The backtracking algorithm, therefore, has a worst-case bound that is O(2n). With pruning the actual number of nodes "visited" by the algorithm is much less.
Graph Coloring
Let G be a graph and m be a given positive integer. We want to discover whether thenodes or G can be colored in such a way that no two adjacent nodes have the same coloryet only m colors are used. This is termed the m-colorability decision problem. Note that if d is the degree of the given graph, then it can be colored with d+1 colors. The mcolorabilityoptimization problem asks for the smallest integer m for which the graph Gcan be colored. This integer is referred to as the chromatic number of the graph. Forexample, the graph of Figure 7.11 can be colored with three colors 1,2, and 3.