Search code examples
artificial-intelligenceterminologybreadth-first-search

best-first Vs. breadth-first

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

Solution

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

    https://i.sstatic.net/m5EgX.png

    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!

    https://i.sstatic.net/8tMbh.png

    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!