Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: daa furth unit
Description: In this notes you will get a brief notes about The general method—8 queens problem—Sum of subsets—Graph coloring— Hamiltonian cycle—Knapsack problem. and if you have any quieries you can contact me.
Description: In this notes you will get a brief notes about The general method—8 queens problem—Sum of subsets—Graph coloring— Hamiltonian cycle—Knapsack problem. and if you have any quieries you can contact me.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
5th sem
Design and Analysis of Algorithm
UNIT - IV
Backtracking:
The general method—8 queens problem—Sum of subsets—Graph coloring—
Hamiltonian cycle—Knapsack problem
...
Many problems which deal with searching for a set of solutions or for a optimal
solution satisfying some constraints can be solved using the backtracking
formulation
...
The problem is to find a vector, which maximizes or minimizes a criterion
function P(x1…
...
The major advantage of this method is, once we know that a partial vector
(x1,…xi) will not lead to an optimal solution that (mi+1………
...
Many problems solved using backtracking require that all the solutions satisfy a
complex set of constraints
...
ii) Implicit constraints
...
Some examples are,
Xi 0 or Si = {all non-negative real nos
...
Li Xi Ui or Si= {a: Li a Ui}
All tupules that satisfy the explicit constraint define a possible solution space for
I
...
H
...
K
...
Algorithm:
Algorithm IBacktracking (n)
// This schema describes the backtracking procedure
...
{
k=1;
While (k 0) do
{
if (there remains all untried
X[k] T (X[1],[2],…
...
X[k])) is true ) then
{
if(X[1],……X[k] )is the path to the answer node)
Then write(X[1:k]);
k=k+1;
//consider the next step
...
}
}
All solutions are generated in X[1:n] and printed as soon as they are determined
...
X[k-1]) is all possible values of X[k] gives that X[1],……
...
Bk(X[1]………X[k]) is a boundary function which determines the elements of
X[k] which satisfies the implicit constraint
...
Sum of subsets
...
Graph coloring
...
Hamiltonian cycle
...
N-Queens problem
...
this is called sum of subsets
problem
...
H
...
K
...
If the state space tree of the solution, for a node at level I, the left child
corresponds to X(i)=1 and right to X(i)=0
...
We have to generate all
possible combinations of subsets whose sum is equal to the given value M=30
...
The state space tree for the given problem is,
S, n, r
0,1,73
X(1)=1
x(1)=0
5,2,68
0,2,68
X(2)=1
x(2)=0
5,3,58
X(3)=1
27,4,46
x(2)=1
5,3,58
x(3)=0
10,3,58
x(3)=1
15,4,46
5,4,4
X(4)=1
B
10,4,46
C
x(4)=0
5,5,33
X(5)=1
A
0,3,58
x(3)=0
17,4,46
X(4)=0
15,5,33
x(2)=0
10,5,33
x(5)=1
20,6,18
Ist solution is A -> 1 1 0 0 1 0
IInd solution is B -> 1 0 1 1 0 0
H
...
Kothadia (8 00 00 4 99 53)
R
...
College
Page 3
5th sem
Design and Analysis of Algorithm
III rd solution is C -> 0 0 1 0 0 1
In the state space tree, edges from level ‘i’ nodes to ‘i+1’ nodes are labeled with
the values of Xi, which is either 0 or 1
...
The right subtree of the root defines all subsets, which does not include Wi
...
The value of Xi indicates whether the weight Wi is included or not
...
e
...
We have to check starting from the first node
...
If S+X(k)=M then we print the subset b’coz the sum is the required output
...
If so, we have to generate the left sub tree
...
After generating the left sub tree we have to generate the right sub tree, for this
we have to check S+W(k+1)<=M
...
Repeat the process and find all the possible combinations of the subset
...
note s+w(k)<=M since Bk-1 is true
...
Else if (S+W[k]+W[k+1]<=m) then sum of sub (S+W[k], k+1,r- W[k]);
//generate right child and evaluate Bk
...
H
...
K
...
A HAMILTONIAN CYCLE
is a round trip path along ‘n’ edges of G which every vertex once and returns to
its starting position
...
Vn+1,then the edges are in E,1<=I<=n and the
Vi are distinct except V1 and Vn+1 which are equal
...
1
2
3
4
8
7
6
5
The graph G1 has Hamiltonian cycles:
->1,3,4,5,6,7,8,2,1 and
->1,2,8,7,6,5,4,3,1
...
Procedure:
1
...
Xn) where Xi represents the I th visited
vertex of the proposed cycle
...
Create a cost adjacency matrix for the given graph
...
The solution array initialized to all zeros except X(1)=1,b’coz the cycle should
start at vertex ‘1’
...
Now we have to find the second vertex to be visited in the cycle
...
H
...
K
...
The vertex from 1 to n are included in the cycle one by one by checking 2
conditions,
1
...
2
...
6
...
7
...
if no path, the go back one step and after the previous visited node
...
Repeat the above steps to generate possible Hamiltonian cycle
...
If (j=k) then
//if true then the vertex is distinct
...
H
...
K
...
Solution:
The solution vector X (X1…Xn) represents a solution in which Xi is the column
of the th row where I th queen is placed
...
Second, we have to check no two queens are in same column
...
Third, we have to check no two queens are in it diagonal
...
Also, every element on the same diagonal that runs from lower right to upper left
has the same value
...
STEPS TO GENERATE THE SOLUTION:
Initialize x array to zero and start by placing the first queen in k=1 in the first row
...
Of
columns or no
...
If k=1 then x (k)=1
...
Here we
have to check whether there is any queen in the same column or diagonal
...
Check whether
X (I)=X(k) for column |X(i)-X(k)|=(I-k) for the same diagonal
...
For not possible condition increment X (k) value by one and precede d until the
position is found
...
H
...
K
...
If k
So decrement the ‘k’ value by one i
...
we have to back track and after the position
of the previous queen
...
otherwise it returns //
//false
...
Abs® returns the
//absolute value of r
...
Or (abs (X [j]-I)=Abs (j-k)))
Then return false;
Return true;
}
Algorithm Nqueen (k,n)
//using backtracking it prints all possible positions of n queens in ‘n*n’ chessboard
...
{
For I=1 to n do
{
If place (k,I) then
{
X [k]=I;
If (k=n) then write (X [1:n]);
Else nquenns(k+1,n) ;
}
}
}
Example: 4 queens
...
H
...
K
...
If the nodes of ‘G’ can be
colored in such a way that no two adjacent nodes have the same color
...
So it’s called M-color ability decision problem
...
This integer is referred
to as chromatic number of the graph
...
Suppose we are given a map then, we have to convert it into planar
...
If two regions are adjacent then the
corresponding nodes are joined by an edge
...
4
5
2
1
3
1 is adjacent to 2, 3, 4
...
H
...
K
...
The Colors will be represented by the integers 1,2,…
...
,X(n) ,X(index) is the color, index is the
node
...
Repeat the procedure until all possible combinations of colors are found
...
Node-1 can take the given graph of 4 nodes using 3 colors
...
H
...
Kothadia (8 00 00 4 99 53)
R
...
College
Page 10
5th sem
Design and Analysis of Algorithm
State Space Tree:
Algorithm:
Algorithm mColoring(k)
// the graph is represented by its Boolean adjacency matrix G[1:n,1:n]
...
,m to the vertices of the graph such that adjacent vertices are assigned
//distinct integers are printed
...
{
repeat
{
// generate all legal assignment for X[k]
...
If (X[k]=0) then return;
// No new color possible
...
A value for X[k] is determined in the
//range[0,m]
...
If no such color exists, then X[k] is
0
...
H
...
K
...
If(X[k]=0) then return;
//All colors have been used
...
If((G[k,j] 0)and(X[k] = X[j]))
// If (k,j) is an edge and if adjacent vertices have the same color
...
} until(false); //otherwise try to find another color
...
Knapsack Problem using Backtracking:
The problem is similar to the zero-one (0/1) knapsack optimization problem is
dynamic programming algorithm
...
1 i n
Xi Constitute Zero-one valued Vector
...
Bounding functions are needed to help kill some live nodes without expanding
them
...
The profits and weights are assigned in descending order depend upon the ratio
...
e
...
H
...
K
...
e
...
(i
...
) K 1
...
So unit of that object is ‘0’
...
e
...
Then We are going to the bounding function ,this function determines an upper
bound on the best solution obtainable at level K+1
...
Algorithm:
Algorithm Bknap(k,cp,cw)
// ‘m’ is the size of the knapsack; ‘n’ no
...
W[]&P[] are the
//weights & weights
...
//fwFinal weights of knapsack
...
profit
...
{
// Generate left child
...
H
...
K
...
//cw current weight total
...
//mthe knapsack size
...
e
...
Fp = (-1)
1 3 & 0+4 6
cw = 4,cp = 5,y(1) =1
k = k+2
2 3 but 7>6
so y(2) = 0
So bound(5,4,2,6)
H
...
Kothadia (8 00 00 4 99 53)
R
...
College
Page 14
5th sem
Design and Analysis of Algorithm
B=5
C=4
I=3 to 3
C=6
6 6
So return 5+(1-(6-6))/(2*1)
5
...
So, k=k+1 (i
...
) 3
...
K=4
...
H
...
Kothadia (8 00 00 4 99 53)
R
...
College
Page 15
5th sem
Name
Design and Analysis of Algorithm
:
Contact no
...
Kothadia
8 00 00 4 99 53
College
:
R
...
University
City
:
Rajkot
For more material and soft copy book visit below blog…
http://kothadiahardik
...
com
Free software download visit below blog…
...
blogspot
...
H
...
K
Title: daa furth unit
Description: In this notes you will get a brief notes about The general method—8 queens problem—Sum of subsets—Graph coloring— Hamiltonian cycle—Knapsack problem. and if you have any quieries you can contact me.
Description: In this notes you will get a brief notes about The general method—8 queens problem—Sum of subsets—Graph coloring— Hamiltonian cycle—Knapsack problem. and if you have any quieries you can contact me.