当前课程知识点：人工智能 > 第二章 无信息搜索策略 > 2.1.2问题形式化 > Video
那么我们问题的形式化一般是由四个组成部分来
进行形式化
第一个组成部分就是来描述它的初始状态
也就是根据它的当前感知到自己现在处于一种什
么样的状态
第二个组成部分就是智能体能够执行的动作是什
么
或者说叫后续函数
我们在后面讲到搜索算法的时候更多的是应用
会用到后续函数这个概念
也就是说它在当前状态下执行某个动作会产生怎
么样的后续状态
后续的意思也就是当前状态执行些动作之后产生
后续状态，所以它叫后续函数
然后第三个方面就是我们如何来判断智能体已经
达到了目标状态
那么这个目标测试可以是显式的
也就是说我就给出一些目标状态的集合
那么你去匹配你这个状态是不是在这些目标状态
里面
是的话那就是到达了一个目标状态，不是的话就
不是
还有一种目标测试方法是隐式的
也就是说它只是告诉你一些目标状态所具有的一
些性质
比如说下棋的时候“将死”就是一种目标状态
但是“将死”只是一种性质
那么你要判断你当前的这个状态是不是“将死”，符
合这么一种标准
那么你才能知道是不是到达了目标状态
第四个组成部分就是路劲代价（路劲耗散）
这个路劲代价的意思就是
我每执行一个动作带来的消耗（代价）是多少
或者是我从初始状态出发到达当前这个状态
它执行过的动作，走过的这些路，所引起的耗散
是多少
一般的话只要给出单步代价
也就是说从一个状态到达它的一个后续状态
一个动作所产生的代价，定义出来就行了
那么我们的代价函数是可加的
问题形式化就是这四个部分组成的
那么我们这个问题的解就是找到一个从初始状态
到达目标状态的动作序列
那么当然你可以算出这个解的代价
就是从初始状态到目标状态所执行的动作的单步
代价的累加和
那么解的话有最优解的概念
最优解的概念就是在所有解的代价中这个解的代
价是最小的
这是一个真快吸尘器的状态空间图
所谓的状态空间图就是智能体所能达到的所有状
态的集合就是一个状态空间
这个状态空间，状态与状态之间如何来转换呢？
可以通过动作，或者说后续函数来实现
所以这些动作和状态就能构成一个图或者说一个
网络
结点我们用状态来表示，边用来表示动作
就是状态与状态之间通过什么样的动作来进行转
换
来形成一个状态空间图
那么像真空吸尘器世界空间图就是这么一个
因为我们只考虑智能体的位置以及灰尘的位置
所以智能体，要嘛在A，要嘛在B，所以它有两种
可能
那么灰尘的位置有四种可能
所以乘在一起就有八种不同的状态
那么这八种不同的状态就形成了真空吸尘器世界
的状态空间
那么这个状态空间，不同的状态之间如何转换
通过什么样的动作能够转换
通过这些弧线这些边连起来
所以这个真空吸尘器世界这个问题的形式化
我们的状态是这样描述的
机器人的位置以及灰尘的位置来描述一种特定的
状态
比如说这个就是一种状态
A、B格子都有灰尘，机器人在A格子里面，这是
一个状态
那么这个智能体他能做的就是向左移动向右移动
以及吸的动作
比如说要到达这个状态的话，只要它向右移动就
能到达这个状态
这个状态到达这个状态只要智能体向左移动就能
到达这个状态
那么这个状态到达它自己只要向左移动就能在这
个状态维持不动
那么我们的目标测试就是，希望所有的位置都不
脏
那么像指的这两个都是目标，也就是说智能体就
是要使得房间都不脏
路径代价可以定义成每做一个动作计代价1
比如说它每移动一下计代价为1，每吸一下也计代
价为1
那么你就可以找到一个从所指状态到达另一所指
状态的一个动作序列，让他实现目标
但是找到的动作序列不唯一，每一个动作序列，
每一个解都有一个路径代价
当然，最优解就是希望这个路径代价是最小的
那么第二个例子是八数码问题
这个八数码问题是一个滑块游戏
也就是说我们给一个初始状态，这些数字板块是
这样摆放的
希望你通过板块的移动来达到这种目标状态
也就是说这些数字板块这样摆放
那么像这么一个八数码问题它的状态应该怎么样
来描述呢？
也就是说这个问题应该如何形式化呢？
那么这个状的描述我们可以，每一种数字块的摆
放情况就是一种状态
比如说我们的空格和八个数字
第一个它可以摆放在九个格子的任何一个
第二个可以摆放在八个格子中的任何一个
接下来第三个可以摆放在七个格子中的任何一个
所以它的状态空间应该是有9的阶乘个不同的状态
构成
那么状态与状态之间如何转换，也就是说它可以
执行的动作是什么呢？
这个游戏它移动的是数字块，实际上实现的效果
就是这个空格在移动
所以你考虑的是移动数字块这个实际的动作，那
么你就要定义很多种动作
也就是说八个板块都有四种动作来执行，就要32
种动作来执行
如果你从它实现的效果来定义的话就只要定义四
种动作
就是这个空格向上、向下、向左、向右移动
这样的话就会使得这个问题简单得多
那么第三个目标状态的形式化呢
在这里我们的目标状态是给定的
也就是说只要去判断这个状态是不是这样的一种
摆放情况
就可以判断的出来这个状态是不是到达了目标
路径代价在这里可以这样定义每移动一步，代价
就加一
那么你当然是希望找到一种游戏方案
使得从初始状态到达目标状态移动数字块最少的
一种游戏方案
这么一种动作序列去玩就是它的最优解
-1.1 人工智能概念
-第一章 绪论--1.1 人工智能概念
-1.2 什么是理性智能体
--1.2理性智能体
-第一章 绪论--1.2 什么是理性智能体
-2.1.1问题求解智能体
-第二章 无信息搜索策略--2.1.1问题求解智能体
-2.1.2问题形式化
--Video
-2.1.3 树搜索算法
--Video
-第二章 无信息搜索策略--2.1.2问题形式化
-2.1.4树搜索算法的实现
--Video
-2.2.1搜索策略
--Video
-第二章 无信息搜索策略--2.1.3树搜索算法
-2.2.2宽度优先搜索
--Video
-2.2.3一致代价搜索
--Video
-第二章 无信息搜索策略--2.1.4树搜索算法的实现
-2.3.1深度优先搜索
--Video
-2.3.2有限深度搜索
--Video
-2.3.3迭代深入搜索
--Video
-第二章 无信息搜索策略--2.2.2宽度优先搜索
-2.3.4迭代深入深度搜索性能分析
--Video
-2.4无信息搜索策略小结
--Video
-第二章 无信息搜索策略--2.2.3一致代价搜索
-第二章 无信息搜索策略--2.3.1深度优先搜索
-第二章 无信息搜索策略--2.3.2有限深度搜索
-第二章 无信息搜索策略--2.3.3迭代深入搜索
-第二章 无信息搜索策略--2.3.4迭代深入深度搜索性能分析
-第二章 无信息搜索策略--2.4无信息搜索策略小结
-3.1贪婪搜索算法
--Video
-3.2.1A星搜索算法
--Video
-第三章 有信息搜索策略--3.2.1A星搜索算法
-3.2.2A星搜索算法的最优性
--Video
-3.2.3可采纳的启发式函数
--Video
-第三章 有信息搜索策略--3.2.2A星搜索算法的最优性
-3.3爬山搜索算法
--Video
-3.4模拟退火搜索算法
--Video
-第三章 有信息搜索策略--3.2.3可采纳的启发式函数
-3.5遗传算法
--Video
-第三章 有信息搜索策略--3.3爬山搜索算法
-第三章 有信息搜索策略--3.5遗传算法
-4.1.1什么是约束满足问题
--Video
-第四章 约束满足问题--4.1.1什么是约束满足问
-4.1.2约束满足问题的标准搜索形式化
--Video
-4.2.1回溯搜索算法
--Video
-第四章 约束满足问题--4.1.2约束满足问题的标准搜索形式化
-4.2.2回溯搜索的变量赋值顺序策略
--Video
-4.2.3回溯搜索的前向检查及约束传播
--Video
-第四章 约束满足问题--4.2.1回溯搜索算法
-4.2.4 AC-3弧相容算法
--Video
-4.3约束满足问题的局部搜索方法
--Video
-第四章 约束满足问题--4.2.2回溯搜索的变量赋值顺序策略
-第四章 约束满足问题--4.2.3回溯搜索的前向检
-第四章 约束满足问题--4.3约束满足问题的局部搜索方法
-5.1博弈及极小极大值概念
--Video
-5.2极小极大值决策算法
--Video
-第五章 对抗搜索--5.2极小极大值决策算法
-5.3.1剪枝的概念
--Video
-5.3.2 alpha-beta算法
--Video
-5.3.3 alpha-beta剪枝示例
--Video
-5.4 不完美的实时决策
--Video
-第五章 对抗搜索--5.3.3 alpha-beta剪枝示例
-第五章 对抗搜索--5.4 不完美的实时决策
-6.1不确定性量化
--Video
-第六章 不确定性推理--6.1不确定性量化
-6.2使用完全联合分布进行推理
--Video
-6.3贝叶斯规则及其应用
--Video
-6.4贝叶斯网络推理
--Video
-第六章 不确定性推理--6.2使用完全联合分布进行推理
-6.5隐马尔可夫模型
--Video
-6.6卡尔曼滤波器
--6.6
-第六章 不确定性推理--6.4贝叶斯网络推理
-第六章 不确定性推理--6.3贝叶斯规则及其应用
-第六章 不确定性推理--6.6卡尔曼滤波器
-结课测试
