6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search

Comparison of Search Techniques

Let $b$ = branching factor
$m$ = depth of search space
$d$ = length of solution

	DFS	BFS	UCS	IDS	Best	HC	Beam	A*	IDA*
Complete?	N	Y	Y	Y	N	N	N	Y	Y
Optimal?	N	N	Y	N	N	N	N	Y	Y
Heuristic	N	N	N	N	Y	Y	Y	Y	Y
Time	$b^m$	$b^d$	$b^m$	$b^d$	$b^m$	$m$	$m*n$	$b^m$	$b^m$
Space	$m$	$b^d$	$b^m$	$d$	$b^m$	1	$n$	$b^m$	$m$