7

I am studying branch and bound and best-first search for my thesis work but found lots of contradictions on the web about these two concept. First I thought branch and bound only prune the branches ending to high cost solution (using heuristic) and do not prioritize the search (do a simple DFS or BFS on the rest of a tree after the pruning). However, later I found many resources that say BB ranks the states as well and considers nodes with higher rank first (a prioritized search). If it is so, what is exactly the difference between BB and best-first search?

Barpa
  • 275
  • 1
  • 3
  • 13

1 Answers1

6

The 2 concepts are related (you can sometimes even combine them) but you should just focus on the fundamental differences between them as their names suggest:

Branch and bound explores the search space exhaustively by branching on variables (=test out the values of the variables). This creates several subproblems e.g. branching on a binary variable creates a problem in which the variable =0 and a problem in which it =1. You could then proceed and solve them recursively. The 'bounding' aspect of the technique consists of estimating bounds on the solutions that can be attained in the subproblem. If the subproblem can only yield bad solutions(compared to a previously found solution) you can safely skip the exploration of that part of the search space.

Best first tries to find a solution as fast as possible by looking at the most interesting part of the search space first (most interesting = estimate). It does not split the search space, only tries to reach a/the solution as fast as possible.

Both approaches try to skip the investigation of parts of the search space. Their use and efficiency depends on the problem setting. Best first requires you to specify a criterium for 'the most interesting solution to explore', which can sometimes be hard/impossible. Branch and bound is only interesting if the bound you can put on the subproblems are meaningful/not too broad. It depends on the problem you're considering...

Origin
  • 2,009
  • 5
  • 19
  • 19
  • What I understood is this: best-first search only considers the cost of reaching a state (i.e. the sum of the costs from the root state to that state) for ranking, but BB uses estimated minimum cost of having complete solutions via that state. Am I right? – Barpa Jun 26 '13 at 12:05
  • No, Best First tries to select the next-node-to-process using a global cost estimate and not only the current cost. Consider a navigation problem for which you could use Dijkstra to create shortest-path-trees. Only looking at the cost of reaching the current state is exactly what Dijkstra does by selecting the node with the lowest tentative distance to settle next. By applying Best First to it, you get A* as in A* you always select the node with the lowest total cost estimate. – Origin Jun 26 '13 at 13:12
  • Sorry, but I am more confused now. You say best-first select the next node using global cost estimate. Is not the global cost estimate same as global bound (lower or upper) branch and bound uses for comparison with the current state bound? – Barpa Jun 26 '13 at 15:27
  • It could be the same, depending on your problem setup. Keep in mind that Best first is a selection critirium ("which one of my current states am I going to investigate next") while branch and bound is more pruning based on previous results (states can be discarded if they can only lead to bad solutions when a better solution has already been found). As I said before, both approaches can sometimes be combined and are definitely not mutually exclusive – Origin Jun 26 '13 at 15:40
  • Good answer but some confusion in the comments. Remember that A* is an example of a best-first search algorithm. Best-first explores most promising nodes first based on the function that evaluates nodes, **f**. This function **f** can be composed of two parts, **g** (known sure value) and **h** (heuristic estimate). For A*, **f=g+h**. But you can also have a best-first algorithm that uses **f=g** only, or another best-first algorithm (often called "greedy", but this adjective has many meanings and is used in many contexts) that uses **f=h** only. – dolphin May 30 '14 at 00:59