ALGORITHM ANALYSIS AND DESIGN

2:15 AM Algorithm Analysis and Design

BRANCH AND BOUND METHOD

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

1

Principle Used

• State space search method
• All children of the E-node (expanding node) are generated before any other live node can become the E -node.
• Breadth First Generation
• Apply bounding functions at each node
• Prune/ cut off less optimal paths

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

2

Branch And Bound Methods

• FIFO
• (First Node generated (In) is Expanded First (Out))
• LIFO
• (Last Node generated (In) is Expanded First (Out))
• LC - Search
• ( Least-Cost Search/ Best First Search)

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

3

FIFO Branch And Bound Technique

2:15 AM Algorithm Analysis and Design

the list of live nodes is maintained as a FIFO list or queue

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

4

LIFO Branch And Bound Technique

2:15 AM Algorithm Analysis and Design

the list of live nodes is maintained as a LIFO list or stack

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

5

Least Cost Search

2:15 AM Algorithm Analysis and Design

• Intelligent ranking function
• Cost of reaching the answer/goal state
• E-node selection based on rank
• Most promising path is explored first

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

6

Computing Cost

2:15 AM Algorithm Analysis and Design

X -Live Node

C(X)- Best cost of solving X

Intelligent function/ approximation function Ĉ to C(X)

Ĉ(X) - Returns a lower bound on the cost of solving through X

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

7

Bounding Function

2:15 AM Algorithm Analysis and Design

U- Upper bound on the cost of a minimum cost solution

U can be a very high cost / the cost of reaching an already found answer state

All live nodes X with Ĉ(X)>U can be killed/ bounded.

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

8

Control Abstraction

Let bound U ← ∞ . //structure min-heap for least-cost search….

Expand from the root and generate children with some estimated cost where children are stored in “live node” L .

While( L is not empty)

{Select and remove the least cost live node as the “expansion node” E, which is the most possible node to the optimal solution.

if( c(E) < U ) then // if (c(E) > U) then E need not be expanded

{ generate children from E.

If child t’s estimated cost c(t) < U, then // if (c(t) > U) then t { Add t to L. //need not be expanded

If t is a solution node and c(t) < U, then U ← c(t) } } }

2:15 AM Algorithm Analysis and Design

9

The node with the last bound U is an optimal solution node.

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

9

More On Least Cost Search

• Let x be a node in the state space tree.
• The cost function of x is c(x) = f(x) + g(x).
• f(x) is the real cost of traversing from the root to x and is a non-decreasing function.
• g(x) is an estimated cost from node x to an answer node.

2:15 AM Algorithm Analysis and Design

10

R

x

A

f(x)

g(x)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

10

Least Cost (LC) Search

2:15 AM Algorithm Analysis and Design

11

Ĉ(x) =f(h(x) )+ĝ(x)

Select an e-node with least Ĉ(x)

• If ĝ(x)=0 Ĉ(x) =f(h(x)) =level of node x

– Breadth First Search

• If f(h(x))=0 and ĝ(x)>= ĝ(y)

where x is parent of y

– Depth First Search

R

x

A

f(h(x))

ĝ(x)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

11

LC Branch & Bound

2:15 AM Algorithm Analysis and Design

12

x

• An LC search combined with branch and

bound is known as LC branch and bound

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

12

Analysis

• The closer estimate of g(x), the smaller number of nodes generated in the state space tree and hence the total computation time may decrease.
• A good ĝ(x) results in more computation , thus the total computation time may increase.
• compromise between unbounded nodes in the state space tree and the computation complexity of ĝ(x)

2:15 AM Algorithm Analysis and Design

13

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

13

Puzzles

• Given n numberd tiles on a square frame of capacity n+1 (k X k)
• Initial arrangement
• Goal Arrangement
• Legal moves

2:15 AM Algorithm Analysis and Design

An initial arrangement

Goal arrangement

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

14

8 - Puzzle

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

15

Solving 8 Puzzle

2:15 AM Algorithm Analysis and Design

Goal:

↑

←

↓

←

←

→

↓

↓

←

→

↓

↑

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

16

The 15-puzzle: Cost Estimation

• Ĉ(X) = f(x) + ĝ(x)
• f(x) is the length of the path from the root to node x
• g(x) is an estimate of the length of a shortest path from x downward to a goal node.
• ĝ(x) = number of nonblank tiles not in their goal position

2:15 AM Algorithm Analysis and Design

17

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

17

Solving the 15-Puzzle - Steps

• Initially, the bound is set to infinity, U ← ∞.
• Whenever an answer is reached, the bound is compared.
• If the cost of the new answer is less than the bound, then the bound is replaced by the new smaller cost.
• If the estimated cost Ĉ(X) >U, then x is bounded.
• When cost traversing from the root via x to goal node is greater than or equal to U, x cannot lead to better solution than U.

2:15 AM Algorithm Analysis and Design

18

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

18

Solving the 15-Puzzle

2:15 AM Algorithm Analysis and Design

Initial

Goal

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

19

Solving the 15-Puzzle Contd..

2:15 AM Algorithm Analysis and Design

Initial

Goal

ĝ(x)= number of misplaced tiles = 3

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

20

2:15 AM Algorithm Analysis and Design

21

c(2) = 1+4

c(3) = 1+4

c(4) = 1+2

c(5) = 1+4

c(10) = 2+1

c(11) = 2+3

c(12) = 2+3

U ← ∞

U ← 3

c(22) = 3+2

c(23) = 3 = f(23) and g(23) = 0

Because the costs of the remaining live nodes are

c(2) = 5, c(3) = 5, c(5) = 5, c(11) = 5, c(12) = 5, c(22) = 5.

None of the 6 nodes’ costs are less than B = 3,

thus the 6 nodes become dead nodes.

There is no live node, then

node 23 is the goal node.

That is, 3 steps is the minimum

number of steps to the goal.

Solution

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

21

Traveling Salesman Problem

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

22

Definition

• To find a minimum round trip path containing all vertices of G=(V,E), a directed graph with n vertices.

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

23

Static State Space Tree

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

24

Applying LCBB

• C(A) = Cost of a minimum cost path through A
• C(A) is defined in 2 ways
• If A is leaf
• Length of tour defined by the path from the root to A
• If A is not a leaf
• Cost of a minimum-cost leaf in the sub tree A

​

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

25

Obtaining Cost Estimate

• Ĉ(A) Estimated value of C(A)
• = Cost to reach A +Estimated cost to goal from A

​

​

• A better Ĉ can be obtained using the concept of reduced matrix .

2:15 AM Algorithm Analysis and Design

R

x

A

f(h(x))

ĝ(x)

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

26

Principle Used

• If t is chosen to be the minimum entry in row i (column j), subtracting t from all entries introduces a zero in row i (column j)
• A minimum cost remains the minimum cost tour after the operation
• Repeating process to all rows and columns of cost matrix

​

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

27

Reduced Matrix

• A row(column) in a matrix is said to be reduced iff it contains at least one zero and all remaining entries are non-negative
• A matrix is reduced iff every column and every row is reduced

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

28

Example

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

29

Concept of Reduction

• Required to find the minimal cost cycle
• Starts at vertex 1 passes through all vertices and ends at 1
• For each vertex i
• Exactly be one edge going to vertex i
• and one edge leaving the vertex.

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

30

Reducing Rows

• Row i represent all edges leavingvertex i.
• Any cycle will cost at least as that of minimum cost edge leaving i
• Represented by minimum value in row i

2:15 AM Algorithm Analysis and Design

​

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

31

Reducing Columns

• Column j represent all edges entering vertex j
• Any cycle will cost at least as that of minimum cost edge entering j
• Represented by minimum value in column j

2:15 AM Algorithm Analysis and Design

​

​

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

32

Example for Row Reduction

• Minimum cost leaving vertex 1
• Minimum cost edge in row1 = 10
• Minimum cost leaving vertex 2
• Minimum cost edge in row2 = 2
• Minimum cost leaving vertex 3
• Minimum cost edge in row3 = 2
• Minimum cost leaving vertex 4
• Minimum cost edge in row4 = 3
• Minimum cost leaving vertex 5
• Minimum cost edge in row5 = 4

2:15 AM Algorithm Analysis and Design

Cost Matrix

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

33

Reducing Rows

2:15 AM Algorithm Analysis and Design

α 10 20 0 1

13 α 14 2 0

1 3 α 0 2

16 3 15 α 0

12 0 3 12 α

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

34

Example for Column Reduction

• Minimum cost to reach vertex1
• Minimum cost edge in col 1 = 3
• Minimum cost to reach vertex2
• Minimum cost edge in col 2 = 4
• Minimum cost to reach vertex3
• Minimum cost edge in col 3 = 7
• Minimum cost to reach vertex4
• Minimum cost edge in col 4 = 2
• Minimum cost to reach vertex5
• Minimum cost edge in col 5 = 7

2:15 AM Algorithm Analysis and Design

Cost Matrix

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

35

Reducing Column

2:15 AM Algorithm Analysis and Design

1

0

3

0

0

Minimum Cost

α 10 17 10 1

12 α 11 2 0

0 3 α 0 2

15 3 12 α 0

11 0 0 12 α

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

36

Minimum Cost Path

• Any minimum cost path should contain at least one edge leaving and entering a particular node.
• Will have at least a cost equal to the the total sum of minimum cost edges leaving and entering all vertices.
• Will have at least a cost of rowsums + columnsums obtained while reducing the matrix

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

37

Reduced Matrix

2:15 AM Algorithm Analysis and Design

=25

Minimum Cost

Min cost for level 2 of state space tree is 25

α 10 17 10 1

12 α 11 2 0

0 3 α 0 2

15 3 12 α 0

11 0 0 12 α

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

38

Reduced Matrix for A Child Node

Reduced matrix for a child node S of R can be obtained as

1. Change all entries in row i and column j of cost matrix A to α to prevent the use of any more edges leaving vertex i or entering vertex j
2. Set A(j,i) to α
3. Reduce all rows and columns except those containing only values α

​

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

39

Computing Ĉ (S)

• Reduce all rows & columns.
• Let reduced value be r
• So Reduced matrix can be calculated as
• Ĉ (S) = Ĉ(R) + A(i, j) + r

​

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

40

Reduced Cost Matrix

• Reduced cost matrix L = 25

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

41

Reduced Matrix – Path 1,2

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+10+0= 35

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

42

Reduced Matrix – Path 1,3

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+17+11= 53

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

43

Reduced Matrix – Path 1,4

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+0+0= 25

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

44

Reduced Matrix – Path 1,5

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+1+5= 31

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

45

Static State Space Tree

2:15 AM Algorithm Analysis and Design

1

25

28

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

46

Reduced Matrix–Path 1,4,2 -Node 6

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+3= 28

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

47

Reduced Matrix–Path 1,4,3 -Node 7

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+12+2+11= 50

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

48

Reduced Matrix–Path 1,4,5 -Node 8

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+0+11= 36

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

49

Reduced Matrix–Path 1,4,2,3 -Node 9

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 28+11+2+11= 52

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

50

Reduced Matrix-Path 1,4,2,5-Node 10

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 28+0+0= 28

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

51

Reduced Matrix-Path 1,4,2,5,3-Node 11

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 28+0+0= 28

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

52

Dynamic Trees�

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

53

Dynamic Trees

• All tours have a minimum length of 25
• Represented by the root of the tree
• Decision regarding
• Inclusion of edge <i,j>-left subtree
• Exclusion of edge <i,j>- right subtree

2:15 AM Algorithm Analysis and Design

2

3

Include <i,j>

1

Exclude <i,j>

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

54

Dynamic Trees Contd..

• If the optimal tour is included in the left subtree
• Then only n-1 edges more
• Else n edges more

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

55

Dynamic Trees Contd..

• Our aim is to get the optimal tour faster.
• Use heuristic to choose an edge
• A selection rule is to choose an edge which results in a right sub tree that has highest ^c value.
• Another selection strategy can be to choose an edge such that the difference in ^c values for the left and right sub trees is maximum.

​

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

56

Dynamic Trees Contd..

• An edge <i, j> which will maximize the Ĉ value of the right sub tree is always selected.
• If A(i,j) is +ve
• the Ĉ value of the right sub tree will remain 25(original) value.
• if A(i,j) = 0
• Ĉ of the right sub tree will be high.
• So such an edge is selected

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

57

Selection of Edge

• Selection of the edge<i,j> will increase the Ĉ of right sub tree by  where
•  = min _k#j{A(i,k)}+ min _k#i{A(k,j)}
• An edge with highest  is selected first

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

58

Reduced Matrix�Include < 1,2>

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) + A(i, j) + r= 25+10+0= 35

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

59

Reduced Matrix�Exclude < 1,2>

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) = 25

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

60

Reduced Matrix�Exclude < 3,1>

2:15 AM Algorithm Analysis and Design

Ĉ (S) = Ĉ(R) +r= 25 +11=36

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

61

Dynamic State Space Tree

2:15 AM Algorithm Analysis and Design

2

3

Include <3,1>

1

Exclude <3,1>

4

5

Include <5,3>

Exclude <5,3>

2

3

Include <1,4>

Exclude <1,4>

25

25

36

28

36

28

37

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

62

2:15 AM Algorithm Analysis and Design

Computer Science and Engineering, M.A.College of Engineering, Kothamangalam

63