View source for Draft:Informed search

{{AfC submission|t||ts=20240921032520|u=So9q|ns=118|demo=}}
{{orphan|date=September 2024}}
{{rough translation|date=September 2024}}
'''Informed search''' (also known as '''heuristic search''') is a strategy of [[State space search|searching for solutions in a state space]] that uses knowledge specific to the given problem. Informed methods usually provide a more efficient search compared to [[Uninformed search method|uninformed methods]].

Information specific to the problem is formulated as a ''heuristic function''. At each step of the search, the heuristic function evaluates alternatives based on additional information to decide which direction the search should continue<ref name="aima2">{{cite book
 | author = Stuart Russell, Peter Norvig
 | chapter = Constructing Admissible Heuristic Functions
 | title = Artificial Intelligence: A Modern Approach
 | edition = 2nd
 | place = M.
 | publisher = Williams
 | year = 2006
 | pages = 170–173
 | isbn = 5-8459-0887-6
}}</ref>.

== Heuristic Functions ==
In the context of state space search, a '''heuristic function''' ''h''(''n'') is defined on the nodes of a '''search tree''' as follows:
:: ''h''(''n'') = an estimate of the cost of the least expensive path from node ''n'' to a goal node.

If ''n'' is a goal node, then ''h''(''n'') = 0.

The node to expand is selected based on the '''evaluation function''' ({{langx|en|evaluation function}})
:: ''f''(''n'') = an estimate of the cost of the least expensive solution path passing through node ''n'',
:: ''f''(''n'') = ''g''(''n'') + ''h''(''n''),

where the function ''g''(''n'') determines the cost of the path already traversed from the start node to node ''n''.

[[File:Heuristics.png|360px|thumb|Values of the functions along the optimal solution<br />f1(n) = g(n) + h1(n) – inadmissible heuristic<br />f2(n) = g(n) + h2(n) – admissible, but not consistent<br />f3(n) = g(n) + h3(n) – consistent heuristic]]

If the heuristic function ''h''(''n'') never overestimates the actual minimum cost of reaching the goal (i.e., it is a lower bound of the actual cost), such a function is called '''admissible'''.

If the heuristic function ''h''(''n'') satisfies the condition
:: ''h''(''a'') ≤ ''cost''(''a'', ''b'') + ''h''(''b''),
where ''b'' is a successor of ''a'', then this function is called '''consistent'''.

If ''f''(''n'') = ''g''(''n'') + ''h''(''n'') is the evaluation function, and ''h''(''n'') is a consistent function, then the function ''f''(''n'') is monotonically non-decreasing along any explored path. Therefore, consistent functions are also called '''monotonic'''.

Any consistent function is admissible, but not every admissible function is consistent.

If ''h''<sub>1</sub>(''n''), ''h''<sub>2</sub>(''n'') are admissible heuristic functions, and for any node ''n'' the inequality ''h''<sub>1</sub>(''n'') ≥ ''h''<sub>2</sub>(''n'') holds, then ''h''<sub>1</sub> is a '''more informed''' heuristic, or '''dominates''' over ''h''<sub>2</sub>.

If there are admissible heuristics ''h''<sub>1</sub> and ''h''<sub>2</sub> for the problem, then the heuristic ''h''(''n'') = max(''h''<sub>1</sub>, ''h''<sub>2</sub>) is admissible and dominates each of the original heuristics<ref name="aima2" /><ref name="hsta" />.

=== Comparison of Heuristic Functions ===

When comparing admissible heuristics, the degree of informativeness and the spatial and temporal complexity of computing each heuristic are important. More informed heuristics can reduce the number of nodes expanded, although the cost may be the time required to compute the heuristic for each node.

The '''[[effective branching factor]]''' is the average number of successors of a node in the search tree after applying heuristic pruning methods<ref name="aima2" /><ref name="hsta" />. The effective branching factor can be used to judge the quality of the heuristic function used.

An ideal heuristic function (e.g., a '''[[lookup table]]''') always returns the exact values of the shortest solution length, so the search tree contains only optimal solutions. The effective branching factor of an ideal heuristic function is close to 1<ref name="aima2" />.

{{anchor|Examples}}

=== Search Problem Examples ===
[[File:15-puzzle-solvable.svg|240px|thumb|Sum of the Manhattan distances of all tiles from their target positions:<br />h<sub>m</sub>(n)=3+0+0+3+2+4+2+4+1+3+2+2+<br />+3+3+2=34.<br />The optimal solution consists of 50 moves.]]

Permutation puzzles are often used as models for testing search algorithms and heuristic functions, such as 3×3 <ref name="reinefeld_1993" /><ref name="kunkle_2001" />, 4×4 <ref name="korf_1985" /><ref name="culberson_schaeffer_1998" /><ref name="korf_schultze_2005" />, 5×5 <ref name="taylor_korf_1996" /><ref name="korf_2000" /><ref name="korf_felner_2002" />, 6×6 <ref name="felner_korf_hanan_2004" />, Rubik's Cube <ref name="korf_2000" /><ref name="korf_1997" />, and the Tower of Hanoi with four rods <ref name="felner_korf_hanan_2004" /><ref name="korf_felner_2007" />.

In the "15-puzzle," the heuristic ''h''<sub>''m''</sub>, based on Manhattan distance, can be applied. More specifically, for each tile, the Manhattan distance between its current position and its position in the initial state is calculated, and these values are summed.

It can be shown that this heuristic is admissible and consistent: its value cannot change by more than ±1 in a single move.

=== Constructing Heuristic Functions ===

==== Relaxed Problem ====
The heuristic function ''h''<sub>''m''</sub>, used to solve the "Fifteen Puzzle," represents a lower bound on the length of the optimal solution. Additionally, ''h''<sub>''m''</sub>(''n'') is the exact length of the optimal solution for the ''relaxed version'' of the puzzle, where tiles can be moved into occupied positions. The original puzzle has the constraint "no more than one tile per cell," which is not present in the relaxed version. A problem with fewer constraints on possible actions is called a '''relaxed problem'''; the cost of solving the relaxed problem is a valid heuristic for the original problem<ref name="aima2" />, as any solution to the original problem is also a solution to the relaxed problem.

==== Subproblem ====
A valid heuristic may be based on the cost of solving a '''subproblem''' of the original problem. Any solution to the main problem is simultaneously a solution to each of its subproblems<ref name="aima2" />.

A subproblem of the Fifteen Puzzle could be the problem of placing tiles 1, 2, 3, and 4 in their correct positions. The cost of solving this subproblem is a valid heuristic for the original problem.

{{anchor|PDB}}

=== Pattern Databases ===
[[File:15-puzzle-fringe.svg|240px|thumb|The "fringe" template (target configuration of the subproblem)<ref name="culberson_schaeffer_1998" />]]
Pattern databases<ref name="aima2" /> — a type of admissible heuristic based on the idea of storing the exact cost of solving each possible instance of a subproblem<ref name="aima2" /><ref name="culberson_schaeffer_1998" /><ref name="korf_1997" />.

An example of a template for the 15-puzzle is shown in the image on the right: the definition of the subproblem includes the positions of seven tiles in the first column and the first row. The number of configurations for this template is <math>\dfrac{16!}{8!}=518918400</math>. For each configuration, the database contains the minimum number of moves required to transform this configuration into the target configuration of the subproblem, as shown in the image. The database is constructed using the method of backward [[Breadth-first search|breadth-first search]]<ref name="hsta" /><ref name="culberson_schaeffer_1998" />.

{{anchor|Algorithms}}

== Search Algorithms ==

=== Best-First Search ===
'''Best-First Search''' is an approach in which the node for expansion is chosen based on an evaluation function ''f''(''n''). The node with the lowest evaluation is selected for expansion.

=== A* Search ===
'''A* Search''' is the most well-known variant of best-first search. It uses the evaluation function ''f''(''n'') of the cost of the least costly path to the goal passing through node ''n'':

: ''f''(''n'') = ''g''(''n'') + ''h''(''n''), where
:: ''g''(''n'') is the cost from the start node to node ''n'',
:: ''h''(''n'') is the estimated cost from node ''n'' to the goal.

If ''h''(''n'') never overestimates the cost to reach the goal (i.e., is admissible), then A* Search is optimal.

=== IDA* ===
'''Iterative Deepening A*''' (IDA*) is the application of the iterative deepening idea in the context of heuristic search.

The uninformed [[Uninformed search#IDDFS|iterative deepening algorithm]] stops expanding when the search depth ''d'' exceeds the current depth limit ''l''. The informed IDA* algorithm stops expanding when the evaluation ''f''(''n'') of the path cost through the current node ''n'' exceeds the current path cost bound ''bound''.

IDA* has minimal memory overhead compared to A* and a comparatively small (if a good heuristic is chosen) number of expanded nodes compared to IDDFS.

==== Pseudocode ====
<ref>Based on [http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html Lecture Notes: IDA*] {{webarchive|url=https://web.archive.org/web/20120622202730/http://www.apl.jhu.edu/~hall/AI-Programming/IDA-Star.html}}</ref>
  <span style="color:Green;">node</span>              ''current node''
  <span style="color:Green;">g</span>                 ''cost from root to node''
  <span style="color:Green;">f</span>                 ''estimated cost of the minimum path through node''
  <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">node</span>)           ''heuristic estimate of the cost from node to goal''
  <span style="color:OrangeRed;">'''cost'''</span>(<span style="color:Green;">node</span>, <span style="color:Green;">succ</span>)  ''path cost function''
  <span style="color:OrangeRed;">'''is_goal'''</span>(<span style="color:Green;">node</span>)     ''goal test function''
  <span style="color:OrangeRed;">'''successors'''</span>(<span style="color:Green;">node</span>)  ''node expansion function''

  '''procedure''' <span style="color:OrangeRed;">'''ida_star'''</span>(<span style="color:Green;">root</span>, <span style="color:OrangeRed;">'''cost'''</span>(), <span style="color:OrangeRed;">'''is_goal'''</span>(), <span style="color:OrangeRed;">'''h'''</span>())
    <span style="color:Green;">bound</span> := <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">root</span>)
    '''loop'''
      <span style="color:Green;">t</span> := <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">root</span>, 0, <span style="color:Green;">bound</span>)
      '''if''' <span style="color:Green;">t</span> = FOUND '''then return''' FOUND
      '''if''' <span style="color:Green;">t</span> = ∞ '''then return''' NOT_FOUND
      <span style="color:Green;">bound</span> := <span style="color:Green;">t</span>
    '''end loop'''
  '''end procedure'''

  '''function''' <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">node</span>, <span style="color:Green;">g</span>, <span style="color:Green;">bound</span>)
    <span style="color:Green;">f</span> := <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''h'''</span>(<span style="color:Green;">node</span>)
    '''if''' <span style="color:Green;">f</span> > <span style="color:Green;">bound</span> '''then return''' <span style="color:Green;">f</span>
    '''if''' <span style="color:OrangeRed;">'''is_goal'''</span>(<span style="color:Green;">node</span>) '''then return''' FOUND
    <span style="color:Green;">min</span> := ∞
    '''for''' <span style="color:Green;">succ</span> '''in''' <span style="color:OrangeRed;">'''successors'''</span>(<span style="color:Green;">node</span>) '''do'''
      <span style="color:Green;">t</span> := <span style="color:OrangeRed;">'''search'''</span>(<span style="color:Green;">succ</span>, <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''cost'''</span>(<span style="color:Green;">node</span>, <span style="color:Green;">succ</span>), <span style="color:Green;">bound</span>)
      '''if''' <span style="color:Green;">t</span> = FOUND '''then return''' FOUND
      '''if''' <span style="color:Green;">t</span> < <span style="color:Green;">min</span> '''then''' <span style="color:Green;">min</span> := <span style="color:Green;">t</span>
    '''end for'''
    '''return''' <span style="color:Green;">min</span>
  '''end function'''

{{anchor|MAStar}}

=== MA* ===
{{In progress|date=2016-11-30}}

{{anchor|SMAStar}}

=== SMA* ===
[[:en:SMA*|SMA*]]
{{In progress|date=2016-11-30}}

{{anchor|RBFS}}

=== RBFS ===
{{In progress|date=2016-11-30}}

== See also ==
* [[Uninformed search algorithm]]

== Notes ==
{{reflist|refs=
<ref name="hsta">{{cite book
 | author = Stefan Edelkamp, Stefan Schrödl
 | title = Heuristic search: theory and applications
 | url = https://archive.org/details/heuristicsearcht0000edel
 | publisher = [[Morgan Kaufmann Publishers]]
 | year = 2012
 | pages = 712
 | isbn = 978-0-12-372512-7
}}</ref>

<ref name="reinefeld_1993">{{cite journal
 | url = https://www.ijcai.org/Proceedings/93-1/Papers/035.pdf
 | author = Alexander Reinefeld
 | title = Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*
 | journal = International Joint Conference on Artificial Intelligence
 | year = 1993
}}</ref>

<ref name="kunkle_2001">{{cite journal
 | author = Daniel R. Kunkle
 | url = https://web.mit.edu/6.034/wwwbob/EightPuzzle.pdf
 | title = Solving the 8 Puzzle in a Minimum Number of Moves: An Application of the A* Algorithm
 | journal = Introduction to Artificial Intelligence
 | year = 2001
}}</ref>

<ref name="korf_1985">{{cite book
 | author = Richard E. Korf
 | title = Depth-first iterative-deepening: An optimal admissible tree search
 | year = 1985
}}</ref>

<ref name="culberson_schaeffer_1998">{{cite book
 | author = Joseph C. Culberson, Jonathan Schaeffer
 | title = Pattern Databases
 | year = 1998
}}</ref>

<ref name="korf_schultze_2005">{{cite book
 | author = Richard E. Korf, Peter Schultze
 | title = Large-Scale Parallel Breadth-First Search
 | year = 2005
}}</ref>

<ref name="taylor_korf_1996">{{cite book
 | author = Richard E. Korf, Larry A. Taylor
 | title = Finding Optimal Solutions to the Twenty-Four Puzzle
 | year = 1996
 | url = http://www.aaai.org/Library/AAAI/1996/aaai96-178.php
 | archivedate = 2015-09-10
 | archiveurl = https://web.archive.org/web/20150910194314/http://www.aaai.org/Library/AAAI/1996/aaai96-178.php
 }}</ref>

<ref name="korf_2000">{{cite book
 | author = Richard E. Korf
 | title = Recent Progress in the Design and Analysis of Admissible Heuristic Functions
 | year = 2000
}}</ref>

<ref name="korf_felner_2002">{{cite journal
 | author1 = Richard E. Korf |author2= Ariel Felner
 | title = Disjoint Pattern Database Heuristics
 | journal = Artificial Intelligence
 | year = 2002
 | volume = 134
 | issue = 1–2
 | pages = 9–22
 | doi = 10.1016/S0004-3702(01)00092-3
 | url = http://dl.acm.org/citation.cfm?id=512150
 | archivedate = 2019-05-07
 | archiveurl = https://web.archive.org/web/20190507175206/https://dl.acm.org/citation.cfm?id=512150
 }}</ref>

<ref name="felner_korf_hanan_2004">{{cite journal
 | author1 = Ariel Felner |author2= Richard E. Korf |author3= Sarit Hanan
 | title = Additive Pattern Database Heuristics
 | journal = Journal of Artificial Intelligence Research
 | year = 2004
 | url = http://www.aaai.org/Library/JAIR/Vol22/jair22-009.php
 | archivedate = 2021-12-01
 | archiveurl = https://web.archive.org/web/20211201071922/https://aaai.org/Library/JAIR/Vol22/jair22-009.php
 }}</ref>

<ref name="korf_1997">{{cite book
 | author = Richard E. Korf
 | title = Finding Optimal Solutions to Rubik's Cube Using Pattern Databases
 | year = 1997
}}</ref>

<ref name="korf_felner_2007">{{cite book
 | author = Richard E. Korf, Ariel Felner
 | title = Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem
 | year = 2007
}}</ref>

}}

== Literature ==
* {{cite book
 | author = Stefan Edelkamp, Stefan Schrödl
 | title = Heuristic search: theory and applications
 | url = https://archive.org/details/heuristicsearcht0000edel
 | publisher = [[Morgan Kaufmann Publishers]]
 | year = 2012
 | pages = 712
 | isbn = 978-0-12-372512-7
}}

* {{cite book
 | author = Stuart Russell, Peter Norvig
 | chapter = Constructing Admissible Heuristic Functions
 | title = Artificial Intelligence: A Modern Approach
 | edition = 2nd
 | place = M.
 | publisher = Williams
 | year = 2006
 | pages = 170–173
 | isbn = 5-8459-0887-6
}}

== External links ==
{{wikibooks|Algorithms}}

{{Draft categories|
[[Category:Artificial intelligence]]
[[Category:Heuristic algorithms]]
}}

{{Drafts moved from mainspace|date=September 2024}}