Branch And Bound
Branch and Bound is an algorithm design pattern that is like backtracking and it also uses a state-space tree for solving the problem(i.e., the solution is represented as a state-space tree) and it is also used for solving optimization and only minimization problems.
Generally, Branch and Bound belong to the state space search method. Here all the E-node of the children will be generated before a live node becomes an E-node.
Let us discuss this in the following example.
The 15-puzzle problem:
In 1878 Sam Loyad has invented a 15-puzzle problem. It consists of 15 numbered tiles on a square frame where the capacity of the frame is 16 tiles. We have given an arrangement of tiles initially which has to be arranged accordingly to our goals through legal moves. Generally, legal moves in which a tile adjacent to an empty spot(ES) is moved to ES. ( From the example below, tiles having number 2,3,5,6 i.e., anyone can be moved to an empty spot(ES). After having this first move other tiles can arrange in the same way.) Here, each move creates a new arrangement of the tiles which are called states of the puzzle. The initial arrangement is considered as the initial state and the final arrangement is considered as the goal state.
The straightforward way for solving this puzzle is by searching the state space for the final arrangement and using the way from the initial state to the goal state.
We can easily see there are 16! (i.e.,. 20.9*1⁰¹²) a different way of arrangements. But here the truth is only half of them are reachable from the given random initial state. Here state space of the problem is big. So, we must determine whether the goal state is reachable from the initial state before attempting the search in the state space. We denote positions for each tile in the problem from 1 to 16. If position i is the initial state then position 16 is the goal state or the empty spot.
Theorem:
The goal state is reachable from the initial state if and only if i=1 to 16 ∑ less(i) + x is even, where x is the row number of the empty spot.
Here less(i) be the number of tiles j so that j<i and position(j)>position(i).
This theorem is helpful in determining whether the goal state is reachable or not. If there exists a goal state then the sequence of moves can be followed to reach the goal state. For carrying out this entire process a state space tree is generated. For node x, there exists a child in the state space tree which represents the reachable states from node x by one move. After moving the original tile, we do not leave the child as it is, but we rearrange them according to the original movie. For each move, the tail moves up, right, down, left based on the space available. With an example, this can be explained.
Example:
In this example, we are going to check whether we have achieved the goal state or not.
At Initial state:
Less(1)= Less(2)= Less(3)= Less(4)= Less(5)=0.
Less(6)= Less(7)= Less(8)=1 Less(9)= 1 Less(10)=1.
Less(11)= Less(12)= Less(13)= 1 Less(14)= 1 Less(15)=1.
Empty state row , x = 2
∑ = (9*0)+(6*1)+2
∑ = 8
Goal State:
Less(1)= Less(2)= Less(3)= Less(4)= Less(5)=0.
Less(6)= Less(7)= Less(8)= Less(9)= Less(10)=0.
Less(11)= Less(12)= Less(13)= Less(14)=0
Less(15)=0.
x = 4
∑ = 15*0+4
∑ = 4
Since the goal state and initial state are even then the goal state is reachable from the initial state.
The below diagram represents the state space tree of the 15-puzzle problem:
In this state-space tree, no two nodes are equal or similar.
Moves in this theorem are assumed in a such way that every move might reach the goal state or every child node after the move is the final state.
So, let us calculate c’(x)(spell as c cap or c dash) instead of c(x).
Now the formula for c’ is.
c’=f(x) + g’(x)
where f(x) will be the path length from root to x.
g’(x) will be a number of occupied tiles not in the goal position.
In the state-space tree, node one will be terminated after leaving node two, node three, node four, and node five.
Now let us calculate c’(x) for node 2, node 3, node 4,node 5.
c’(2) = 1 + 4 = 5
c’(3) = 1 + 4 = 5
c’(4) = 1 + 2 = 3
c’(5) = 1 + 4 = 5
Here in the above diagram, according to their directions labeling of edges is done through which ES(Empty Space) moves.
Here node 4 will be the lowest node compared to other nodes. So, node 4 will be the next E-node.
Here child 10, child 11, and child 12 will be generated. Now node 2, node 3, node 5, node 10, node 11, and node 12 will be the live nodes.
c’(10)=2+1=3
c’(11)=2+3=5
c’(12)=2+3=5
After this, we will be going to select node 10.
Continue this process until we get E-node as 23 nodes. After getting node 23 as the next E-node it will be our answer
Here in the above diagram, according to their directions labeling of edges is done through which ES(Empty Space) moves.
15-PUZZLE Algorithm:
// nodeset:is used to set and hold the live nodes at any time //
// cost_low: is a variable that hold the best cost at any given//
//node //
Begin
cost_low = ∞;
While nodeset ≠∞ do
- choose a branching node, p, such that
p∈ nodeset; // p is a E-node //
- nodeset= nodeset — {p};
- Generate the children of node p and the
corresponding lower bounds;
Ap={(q,oq ): q is child of p and oq its lower bound}
- For each element (q, oq) in Ap do
- if oq > U //more than lower bound??//
- then
- Kill child q; // q is a child node //
- else
if child q is a solution
then
U =oq ; current best = child q;
else
add child q to nodeset;
endif;
endif;
- endfor;
Endwhile;
End
