Description: The basis of branch and bound algorithms is a ranking function. The ranking function assigns a value to each node in the graph. At each step, a branch and bound algorithm uses the ranking function to decide which node to expand next. In contrast, the usual DFS (Depth First Search) and BFS( Breadth First Search) exploration algorithms perform a blind search of the graph. Ideally, the ranking function, c(x), ranks nodes based on the cost of a minimal solution reachable from node x. The problem with this ranking function is that the minimal solution must be known ahead of time. Instead, the ranking function uses an estimate, g(x), of the cost of a minimal solution reachable from node x. Using g(x) to rank nodes may require exploring unnecessary nodes in the graph?particularly if g(x) is not a good estimate.The final element of the ranking function measures the cost of reaching a node from the root. As the searches gets farther from the root node, the node falls in the ranking.
To Search:
File list (Check if you may need any files):
branchandbound.docx
Download