Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
3  
There are a lot of ways of determining "best" - your question might be better answered if you told us the heuristic you're using. For example, we could define "best" as "deepest", and then essentially get a depth-first search. –  Xodarap Oct 17 '12 at 16:41
    
Also, by which measure do you want to compare different algorithms? –  Raphael Oct 17 '12 at 20:06
    
I read this question in back exercises of "AI by Rich & Knight".I am looking for an answer in terms of time & space complexity.Please give an example, by taking your own heuristic function. –  abhi120 Oct 18 '12 at 8:29
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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