State-space search

<h2 id="representation">Representation</h2>
<p>In state-space search, a state space is formally represented as a <a href="/facts/Tuple/BI1HIxL8">tuple</a> 
  
    
      
        S
        :
        ⟨
        S
        ,
        A
        ,
        Action
        ⁡
        (
        s
        )
        ,
        Result
        ⁡
        (
        s
        ,
        a
        )
        ,
        Cost
        ⁡
        (
        s
        ,
        a
        )
        ⟩
      
    
    {\displaystyle S:\langle S,A,\operatorname {Action} (s),\operatorname {Result} (s,a),\operatorname {Cost} (s,a)\rangle }
  
, in which:
</p>
<ul><li>
  
    
      
        S
      
    
    {\displaystyle S}
  
 is the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of all possible states;</li>
<li>
  
    
      
        A
      
    
    {\displaystyle A}
  
 is the set of possible actions, not related to a particular state but regarding all the state space;</li>
<li>
  
    
      
        Action
        ⁡
        (
        s
        )
      
    
    {\displaystyle \operatorname {Action} (s)}
  
 is the function that establishes which action is possible to perform in a certain state;</li>
<li>
  
    
      
        Result
        ⁡
        (
        s
        ,
        a
        )
      
    
    {\displaystyle \operatorname {Result} (s,a)}
  
 is the function that returns the state reached performing action 
  
    
      
        a
      
    
    {\displaystyle a}
  
 in state 
  
    
      
        s
      
    
    {\displaystyle s}
  
;</li>
<li>
  
    
      
        Cost
        ⁡
        (
        s
        ,
        a
        )
      
    
    {\displaystyle \operatorname {Cost} (s,a)}
  
 is the cost of performing an action 
  
    
      
        a
      
    
    {\displaystyle a}
  
 in state 
  
    
      
        s
      
    
    {\displaystyle s}
  
. In many state spaces, 
  
    
      
        a
      
    
    {\displaystyle a}
  
 is a constant, but this is not always true.</li></ul>
<h2 id="examples-of-state-space-search-algorithms">Examples of state-space search algorithms</h2>
<h3>Uninformed search</h3>
<p>According to Poole and Mackworth, the following are <i>uninformed</i> state-space search methods, meaning that they do not have any prior information about the goal's location.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<ul><li><a href="/facts/Depth-first_search/luxJKVph">Traditional depth-first search</a></li>
<li><a href="/facts/Breadth-first_search/2kulDXCx">Breadth-first search</a></li>
<li><a href="/facts/Iterative_deepening_depth-first_search/BezFNMTR">Iterative deepening</a></li>
<li><a href="/facts/Dijkstra%2527s_algorithm/ehun88jl">Lowest-cost-first search / Uniform-cost search (UCS)</a></li></ul>
<h3>Informed search</h3>
<p>These methods take the goal's location in the form of a <a href="/facts/Heuristic_function/PM2qkoa2">heuristic function</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> Poole and Mackworth cite the following examples as informed search algorithms:
</p>
<ul><li>Informed/Heuristic depth-first search</li>
<li><a href="/facts/Best-first_search/jaIwMxBE">Greedy best-first search</a></li>
<li><a href="/facts/A*_search/BXFmt6hz">A* search</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/State_space/H1vjb3LL">State space</a></li>
<li><a href="/facts/State-space_planning/qeJ4lrFP">State-space planning</a></li>
<li><a href="/facts/Branch_and_bound/mhALtav7">Branch and bound</a> – Method for making state-space search more efficient by pruning subsets of it</li></ul>

<ul><li>Stuart J. Russell and Peter Norvig (1995). <i>Artificial Intelligence: A Modern Approach</i>. Prentice Hall.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Poole, David; Mackworth, Alan. "3.5 Uninformed Search Strategies‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition". artint.info. Retrieved 7 December 2017. <a href="http://artint.info/2e/html/ArtInt2e.Ch3.S5.html" target="_blank">http://artint.info/2e/html/ArtInt2e.Ch3.S5.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Poole, David; Mackworth, Alan. "3.6 Heuristic Search‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition". artint.info. Retrieved 7 December 2017. <a href="http://artint.info/2e/html/ArtInt2e.Ch3.S6.html" target="_blank">http://artint.info/2e/html/ArtInt2e.Ch3.S6.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

State-space search open-in-new

State-space search