Informed Search (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