Difference(s) between branch and bound and best-first search

Question

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?

Answer 1

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...