best-first Vs. breadth-first

Question

What is the difference between best-first-search and the breadth-first-search ? and which one do we call "BFS" ?

Answer 1

To answer your second question first:

which one do we call "BFS" ?

Typically when we refer to BFS, we are talking Breadth-first Search.

What is the difference between best-first-search and the breadth-first-search

The analogy that I like to consult when comparing such algorithms is robots digging for gold.

Given a hill, our goal is to simply find gold.

Breadth-first search has no prior knowledge of the whereabouts of the gold so the robot simply digs 1 foot deep along the 10-foot strip if it doesn't find any gold, it digs 1 foot deeper.

Best-first search, however, has a built-in metal detector, thus meaning it has prior knowledge. There is, of course, the cost in having a metal detector, and cost in turning it on and seeing which place would be the best to start digging.

Best-first search is informed whereas Breadth-first search is uninformed, as in one has a metal detector and the other doesn't!

Breadth-first search is complete, meaning it'll find a solution if one exists, and given enough resources will find the optimal solution.

Best-first search is also complete provided the heuristic — estimator of the cost/ so the prior knowledge — is admissible — meaning it overestimates the cost of getting to the solution)

I got the BFS image from http://slideplayer.com/slide/9063462/ the Best-first search is my failed attempt at photoshop!

Answer 2

Thats 2 algorithms to search a graph (tree).

Breadth first looks at all elements(nodes) of a certain depth, trying to find a solutuion (searched value or whatever) then continous one level deeper and looks at every node and so on.

Best first looks at the "best" node defined mostly by a heuristic, checks the best subnode of that node and so on.

A* would be an example for heursitic (best first search) and its way faster. But you need a heuristic what you wouldn't need for breadth search.

Creating a heuristic needs some own effort. Breadth first is out of the box.