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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.