当前课程知识点：人工智能 > 第四章 约束满足问题 > 4.3约束满足问题的局部搜索方法 > Video
那么我们除了可以用标准的系统化的搜索算法
回溯搜索算法来解决这个约束满足问题之外呢
我们还可以用这个局部搜索算法来解决这个约束
满足问题
那么前面我们讲过这个局部搜索算法它
最大的一个好处就是它是对这个存储空间的要求
是非常低的
所以它可以用来解决这个规模很大 很复杂的问题
那么如果要运用这个局部搜索算法来解决这个约
束满足问题
那么我们这个约束满足问题的形式化和前面就会
不一样
也就是说这个时候我们约束满足问题里面我们状
态的描述呢
就是描述成一个完整的赋值
也就是说每一种赋值方案对应着一种状态
并且呢这种赋值方案呢并不是说一定要符合约束
就是说随便给这个变量赋一种值
没有必要要求它满足约束
那么任何一种赋值呢都是对应着一个状态
这是它的这个状态描述
然后呢这个动作的定义呢就定义成给这个已经赋
值的变量重新赋值
也就是说这个是它产生这个后续 产生这个儿子结
点的一个动作或者说后续函数
就是给已经赋值的变量重新赋值
那么你既然所有的变量都赋了值 那么你要选择给
哪一个变量重新赋值呢
这个的话呢 如果没有其它的原则就是随机选择一
个违反约束的变量给它重新赋值
使得它朝着目标前进 因为我们的目标就是找到一
个符合所有约束的赋值
所以这个就是变量的选择
那么我们在给变量重新赋值的时候我们这个赋值
方案
采用的是这个最少冲突启发式原则
什么叫最少冲突启发式原则呢
就是选择违反最少约束的值来给它赋值
也就是说我们选择一个变量重新赋值的时候
给它重新赋的值呢 这个重新赋的值呢
就是让它 使得它竟可能少的违反这些约束
那么当然不违反约束是最好了
那么这个就是叫做最少冲突启发式原则
那么来看一下这个用局部搜索算法来解决这个四
皇后问题
这是一个很简单的四皇后问题
那么我们的这个状态的描述就是一个完整的赋值
比如说像这里就是对应着一个状态
那么这个状态就是每一列摆一个皇后
那么我们总共有多少个状态呢
那么每一列比如说这一列我可以摆放在
四个行里面的每一行 所以它有四种选择
那么每一列都有四种选择它就是4的4次方
所以呢对于这个问题呢我们就有256个不同的状态
那么用局部搜索算法来做的话
它就是相当于在256个不同的状态去找一个 搜索
一个目标状态
那么我们的这个 定义的这个动作或者后续函数
就是你选择某一列的皇后将这个皇后在同一列内
移动
就是规定它只能在同一列内移动
因为最终的话这个皇后肯定是每一列有一个的
也就是说你不可能同一列放两个 那明显就不是目
标状态
所以这种方法也是使得这个问题简单化
所以呢这个就是这样子规定它的动作
那么目标测试的话就是 我的这种摆放 我的这种赋
值方案呢
就是使得所有的皇后都相互攻击不到
那么我们对于这个因为我们知道我们这个用局部
搜索
进行解决问题的时候 对它产生的后续我们是要评
估的
这个后续是不是比我当前状态要更好
更好的话它才会走向这个后续状态
如果它发现这个后续状态都比自己更差
那么它就会把这个局部最优点返回去的
所以它是有一个评估函数来评估这个状态的好坏
的
那么对于这个例子的话假设我们定义这个评估函
数为攻击到的皇后对数
也就是说如果你是定义成这么一个皇后对数的话
那么当然是评估函数值越小这个状态越好的
也就是说对于这个n状态这个评估函数值就定义成
能够攻击到的 能够攻击到的皇后对数
那么比如说像这里针对这个例子的话
那么我们形式化好了之后我们用局部搜索算法来
求解这个问题的话
都是任意给一个初始状态 比如说像这里任意给一
个初始状态
那么计算它的评估函数值它是等于5的
5的话就是有5对皇后互相攻击的到
请大家看到这里 每一条线就表示这是一对
这是一对 这是一对 这是一对 这是一对
所以总共有五对皇后可以互相攻击的到
所以它的评估函数值是等于5
然后呢它就利用我们刚才定义的动作或者后续函
数去产生这个后续
那么产生后续的话 它可能会产生很多个后续的
因为这个 我们看到这个动作就是将皇后在同一列
内移动
那么你可以选择在这个皇后移动 这个皇后移动
这个皇后移动 这个皇后移动
所以它产生的后续呢可以有很多种 比如说3
想这个可以移它3种 这里移它三种
这里移它三种 这里移它三种
所以其实上会有3的四次方个不同的儿子产生
那么你要看你用的是哪一种局部搜索算法
如果使用的是爬山搜索算法的话
它要从所有后续里面选一个最好的后续来
判断它是不是比当前状态要更好
那么假设我们最好的一个后续是这个
那么大家看到这个后续的话呢 其实上移的是这个
皇后
这个皇后它把 这个皇后从第二行移到了第一行
那么就变成了这么一个状态
那么这个状态它的评估函数值算出来是等于2的
也就是说只有这一对和这一对皇后互相攻击的到
那么这个算出来这个状态要比当前状态要更好
所以呢它就会走向 就像爬山一样就是走到这个
这个更好的这个后续状态来 所以当前状态就变成
这个状态了
也就是说我就是在前进了 在不断地前进 在爬山了
所以呢这个就到了这里 那到了这里之后这一步
那么假设在这一步的基础上我又去产生它的后续
那么产生它的后续呢假设我有一个最好的儿子是
这个儿子
这个儿子怎么产生的呢 就是将这个皇后移到这里
移到这里来了之后呢 这个最好的儿子的评估函数
值是等于零
也就是说没有任何一对皇后可以互相攻击的到
所以呢它发现这个儿子呢比我当前状态要更好
所以它肯定义无反顾的走向它
然后呢走向它之后呢 这个当前状态一看呢 已经是
一个目标状态
也就是说呢他都没有任何一对皇后可以攻击的到
所以他就返回去了 它就把这个状态呢就返回去了
就找到了一个全局最优点 就找到了一个解给你
那么所以这个局部搜索算法呢 看似它好像很盲目
的
就是只看到周边一点点提高 不断地改进当前状态
然后呢来找到 从而向目标前进来找到一个解给你
这个局部搜索算法就是 它的解决问题的能力是非
常强的
也就是说我们任意给定初始一个状态
这个局部搜索算法呢能够以很高的概率 也就是说
它很大的可能性 就是说我是不能保证百分百能帮
你解决问题
但是我的这个解决问题的概率是很高的
并且呢我解决问题的时间是固定的
是常数时间 也就是说我不会随着你这个问题的规
模增大
而指数级 平方级的增大
就是在常数时间内解决大规模的n皇后问题 可以解
决
像这个的话它可以解决皇后问题的规模
可以规模达到 看到没有这么一个数量级
这个数量级就是比前面的要多的多
前面我们讲了回溯搜索算法如果没有用那些提高
效率的启发式原则的话
它只能解决25皇后问题 用了那些启发式原则之后
它能解决1000皇后问题
那么像我们的这个局部搜索算法呢
它能够在常数时间内以很高的概率 解决大规模的n
皇后问题
也就是说这个n可以达到这么一个数量级
所以呢这个是局部搜索算法它的优势所在
那么我们来总结一下这一章的内容
我们知道这个约束满足问题是一类特殊的问题
也就是说它的状态是固定变量集的赋值来决定它
的这个状态
就是说不同的赋值呢对应着不同的状态
那么它的这个目标测试就是由这个变量之间的值
的约束来定义的
也就是说如果满足所有约束的赋值就是一个目标
那么这个是约束满足问题
那么我们讲到了用回溯搜索算法来解决约束满足
问题
那么回溯搜索算法其实上是一个深度优先搜索算
法
只不过是它要求这个深度优先搜索算法
这个结点产生后续的时候只给一个变量赋值
那么只给一个变量赋值的话 所以每个结点它最多
就是产生d个儿子
也就是说它的分支树最多就是d
所以呢这个是回溯搜索算法
那么回溯搜索算法呢
它可以使用变量选择和值选择策略来提高这个算
法的效率
也就是说如果没有运用这些启发式的这些策略呢
这个回溯搜索算法大概只能解决25皇后问题
那么应用了这些策略之后呢 它可以解决1000皇后
问题
所以呢这个算法的效率是提高了40多倍
那么我们还讲到了用前向检查来阻止这个
结点的这种无谓的搜索
也就是说可以来阻止这个导致将来失败的赋值
也就是说如果我能够
也就是说通过前向检查能够提前检测到这个赋值
呢是不可避免的失败的
所以呢提高这个算法的效率 这是前向检查
那么约束传播的话就能比前向检查更早的检测到
不可避免的失败
那么它在约束值和检测不相容性方面比前向检查
看的更远
也就是说它不单单是把这个约束从这个
赋值变量传到没有赋值的变量
还在没有赋值的变量之间传播 所以它比前向检查
看的更远
能够更早的检测到这种不可避免的失败
那么这个是这一章的内容
-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卡尔曼滤波器
-结课测试
