Least Cost Branch and Bound

Least Cost Branch and Bound is the way of finding a solution from the state space tree.

  • FIFO or LIFO is a very crude way of searching. It does not check the goodness of node. They blindly select the E node strictly in FIFO or LIFO order, without giving any preference to the node having better chances of getting answers quickly.
Least Cost Branch and Bound
Fig. (a): State-space tree
  • In Fig. (a), node 31 is the answer node. When node 30 is generated, it should become the E-node, so that in the very next step, we get the solution. But the FIFO strategy forces the search to expand all the live nodes generated before 30, i.e., nodes 35, 40, 45, 51, 56, 61, 9, 11, 14, 16}.
  • This search can be speeded up by using the ranking function (.) for live nodes. Consider Fig. (a). If the ranking function assigns a better value to node 30 than the remaining live nodes, then node 30 will become the E-node as soon as it is generated, and we will get the solution at the very next step, i.e. node 31.
  • Ranking basically depends on the additional effort (cost) required to reach the answer node from the live node.
  • For any node x, the cost is determined by (1) the number of nodes in the subtree x that need to be generated before the answer node is generated, or (2) the number of levels from x to the answer node.
  • Using the second measure, it can be seen from the
    Fig. (a) shows that the cost of an answer node is 4 (node 31 is four levels away from the root node).
  • Node 39 (child of 38) is also an answer node. So the cost of nodes {18, 34}, {29, 35}, and {30, 38 is respectively 3, 2, and 1. And the remaining nodes on levels 2, 3, and 4 have a cost greater than 3, 2, and 1, respectively.
  • With this approach, only 1, 18, 29, and 30 become the E-nodes. And the other nodes which are generated but not converted to E nodes would be 2, 34, 50, 19, 24, 32, and 31.
  • Cost measure 1 generates a minimum number of nodes.
  • If cost measure 2 is used, then only nodes that become E nodes would be on the path from the answer node to the root node.
  • For any measure, searching the state space tree incurs major search time. And hence, nodes are ranked using estimated cost hat{g}(.)
  • Let hat{g}(x) be the additional effort needed to reach an answer node from x. function hat{c}(.) assigns ranking to node x such that,

                                    hat{c}(x)    =   f(h(x)) + hat{g} (x)

  • h(x) is the cost of reaching from x to root.
  • In LC search, the cost function c(.) is defined as follows :
    • If x is answer node, then c(x) is the cost of reaching x from root
    • If x is not answer node and subtree of x does not contain answer node than c(x) = ∞
    • Otherwise, c(x) is the cost of minimum cost answer node in subtree x.

Control Abstraction

Least Cost Branch and Bound works as follow:

  • Let T and c(.) represent state space tree and cost function for the node in T.
  • For node x ∈ T, c(x) represents the minimum cost of the answer node in the subtree rooted at x. Thus, C(T) represents the cost of the minimum-cost answer in state space T.
  • Finding an exact cost function c(.) is challenging, so in practice, the heuristic function (.) is used to estimate c(.).
  • Heuristic functions are often simple to compute and provide close to optimal performance.
  • The algorithm for LCSearch is described below. Function Least( ) finds the live node with the minimum (.). This node is deleted from the list of live nodes and returned.
  • Function Add(x) adds the new live node to the list of live nodes. Min-heap data structure is used to implement a list of live nodes so that the node with the lowest cost is always at the front. So that Least( ) function can retrieve the minimum cost node in constant time.
  • The LCSearch algorithm returns the path from answer node to the root node. To trace the path to the root, parent index is stored with each live node x.

Algorithm for Least Cost Branch and Bound

Algorithm

 LCSearch(T)
// Description: Find answer node from state space tree and 
print path 
// Input : State space tree T
// Output : Success / Failure

if

 T is an answer node 

then


  

output

 T 
  

return


end


E ← T		
Initialize list of live node to empty

while

(true) 

do


  

for

each child x of E 

do


    

if

 x is an answer node 

then


      

output

 path from x to T
      

return


    

end


    Add(x)	
    x.parent ← E
  

end


  

if

 there are no more live nodes 

then


    

print

“No answer node” 
    

return


  

end


  E ← Least()

end


Additional Reading: Read More

You may also like...

Leave a Reply

Your email address will not be published.