Question 1261 – Algorithms

           List 1					   List 2
(a) Greedy Best-first Search         	 (i) Selects a node for expansion if optimal path to 
                                             that node has been found
(b) A* Search	          		(ii) Avoids substantial overhead associated with 
                                             keeping the sorted queue of nodes
(c) Recursive Best-First Search        (iii) Suffers from excessive node generation
(d) Iterative-deepening A* Search   	(iv) Time complexity depends upon the quality of 
                                             heuristic

→ Greedy Best-first Search: Selects a node for expansion if optimal path to that node has been found. Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. Best-first search as estimating the promise of node n by a “heuristic evaluation function f(n) which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.”
→ A* Search: Time complexity depends upon the quality of heuristic.

→ Recursive Best-First Search: Suffers from excessive node generation. RBFS depends on how widely the promising nodes are separated in the search tree, and is harder to anticipate.
→ Iterative-deepening A* Search: Avoids substantial overhead associated with keeping the sorted queue of nodes.