Informed Search

Description

Informed search tries to reduce the amount of search that must be done by making intelligent choices for the nodes that are selected for expansion.

Parameters

$b$: branching factor (the average number of successors per state)

$d$: the depth of the solution (the shortest path)

$n$: total number of nodes

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
A* Algorithm	1968	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time & Space
Bidirectional A* Algorithm	2007	$O(b^{(d/{2})})$	$O(b^{(d/{2})$})	Exact	Deterministic	Time
Fringe Saving A* (FSA*)	2008	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Generalized Adaptive A* (GAA*)	2008	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Iterative Deepening A* (IDA*)	1985	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Jump Point Search (JPS)	2011	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Lifelong Planning A* (LPA*)	2001	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Simplified Memory-Bounded A* (SMA*)	1992	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Theta*	2010	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Anytime Repairing A* (ARA*)	2005	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Time-Bounded A* (TBA*)	2009	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Greedy Best-First Search	1959	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Space
Incremental Heuristic Search	1968	$O(b^d)$		Exact	Deterministic
Block A*	2011	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
D*	1994	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Field D*	2006	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Fringe	2005	$O(b^d)$	$O(b^d)$	Exact	Deterministic
Anytime Dynamic A* (ADA*)	2005	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
D* Lite	2005	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time
Focused D*	2005	$O(b^d)$	$O(b^d)$	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff