backtracking strategy

Theory:

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 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 xis must relate to each other.

• 8-queens problem

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

Backtracking

– Identify data structures to solve the problem

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

_ Second pass: Since each queen is in a different row, define the chessboard solution to be an 8-tuple (x1, . . . , x8),

where xi is the column for ith queen

– Identify explicit constraints

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

_ Solution space of 88 8-tuples

– Identify implicit constraints

_ 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

_ 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

Kruskal’s algorithm is another greedy algorithm for the minimum spanning tree problem that also always yields an optimal solution. It is named Kruskal’s algorithm [Kru56], after Joseph Kruskal, who discovered the algorithm when he was a second-year graduate student. Kruskal’s algorithm looks at the minimum spanning tree for a weighted connected graph G = {V, E} as an acyclic subgraph with |V|-1 edges for which the sum of the edges weights is the smallest.

The algorithm begins by sorting the graph’s edges in non decreasing order of their weights. Then, starting with the empty subgraph, it scans this sorted list adding the next edge on the list to the current subgraph if such an inclusion does not create a cycle and simply skipping the edge otherwise.

Data Structures used:

Pseudocode for Kruskal: –

// Cost – 2 dimensional matrix, cost[u][v] is cost of edge (u,v);

// n no. of vertices.

//‘t’ set of edges in minimum spanning tree – it us a 2D array. t[1…..n][1….2]

// initially each vertex is in different set.

// each vertex is in different set.

Algorithm SimpleUnion (I, j) // i & j are roots of sets.

{

p[i] = j;

}

Algorithm SimpleFind (i ) // return root of ‘i’

{

while (p[i] >=0) do i=p[i];

return I;

}

If we want to perform n-1 unions then can be processed in Linear time O(n)

The time required to process a find for an element at level ‘i’ of a tree is O(i), so total time needed to process n finds is O(n^2)

One can improve the performance of our union & find by avoiding creation of degenerating trees.

We apply weighting rule for Union, which says that if the number of nodes in the tree with root i is less than the number of nodes in the tree with root j, then make j as the parent of i, otherwise make i, as the parent of j. Thus we avoid degenerated/skewed trees.

Similarly we use CollapseFind , to improve the performance of find. In CollapsingFind, we are required to go up to reach the root node and then reset the links. Every first find has to go through intermediate nodes to go up to root node, but every next find on similar node will require only one link to go up, thus reducing the cost cost of find. Collapsing rule says that, if j is a node on the path from i to its root node and p[i] is not root[i], then set p[j] to root[i].

Weighted union(I,j)

{

Temp=p[i]+p[j];

If(p[i]>p[j]) // i has fewer nodes

{

p[i]=j, p[j]=temp;

}

Else

{

p[j]=I; // j has fewer nodes

p[i]=temp;

}

}

Collapse Find(i)

{

r=I;

While(p[r]>=0)

r=p[r];

while(i=r)

{

s=p[i];

p[i]=r;

i=s;

}

}

Analysis of Kruskal algorithm :

Time required to construct the initial heap is log E.

Removal of edge from heap requires again log E and the edge is removed in the while loop which runs for E times, hence the time complexity of algorithm is O(E log E). Here since we have used sets to represent trees and we have used efficient find and union algorithms which take almost O(1) time.