5
$\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.

$\endgroup$
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 infored 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 neccessery the same as the heuristics) such as Greedy Best First Search, A* and others.

If you meen Greedy Best First Search:

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

  • 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

$\endgroup$
  • $\begingroup$ The link to the "Greedy Best First Search" is broken. It would be nice if you could fix this problem by maybe referring to another (good) article/paper. $\endgroup$ – nbro Jan 6 '17 at 19:15
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.

$\endgroup$
  • 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 Jan 7 '17 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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