Informed Search: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "== Problem 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. == Bounds Chart == 350px == Step Chart == 350px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40...")
 
No edit summary
Line 1: Line 1:
== Problem Description==
{{DISPLAYTITLE:Informed Search (Informed Search)}}
Informed search tries to reduce the amount of search that must be done by making
== Description ==  
intelligent choices for the nodes that are selected for expansion.


== Bounds Chart ==
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.
[[File:Informed_SearchBoundsChart.png|350px]]


== Step Chart ==
== Parameters ==  
[[File:Informed_SearchStepChart.png|350px]]


== Improvement Table ==
<pre>$b$: branching factor (the average number of successors per state)
{| class="wikitable" style="text-align:center;" width="100%"  
$d$: the depth of the solution (the shortest path)
!width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
$n$: total number of nodes</pre>
|-
 
| rowspan="1" | Exp/Factorial
== Table of Algorithms ==  
|
 
|
{| class="wikitable sortable" style="text-align:center;" width="100%"
 
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference
 
|-
 
| [[A* Algorithm (Informed Search Informed Search)|A* Algorithm]] || 1968 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/document/4082128/ Time] & [https://en.wikipedia.org/wiki/A*_search_algorithm: Space]
|-
| [[Bidirectional A* Algorithm (Informed Search Informed Search)|Bidirectional A* Algorithm]] || 2007 || $O(b^{(d/{2})})$ || $O(b^{(d/{2})$}) || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf Time]
|-
| [[Fringe Saving A* (FSA*) (Informed Search Informed Search)|Fringe Saving A* (FSA*)]] || 2008 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [http://idm-lab.org/bib/abstracts/papers/aamas09d.pdf Time]
|-
| [[Generalized Adaptive A* (GAA*) (Informed Search Informed Search)|Generalized Adaptive A* (GAA*)]] || 2008 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [http://idm-lab.org/bib/abstracts/papers/aamas08b.pdf Time]
|-
| [[Iterative Deepening A* (IDA*) (Informed Search Informed Search)|Iterative Deepening A* (IDA*)]] || 1985 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://linkinghub-elsevier-com.ezproxy.canberra.edu.au/retrieve/pii/0004370285900840 Time]
|-
| [[Jump Point Search (JPS) (Informed Search Informed Search)|Jump Point Search (JPS)]] || 2011 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [http://users.cecs.anu.edu.au.ezproxy.canberra.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf Time]
|-
| [[Lifelong Planning A* (LPA*) (Informed Search Informed Search)|Lifelong Planning A* (LPA*)]] || 2001 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf Time]
|-
| [[Simplified Memory-Bounded A* (SMA*) (Informed Search Informed Search)|Simplified Memory-Bounded A* (SMA*)]] || 1992 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.7839 Time]
|-
| [[Theta* (Informed Search Informed Search)|Theta*]] || 2010 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf Time]
|-
| [[Anytime Repairing A* (ARA*) (Informed Search Informed Search)|Anytime Repairing A* (ARA*)]] || 2005 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://papers.nips.cc/paper/2382-ara-anytime-a-with-provable-bounds-on-sub-optimality.pdf Time]
|-
| [[Time-Bounded A* (TBA*) (Informed Search Informed Search)|Time-Bounded A* (TBA*)]] || 2009 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://www.cs.du.edu/~sturtevant/papers/TBA.pdf Time]
|-
|-
| rowspan="1" | Polynomial > 3
| [[Greedy Best-First Search (Informed Search Informed Search)|Greedy Best-First Search]] || 1959 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://en.wikipedia.org/wiki/Breadth-first_search: Space]
|
|
|-
|-
| rowspan="1" | Cubic
| [[Incremental Heuristic Search ( Informed Search)|Incremental Heuristic Search]] || 1968 || $O(b^d)$ ||  || Exact || Deterministic || 
|
|
|-
|-
| rowspan="1" | Quadratic
| [[Block A* (Informed Search Informed Search)|Block A*]] || 2011 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://webdocs.cs.ualberta.ca/~holte/Publications/aaai11PeterYapFinal.pdf Time]
|
|
|-
|-
| rowspan="1" | nlogn
| [[D* (Informed Search Informed Search)|D*]] || 1994 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.3683 Time]
|
|
|-
|-
| rowspan="1" | Linear
| [[Field D* (Informed Search Informed Search)|Field D*]] || 2006 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://www.ri.cmu.edu/pub_files/pub4/ferguson_david_2006_3/ferguson_david_2006_3.pdf Time]
|
|
|-
|-
| rowspan="1" | logn
| [[Fringe (Informed Search Informed Search)|Fringe]] || 2005 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || 
|
|-
|
| [[Anytime Dynamic A* (ADA*) ( Informed Search)|Anytime Dynamic A* (ADA*)]] || 2005 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://www.ri.cmu.edu/publications/anytime-dynamic-a-an-anytime-replanning-algorithm/ Time]
|-|}
|-
| [[D* Lite ( Informed Search)|D* Lite]] || 2005 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://doi-org.ezproxy.canberra.edu.au/10.1109%2Ftro.2004.838026 Time]
|-
| [[Focused D* ( Informed Search)|Focused D*]] || 2005 || $O(b^d)$ || $O(b^d)$ || Exact || Deterministic || [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257 Time]
|-
|}
 
== Time Complexity graph ==
 
[[File:Informed Search - Time.png|1000px]]
 
== Space Complexity graph ==
 
[[File:Informed Search - Space.png|1000px]]
 
== Pareto Decades graph ==
 
[[File:Informed Search - Pareto Frontier.png|1000px]]

Revision as of 10:20, 15 February 2023

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

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Pareto Decades graph

Error creating thumbnail: Unable to save thumbnail to destination