状态空间搜索

状态空间搜索是计算机科学领域使用的一个过程，包括人工智能（AI），其中考虑了一个实例的连续配置或状态，目的是找到一个具有期望属性的目标状态。问题通常被建模为一个状态空间，即一个问题可能处于的一组状态。状态集形成一个图，如果有一个操作可以将xxx个状态转化为第二个状态，那么两个状态就会连接起来。状态空间搜索通常不同于传统的计算机科学搜索方法，因为状态空间是隐含的：典型的状态空间图太大，无法生成并存储在内存中。相反，节点是在探索的过程中产生的，并且通常在之后被丢弃。一个组合搜索实例的解决方案可能包括目标状态本身，或从某个初始状态到目标状态的路径。

在状态空间搜索中，状态空间被正式表示为一个元组S:⟨S,A,Action(s),Result(s,a),Cost(s,a)⟩。

根据Poole和Mackworth的说法，以下是无信息的状态空间搜索方法，意味着它们没有任何关于目标位置的先验信息。

广度优先搜索迭代深化最低成本优先搜索/统一成本搜索（UCS）这些方法以启发式函数的形式获取目标的位置。Poole和Mackworth引用了以下例子作为知情搜索算法。

贪婪式最佳优先搜索A*搜索