状态空间表示法
状态空间表示法引入
- 状态空间表示法就是以 “ 状态空间 ” 的形式来表示问题及其搜索过程的一种方法。
- 状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。
问题状态空间的构成
状态
- 表示问题求解过程中不同时刻问题状况的数据结构。
- 一般用一组变量的有序集合表示，可形式地表示为： S k = { S k 0 , S k 1 , … , S k n } ( i = 0 , 1 , 2 , … , n ) S_{k} = \lbrace{S_{k0}, S_{k1}, …, S_{kn}}\rbrace(i=0,1,2,…,n) Sk={Sk0,Sk1,…,Skn}(i=0,1,2,…,n) 。
- 当对每一个分量 S k i S_{ki} Ski 都给以确定的值时，就得到了一个具体的状态。
算符
- 引起状态中某些变量发生变化，从而使问题由一个状态变为另一个状态的操作；
- 可分为走步、过程、规则、数学算子、运算符号或逻辑符号等。
- 例如：在产生式系统中，每一条产生式规则就是一个算符；而在下棋程序中，一个算符就是一个走步。
状态空间
- 状态空间：一个问题的全部状态及一切可用算符构成的集合。
- 常用一个三元组表示为：**(S, F, G)，其中，S为问题的所有初始状态集合；F为算符的集合；G为目标状态的集合**。
- 状态空间也可用一个有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示算符。
问题的解
- 从问题的初始状态集S出发，经过一系列的算符运算，到达目标状态。
- 由初始状态到目标状态所用算符的序列就构成了问题的一个解。
- 图的角度：从初始状态到目标状态的一条路径。
状态空间法表示问题的步骤
状态空间方法表示问题的步骤如下
- 定义状态的描述形式。
- 用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。
- 定义一组算符。使得利用这组算符可把问题由一种状态转变为另一种状态。
利用状态空间求解问题的过程
问题的求解过程就是不断把算符作用于状态的过程，具体可以描述为：
- 将适用的算符作用于初始状态，以产生新的状态；
- 再把一些适用的算符作用于新的状态，如此反复，直至产生的状态为目标状态；
- 由初始状态到目标状态所用算符构成的序列就是该问题的一个解。
注意：1. 最优解问题 2. 搜索策略问题
利用状态空间表示法解题示例
状态空间表示法简要小结
标签：
人工智能
本文转载自: https://blog.csdn.net/qq_45902301/article/details/125055544
版权归原作者 何处秋风悲画扇 所有， 如有侵权，请联系我们删除。
版权归原作者 何处秋风悲画扇 所有， 如有侵权，请联系我们删除。