Question

0

4.9kviews

Compare following informed searching algorithms based on performance measure with justification

written 7.4 years ago by

teamques10 ★ 64k

modified 23 months ago by

binitamayekar ★ 6.4k

Compare following informed searching algorithms based on performance measure with justification: Complete, Optimal, Time complexity and space complexity. - a. Greedy best first - b. A* - c. Recursive best-first (RBFS) -

Mumbai University > Computer Engineering > Sem 7 > Artificial Intelligence

Marks: 10 Marks

Year: May 2016

artificial intelligence

ADD COMMENT EDIT

1 Answer

Parameters	Greedy Best First	A*	Recursive best-first (RBFS)
Complete	No – can get stuck in loops, e.g., Iasi Neamt Iasi Neamt	Yes (unless there are infinitely many nodes with f ≤ f(G) )	Yes, similar to A*.
Optimal	No	Yes (depending upon search algo and heuristic property)	Yes, similar to A*.
Time Complexity	O(bm), but a good heuristic can give dramatic improvement	Exponential	The time complexity is difficult to characterize: it depends both on the accuracy of the heuristic function and on how often the best path changes as nodes are expanded. Each mind change corresponds to an iteration of IDA_, and could require many re-expansions of forgotten nodes to recreate the best path and extend it one more node.RBFS is somewhat more efficient than IDA_, but still suffers from excessive node regeneration.
Space Complexity	O(bm) --keeps all nodes in memory	Keeps all nodes in memory	O(bd)(linear space best-first search)