patternMinor
When would best first search be worse than breadth first search?
Viewed 0 times
searchthanbreadthworsewouldfirstwhenbest
Problem
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.
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.
Solution
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
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
Context
StackExchange Computer Science Q#6125, answer score: 6
Revisions (0)
No revisions yet.