Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

5th Sem
...

Each node in the combinatorial tree generated in the last Unit defines a problem state
...

Solution states are those problem states 's' for which the path from the root to 's' defines a
tuple in the solution space
...

Answer states are those solution states 's' for which the path from the root to 's' defines a tuple
that is a member of the set of solutions (i
...
,it satisfies the implicit constraints) of the problem
...

A node which has been generated and all of whose children have not yet been generated is
called a live node
...

A dead node is a generated node, which is not to be expanded further or all of whose children
have been generated
...

Depth first node generation with bounding function is called backtracking
...

The term branch-and-bound refers to all state space search methods in which all children of
the E-node are generated before any other live node can become the E-node
...

A D-search (depth search) state space search will be called LIFO (Last In First Out) search,
as the list of live nodes is a list-in-first-out list (or stack)
...
H
...
K
...


Page 1

5th Sem
...

The branch-and-bound algorithms search a tree model of the solution space to get the
solution
...
An algorithm of
this type specifies a real -valued cost function for each of the nodes that appear in the search tree
...
The
branch-and-bound algorithms are rarely simple
...

Example 8
...
2) for the 4-queens problem
...
This represents the case in which no queen has
been placed on the chessboard
...

It is expanded and its children, nodes2, 18, 34 and 50 are generated
...

The only live nodes 2, 18, 34, and 50
...

It is expanded and the nodes 3, 8, and 13 are generated
...
Nodes 8 and 13 are added to the queue of live nodes
...
H
...
K
...


Page 2

5th Sem
...
Nodes 19, 24, and 29 are generated
...
Node 29 is added to the queue of live nodes
...
Figure 8
...
2 that is
generated by a FIFO branch-and-bound search
...

Numbers inside the nodes correspond to the numbers in Figure 7
...
Numbers outside the nodes
give the order in which the nodes are generated by FIFO branch-and-bound
...


Least Cost (LC) Search:
In both LIFO and FIFO branch-and-bound the selection rule for the next E-node is rather
rigid and in a sense blind
...

Thus, in Example 8
...
However, the rigid FIFO
rule first requires the expansion of all live nodes generated before node 30 was expanded
...
) for live nodes
...

If in the 4-queens example we use a ranking function that assigns node 30 a better rank than
all other live nodes, then node 30 will become E-node, following node 29
...
H
...
K
...


Page 3

5th Sem
...

The ideal way to assign ranks would be on the basis of the additional computational effort (or
cost) needed to reach an answer node from the live node
...
1 is 4 (node 31 is four levels
from node 1)
...
The costs of all remaining nodes on levels 2, 3, and 4 are respectively greater than 3, 2, and 1
...
The only other nodes to get generated are nodes 2, 34, 50, 19, 24, 32, and 31
...
Hence, by the time the cost of a node is
determined, that sub-tree has been searched and there is no need to explore x again
...
) of their cost
...
node x
is assigned a rank using a function (
...
) is any non-decreasing function
...
Hence, such a strategy is called
an LC-search (least cost search)
...
) is defined as, if x is an answer node, then c(x) is the cost (level,
computational difficulty, etc
...
If x is not an
answer node, then c(x) =infinity, providing the sub-tree x contains no answer node; otherwise
c(x) is equals the cost of a minimum cost answer node in the sub-tree x
...
) with f (h(x)) =h(x) is an approximation to c (
...


Bounding:
A branch -and-bound searches the state space tree using any search mechanism in which
all the children of the E-node are generated before another node becomes the E-node
...
H
...
K
...


Page 4

5th Sem
...
Three common search strategies are FIFO, LIFO, and LC
...
) such that (x) <=c(x) is used to provide lower bounds on solutions
obtainable from any node x
...
The starting value for upper can be set to infinity
...
Each time a new answer is found ,the value of upper can be
updated
...
We generalize this problem to allow jobs with different processing times
...
Each job i has associated with it a three tuple
(
)
...
if its processing is not completed by the
deadline , and then a penalty is incurred
...
Hence, a penalty can be incurred only on those jobs not in j
...
such a j is optimal
...
The solution space for this instances consists of all possible
subsets of the job index set{1,2,3,4}
...


H
...
Kothadia (8 00 00 499 54) R
...
College
...


Design and Analysis of Algorithm

Figure 8
...
6 corresponds to the variable tuple size formulations while figure 8
...
In both figures square nodes represent infeasible subsets
...
6 all non-square nodes are answer nodes
...
For this node j= {2,3} and the penalty (cost) is 8
...
7 only non-square leaf nodes are answer nodes
...
This node corresponds to j={2,3} and a penalty of 8
...
7 are given below the nodes
...
H
...
K
...


Page 6

5th Sem
...

This technique is implemented in the traveling salesman problem [TSP] which are
asymmetric (Cij <>Cij) where this technique is an effective procedure
...


STEP 3:

[COLUMN REDUCTION]
Use cost matrix- Row reduced one for all columns do STEP 4
...


STEP 5:

Preserve cost matrix C [which row reduced first and then column reduced]
for the i th time
...


STEP 7:

Calculate effective cost of the edges
...


STEP 8:

Compare all effective cost and pick up the largest l
...


STEP 9:

Delete (i, j) means delete ith row and jth column change (j, i) value to infinity
...


STEP 10:

Repeat step 1 to step 9 until the resultant cost matrix having order of 2*2 and
reduce it
...
R and C
...
H
...
K
...


Page 7

5th Sem
...

STEP 12:

Use result obtained in Step 11 to generate a complete tour
...
H
...
K
...


Page 8

5th Sem
...
H
...
K
...


(5,3),

(5,4)


Page 9

5th Sem
...
C]
(1,2) = 2+1 =3
(2,1) = 12+3 = 15
(3,5) = 2+0 =2
(4,5) = 3+0 = 3
(5,3) = 0+12 = 12
(5,4) = 0+2 = 2
STEP 8:
L having edge (2,1) is the largest
...

Now Cost Matrix =
2
3

4

5



5

2



2

0

18



0

1

4

3

44

3

15

14

1

0

0



STEP 10: The Cost matrix  2 x 2
...

PHASE II:
STEP1: C2(R, R)
2
3
4 5
1
 13 1
3

0

2

4

14 
44 18



0
0

5

1

0



0

STEP 3: C2 (C, R)
2

3

4

5

H
...
Kothadia (8 00 00 499 54) R
...
College
...


Design and Analysis of Algorithm

1



13

1

0

3

13



2

0

4

43

18



0

5

0

0

0



STEP 5: Preserve the above in C2
C2 =
2
1

3

4

5



13

1

0

3

13



2

0

4

43

18



0

5

0

0

0



STEP 6:
L= {(1,5), (3,5), (4,5), (5,2), (5,3), (5,4)}
STEP 7: calculation of E
...

(1,5) = 1+0 =1
(3,5) = 2+0 =2
(4,5) = 18+0 =18
(5,2) = 0+13 =13
(5,3) = 0+13 =13
(5,4) = 0+1 =1
STEP 8: L having an edge (4,5) is the largest
...

Now, cost matrix
2

3

4

H
...
Kothadia (8 00 00 499 54) R
...
College
...


Design and Analysis of Algorithm

1



13

1

3

13



2

5

0

0



STEP 10: THE cost matrix  2x2 hence go to step 1
PHASE III:
STEP 1: C3 (R, R)
2
1

3

4



12

0

3

11



0

5

0

0



STEP 3: C3 (C, R)
2
1
3
5

3

4

0
0

STEP 5: preserve the above in C2

11
0

12

0

STEP 6: L={(1,4), (3,4), (5,2), (5,3)}
STEP 7: calculation of E
...
Hence arbitrarily choose
(1,4)
STEP 9: Delete (i,j) (1,4) and make change in it (4,1) =  if exists
...
H
...
K
...


Page 12

5th Sem
...
H
...
K
...


Page 13

5th Sem
...
H
...
K
...


Page 14

5th Sem
...

Here (1,5)  not possible because already chosen index i (i=j)
(3,5)  not possible as already chosen index
...

Final result:
3—2—1—4—5—3
Cost is 15+15+31+6+7=64

H
...
Kothadia (8 00 00 499 54) R
...
College
...


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
...


Page 16



---