4
$\begingroup$

I am studying best first search as it compares to BFS (breadth-first search) and DFS (depth-first search), but I don't know when BFS is better than best-first search. So, my question is

When would best-first search be worse than breadth-first search?

This question is one of the back exercises in Artificial Intelligence by Rich & Knight, and it asks for an answer in terms of time & space complexity and allows you to define any heuristic function.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$

Best first search is different from BFS and DFS by that that it uses problem specific information to chose which node of the search tree to expand next. Best first search is informed search and DFS and BFS are uninformed searches.

In order to use informed search algorithm you need to represent the knowledge of the problem as heuristic function.

Best first search is sometimes another name for Greedy Best First Search, but it may also mean class of search algorithms, that chose to expand the most promising node based on an evaluation function(not necessary the same as the heuristics) such as Greedy Best First Search, A* and others.

If you meant Greedy Best First Search:

  • it is complete (finds a solution in finite graphs) like BFS

  • it is not optimal(to find the least cost solution) as DFS, but BFS is optimal when the cost of each arc is the same

  • in the worst case its time and space complexity is O($b^n$), where b is the branching factor and n is the maximal depth. For BFS time and space complexity is O($b^m$), where m is the depth of the shallowest goal. Greedy best-first search is in most cases better than BFS- it depends on the heuristic function and the structure of the problem. If the heuristic function is not good enough it can mislead the algorithm to expand nodes that look promising, but are far from the goal. Here is one simple example

Let all arcs have the same cost, S - start node, G - goal node and h-heuristic function

Here Greedy best-first search will expand : S,B,C,D,G

And BFS will only expand : S,A,B,G Greedy best-first search vs BFS

Improve this answer
$\endgroup$
0
1
$\begingroup$

  1. Breadth-first search is blind search(uninformed), it just keeps expanding all the leaves and checks if one of them is the goal.

  2. Best-first search is informed search, i.e, it has some information (heuristics) about the goal.For example if the information is about the distance from the current to state to the goal state, best first will choose the state with will reduce the distance by the maximum amount.

  3. Best-first search can get stuck in an infinite loop.

So, if you think the agent might stuck in an infinite loop or if you don't have any heuristics (information), then go with breadth-first search else go for best first search.

A better comparison would be between best-first and hill climbing search.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The point about getting stuck is an independent issue / not an innate character of best-first. Any so-called best-first search that has potential to get stuck (due to revisiting previously explored search space) can be modified to not get stuck (by memorising where it has explored). $\endgroup$
    – Apiwat Chantawibul
    Commented Jan 7, 2017 at 17:11
0
$\begingroup$

When the heuristic function, which Best first search algorithm using is not admissible or good enough, that may mislead the search. The heuristic function may lead the algorithm towards the infinite loop.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.