人工智能--状态空间问题求解方法

ゝ一世哀愁。 2022-01-21 03:45 947阅读 0赞

### 文章目录 ###

*  状态空间问题表示
 *   *  状态
     *  操作
     *  状态空间
 *  状态空间问题的求解
 *  例子
 *   *  二阶梵塔问题
     *  MC问题（修道士与野人问题）

**状态空间法**是人工智能中最基本的问题求解方法，它所采用的 问题表示方法称为状态空间表示法。

状态空间法的基本思想是用 **“状态”和“操作”来表示和求解问题**。

# 状态空间问题表示 #

在状态空间表示法中，问题是用“状态”和“操作”来表示的。

## 状态 ##

状态是表示问题求解过程中每一步状况的数据结构。它可用如下形式表示：

S_k \ = \ \{S_{k0},S_{k1},...,S_{kn}\}

当对每一个分量都赋予确定的值时，就得到了一个具体的状态。

注：**任何一种类型的数据结构都可以用以描述状态**，只要它有利于问题求解，就可以选用。

## 操作 ##

操作也可以称为算符，它是把问题从一种状态转换为另一种状态的手段。

当对一个问题状态**使用某个可用操作时**，它将引起该状态中**某些分量值的变化**，从而使问题从一个具体状态变为另一个具体状态。

## 状态空间 ##

状态空间是由一个问题的全部状态，以及这些状态之间的相互关系所构成的集合，可用一个三元组：

(S,F,G)

来表示。其中，**`S`为问题所有初始状态的集合，`F`为操作的集合，`G`为目标状态的集合**。

状态空间也可用一个赋值的有向图来表示，该有向图为状态空间图。节点表示问题的状态，有向边表示操作。

# 状态空间问题的求解 #

**所有以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空间法**。基本过程是：

1.  为问题选择适当的“状态”和“操作”的形式化描述方法
2.  从某个初试状态出发，每次使用一个“操作”，递增的建立起操作序列，直到达到目标状态为止

**此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解**。

# 例子 #

## 二阶梵塔问题 ##

![image][]

![image][image 1]

## MC问题（修道士与野人问题） ##

![image][image 2]  
![image][image 3]

[image]: http://note.youdao.com/yws/res/13722/824B0566FC724B12A3E0EBB73E137577
[image 1]: http://note.youdao.com/yws/res/13725/2965C4FCC5BF4621BED6C1E7FFE14C8D
[image 2]: http://note.youdao.com/yws/res/13730/4AD0AB8883F8409BA345A0EA300CB78B
[image 3]: http://note.youdao.com/yws/res/13734/CC53B1703F6D4F068FB745DFE858F982

发表评论取消回复

表情：

评论列表（有 0 条评论，947人围观）

还没有评论，来说两句吧...

相关阅读

相关几何算法--python求解空间线段交点坐标

【问题】已知两个线段的端点坐标分别为(x1, y1, z1)、(x2, y2, z2)；(x3, y3, z3)、(x4, y4, z4)，求它们的交点坐标？已知线段

我会带着你远行/ 2023年10月07日 09:20/ 0 赞/ 42 阅读

相关（C++）“韩信点兵”问题的求解方法

有一队士兵，确切人数不知，但若每３人一组，则余２人；每５人一组，余３人；每７人一组，余５人；每１１人一组，余４人。请解答下列问题： ⑴至少有多少人？ ⑵若已知人数在

一时失言乱红尘/ 2023年02月26日 05:28/ 0 赞/ 45 阅读

相关卷积法求解系统的零状态响应_《现代控制理论基础》— 4 状态空间的数学模型（二）...

![9a4d9bc7a7b97548f863862b05a00728.png][] 今天对系统的运动会给分析开展介绍，这部分主要任务是通过状态方程得到状态转移矩阵、状态响应和

悠悠/ 2023年01月02日 01:18/ 0 赞/ 183 阅读

相关传递函数化为状态空间表达式

G ( s ) = N ( s ) D ( s ) G(s)=\\frac\{N(s)\}\{D(s)\} G(s)=D(s)N(s) 的串联分解形式可控标准型

刺骨的言语ヽ痛彻心扉/ 2022年12月02日 12:26/ 0 赞/ 76 阅读

相关求解时间复杂度和空间复杂度

时间复杂度算法效率时间复杂度评估算法运行时间大O渐进表示法最好/最坏/平均时间复杂度实例：

绝地灬酷狼/ 2022年11月04日 15:29/ 0 赞/ 235 阅读

相关现实问题求解

题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可提成7

本是古典何须时尚/ 2022年05月21日 05:14/ 0 赞/ 261 阅读

相关《人工智能》第三章：搜索算法问题求解

问题求解算法的性能完备性：当问题有解时，这个算法是否能保证找到解？最优性：搜索策略是否能找到开销最小的最优解？时间复杂度：找到解需要花费多长时间？

不念不忘少年蓝@/ 2022年02月16日 08:38/ 0 赞/ 1248 阅读

相关人工智能--状态空间的盲目搜索

文章目录状态空间的盲目搜索广度优先算法算法描述：总结深度优先算法

小灰灰/ 2022年01月21日 10:53/ 0 赞/ 272 阅读

相关人工智能--问题规约求解方法

A\[toc\] 问题规约法是不同于状态空间法的另一种形式化方法，其基本思想是对问题进行分解或变换，将它转换为一系列较简单的问题。问题的分解与等价变换分解

ゝ一世哀愁。/ 2022年01月21日 05:55/ 0 赞/ 855 阅读

相关人工智能--状态空间问题求解方法

文章目录状态空间问题表示状态操作状态空间状态空间问题的求解例子二阶梵塔问题

ゝ一世哀愁。/ 2022年01月21日 03:45/ 0 赞/ 948 阅读