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

ゝ一世哀愁。 2022-01-21 03:45 896阅读 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 条评论，896人围观）

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

相关阅读

相关 matlab求解数学题,Matlab求解数学问题

Matlab 求解数学问题如果看完之后还是对相关函数的运用不甚了解，请务必使用 help 查看更详细的帮助文档！求解一元 n 次方程例：求解一元二次方程 x^2+2

朱雀/ 2023年01月13日 12:59/ 0 赞/ 163 阅读

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

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

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

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

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

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

相关现实问题求解

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

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

相关 BFS求解迷宫问题

以前学习C的时候，老师布置过一个拓展作业，实现迷宫的求解，当时没有学习数据结构，有点难以下手，现在学完数据结构已经将近2年，终于解决了这个问题。给定一个n\m大小的迷

女爷i/ 2022年05月20日 06:37/ 0 赞/ 222 阅读

相关快速幂问题求解

快速幂问题在一开始的ACM题还是很常见的。其中有一个很重要的数学公式：(a\b)%c=(a%c\b%c)%c。从这个公式中也可以推出(a\a)%c=(a%c\a%c)%c;

Dear 丶/ 2022年05月18日 11:14/ 0 赞/ 140 阅读

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

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

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

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

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

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

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

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

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

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

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

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