One Stop GATE Forum: Backtracking

Message

   6.1 Backtracking

Problems, which deal with searching a set of solutions, or which
ask for an optimal solution satisfying some constraints can be solved
using the backtracking formulation. The backtracking algorithm yields
the proper solution in fewer trials.

The basic idea of backtracking is to build up a vector one component at
a time and to test whether the vector being formed has any chance of
success. The major advantage of this algorithm is that if it is
realized that the partial vector generated does not lead to an optimal
solution then that vector may be ignored.

Backtracking algorithm determine the solution by systematically
searching the solution space for the given problem. This search is
accomplished by using a free organization. Backtracking is a depth
first search with some bounding function. All solutions using
backtracking are required to satisfy a complex set of constraints. The
constraints may be explicit or implicit.

Explicit constraints are rules, which restrict each vector element to
be chosen from the given set. Implicit constraints are rules, which
determine which of the tuples in the solution space, actually satisfy
the criterion function.

6.1.1 Cassette filling problem:

There are n programs that are to be stored on a tape of length L.  Every program ‘i’ is of length l_i.
All programs can be stored on the tape if and only if the sum of the
lengths of the programs is at most L. In this problem, it is assumed
that whenever a program is to be retrieved, the tape is positioned at
the start end. Hence, the time t_j needed to retrieve program i_j from a tape having the programs in the order i₁,i₂, …,i_n is called mean retrieval time(MRT) and is given by
   t_j =S
l_ikk=1,2,…,j 

In the optimal storage
on tape problem, we are required to find a permutation for the n
programs so that when they are stored on the tape, the MRT is minimized.

Let n=3 and (l₁,l₂,l₃)=(5,10,3),there are n!=6 possible orderings. These orderings and their respective MRT is given in the fig 6.1. Hence, the best order of recording is 3,1,2.

6.1.2 Subset problem:

There are n positive numbers given in a set. The desire is to find all
possible subsets of this set, the contents of which add onto a
predefined value M.

Let there be n elements in the main set. W=w[1..n] represent the
elements of the set. i.e., w = (w1,w2,w3,…,wn) vector x = x[1..n]
assumes either 0 or 1 value. If element w(i) is included in the subset
then x(i) =1.

Consider n=6 m=30 and w[1..6]={5,10,12,13,15,18}. The partial
backtracking tree is shown in fig 6.2. The label to the left of a node
represents the item number chosen for insertion and the label to the
right represents the space occupied in M. S represents a solution to
the given problem and B represents a bounding criteria if no solution
can be reached. For the above problem the solution could be
(1,1,0,0,1,0), (1,0,1,1,0,0) and (0,0,1,0,0,1). Completion of the tree structure is left as an assignment for the reader.

6.3.3 8 queen problem:

The 8 queen problem can be stated as follows. Consider a chessboard of
order 8X8. The problem is to place 8 queens on this board such that no
two queens are attack can attack each other.

Illustration.

Consider the problem of 4 queens, backtracking solution for this is as
shown in the fig 6.3. The figure shows a partial backtracking tree.
Completion of the tree is left as an assignment for the reader.

click here for more details:

http://www.vyomworld.com/gate/cs/ada/6.1.asp

Author	Message
gita Newbie Joined: 08Apr2007 Online Status: Offline Posts: 19	Topic: Backtracking Posted: 08Apr2007 at 10:56pm
	6.1 Backtracking Problems, which deal with searching a set of solutions, or which ask for an optimal solution satisfying some constraints can be solved using the backtracking formulation. The backtracking algorithm yields the proper solution in fewer trials. The basic idea of backtracking is to build up a vector one component at a time and to test whether the vector being formed has any chance of success. The major advantage of this algorithm is that if it is realized that the partial vector generated does not lead to an optimal solution then that vector may be ignored. Backtracking algorithm determine the solution by systematically searching the solution space for the given problem. This search is accomplished by using a free organization. Backtracking is a depth first search with some bounding function. All solutions using backtracking are required to satisfy a complex set of constraints. The constraints may be explicit or implicit. Explicit constraints are rules, which restrict each vector element to be chosen from the given set. Implicit constraints are rules, which determine which of the tuples in the solution space, actually satisfy the criterion function. 6.1.1 Cassette filling problem: There are n programs that are to be stored on a tape of length L. Every program ‘i’ is of length l_i. All programs can be stored on the tape if and only if the sum of the lengths of the programs is at most L. In this problem, it is assumed that whenever a program is to be retrieved, the tape is positioned at the start end. Hence, the time t_j needed to retrieve program i_j from a tape having the programs in the order i₁,i₂, …,i_n is called mean retrieval time(MRT) and is given by t_j =S l_ikk=1,2,…,j In the optimal storage on tape problem, we are required to find a permutation for the n programs so that when they are stored on the tape, the MRT is minimized. Let n=3 and (l₁,l₂,l₃)=(5,10,3),there are n!=6 possible orderings. These orderings and their respective MRT is given in the fig 6.1. Hence, the best order of recording is 3,1,2. 6.1.2 Subset problem: There are n positive numbers given in a set. The desire is to find all possible subsets of this set, the contents of which add onto a predefined value M. Let there be n elements in the main set. W=w[1..n] represent the elements of the set. i.e., w = (w1,w2,w3,…,wn) vector x = x[1..n] assumes either 0 or 1 value. If element w(i) is included in the subset then x(i) =1. Consider n=6 m=30 and w[1..6]={5,10,12,13,15,18}. The partial backtracking tree is shown in fig 6.2. The label to the left of a node represents the item number chosen for insertion and the label to the right represents the space occupied in M. S represents a solution to the given problem and B represents a bounding criteria if no solution can be reached. For the above problem the solution could be (1,1,0,0,1,0), (1,0,1,1,0,0) and (0,0,1,0,0,1). Completion of the tree structure is left as an assignment for the reader. 6.3.3 8 queen problem: The 8 queen problem can be stated as follows. Consider a chessboard of order 8X8. The problem is to place 8 queens on this board such that no two queens are attack can attack each other. Illustration. Consider the problem of 4 queens, backtracking solution for this is as shown in the fig 6.3. The figure shows a partial backtracking tree. Completion of the tree is left as an assignment for the reader. click here for more details: http://www.vyomworld.com/gate/cs/ada/6.1.asp Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Technical Discussions : GATE CS

Topic: Backtracking