(1) 阅读 (1180)

状态空间搜索 编辑

词条创建者 匿名用户

状态空间搜索

编辑

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

表示法

编辑

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

状态空间搜索算法的例子

编辑

无信息的搜索

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

状态空间搜索

传统的深度优先搜索

编辑

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

知情/启发式深度优先搜索

编辑

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


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/176520/

发表评论

登录后才能评论

词条目录
  1. 状态空间搜索
  2. 表示法
  3. 状态空间搜索算法的例子
  4. 无信息的搜索
  5. 传统的深度优先搜索
  6. 知情/启发式深度优先搜索

轻触这里

关闭目录

目录