Informed Search (Informed Search)

From Algorithm Wiki
(Redirected from Family:Informed Search)
Jump to navigation Jump to 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

Informed Search - Time.png