当前课程知识点：人工智能 > 第四章 约束满足问题 > 4.2.4 AC-3弧相容算法 > Video
前面我们讲了弧相容是约束传播的一种方法
那么这里我们来讲一下弧相容算法AC-3 也就是弧
相容的实现
那么AC就是弧相容英文单词的首字母
这个算法的输入是约束满足问题的形式化
也就是变量是哪些 变量的取值范围是哪些 约束是
哪些
然后它返回的同样也是约束满足问题的形式化
只不过可能这些变量的取值范围缩小了
也就是说它 弧相容检查它就是对这些变量的取值
范围进行一个修订
使得所有的约束弧都是相容的
所以呢它返回的是这么一个结果
那么我们来看一下它的输入呢就是我们的约束满
足问题
也就是说它这些约束呢都是一些二元约束
那么假设这个约束满足问题呢有n个变量
那么它定义了一个局部的变量就是这个队列
这个队列呢里面放了什么东西呢 放的是这些约束
弧
就是所有的约束弧就是放在这个队列里面
然后呢一开始的时候呢 就是所有的约束弧都在里
面 都放在里面
也就是说我根据这个问题的形式化 我知道有多少
个约束弧
那么它有方向性的 也就是说一条边包含两条约束
弧在里面
那么我们就开始进入这个循环检查
那么它要检查这个所有的约束弧
也就是说它要这个约束弧队列里面如果不是空的
话它就要一直进行下去
那么我们来看一下 那么也就是说队列里面其实上
是存储的是还没有检查的约束弧
那么如果检查是相容的话 那么它就会从这个队列
里面移出去
那么所以呢这个循环要进行到这个队列空为止
所以我们来看到 它首先就从这个队列里面移出来
一个进行检查
也就是说 我们来看到 比如说它移出来这个弧呢
Xi到Xj的一个有向弧 一个有向约束弧
那么我们来看一下它就开始呢去检查这条弧 它是
不是相容的
那么大家看到这里 也就是说这个检查这条弧是不
是相容的
它用了 定义了另外一个函数来负责进行检查
检查这个弧相容性的这个函数它的返回值是一个
bool值 就是真或者假
那么如果它返回一个真 那么它才会做下面的事情
那么我们首先来看一下它检查这条弧是不是相容
的
这个函数到底实现了什么样一个功能 我们来看到
它的函数名叫做remove 就是移掉
inconsistent 就是不相容的值
他取名叫做移掉不相容的值
因为你要把一个 检查这个弧的相容性的时候
我们知道如果它是不相容的 我们要把它变成相容
的
我们是要把这个Xi里面的有一些值是要删掉的
才能把一条不相容的弧变成相容的 所以它取的名
字是这么一个名字
那么这个函数呢它返回的是一个bool值
它返回真的时候是什么时候发生呢
就是当且仅当你发生了 这个Xi发生了这个删除合
法值的情况下
它就会返回真 如果你这条弧本身就是相容的
也就是说我本身就是相容的 那么它就会返回一个
假
所以这个是这个函数的返回值
那么来看到检查这个弧的相容性是做了一些什么
工作
首先它设了一个变量叫做remove的这么一个旗标
变量
就是一开始就是给它赋一个初始值就是假
（false）就是还没有发生
那么来看一下就是它整个的这个函数实现呢
就是这个定义 就是弧相容的一个定义一个
完全实现就是按照定义来实现的
就是对于这个Xi的取值范围 因为我们有前向检查
表
知道这个里面记录了它能够取值的合法赋值
那么对于它的每一个合法赋值我都要去检查Xj也就
是它的终点
Xj有没有一个对应的值 使得它们两个之间这种值
是满足Xi到Xj之间的这种约束的
那么我们来看到也就是说每个值我们都要检查
那么如果对于Xi的某一个值X
在Xj里面不存在一个值使得xy这一种赋值方案满
足它们之间的约束的话
那么就意味着这个弧是不相容的 那要让这个弧变
得相容
我没有办法 我只能把X呢 就这种值呢 从Xi的合法
值里面取值范围里面删掉
那么一旦发生了删除工作呢 这个旗标就变成true
了
就意味着呢我发生了这个某个变量的这个
合法赋值呢 剩余合法赋值呢发生了改变
那么我们前面讲过 一旦它发生了改变 那么它的邻
居变量 它的那个相容性就要重新检查
所以呢它这个remove这个旗标马上变成true了 这
个意思
所以呢对于它的这个Xi 这个起点的Xi的每一个合
法取值呢 我都要去检查
如果找不到对应的Y值满足约束的话 那么这个值
是要删掉
如果找得到这个检查就通过 那么所有的这个
合法值我都检查完毕之后呢 我就把这个旗标返回
去
是本身原来就相容的话 那么这个remove它就会是
false
如果这条弧是不相容的 我通过删除这个Xi的取值
来把它变得相容的
这个remove就会使true 所以呢它就返回这么一个
信息给你
那么大家看到这里 那么返回来之后呢 那么我队列
里取出来的这条弧
返回来 我去检查的结果返回来之后呢
我根据它返回来是true还是false来做相应的操作
如果返回来是false 那就意味着我没有删掉Xi的任
何值
这条弧本身就是相容的
那么去取弧相容检查队列里面的下一条弧 拿出来
检查
也就是说它没有影响到任何其他人 这条弧相容检
查已经通过了
那么如果它返回来的是true 那就意味着这条弧本
身是不相容的
我通过删除Xi的值 把它变得相容了
那么你尽然删掉了这个Xi的值 那么就会导致
有一些弧本来我原来检查是相容的
那么变得不相容了
所以呢你需要把那些弧重新加到队列里来进行检
查
那么是哪些弧呢 就是这些弧
就是这个和我们的这个Xi相邻的这些邻居变量
这些邻居变量作为起点到我Xi的弧需要重新检查的
所以呢就把这些弧全部加到队列里面去
让它放到后面慢慢子下一次重新来检查
那么这个就是我们的整个的弧相容算法
那么为什么是这样子的弧要重新检查呢
根据我们的定义我们就知道了 如果你的Xi这个值
发生了变化
那么本身对于我们的弧相容定义我们知道
Xk本来如果原来我赋某一种值 我Xi是找得到一个
值来合法对应的
但是你Xi删掉了之后我可能就找不到了
所以呢只有这种Xk到Xi的这样的弧需要重新去检
查
那么Xi到其他的结点的这种 我是不要检查的
因为我Xi作为起点的这种弧
如果它的取值少的话 这个弧相容会更加相容
因为我们的定时是对应它的每一种取值
这个Xj呢要有一个对应的值和它对应
所以呢我们只需要检查它的邻居结点到Xi的这些弧
重新检查
那么这个是这个弧相容算法的一个伪代码
所以大家来看一下算法的时间复杂度到底是一个
什么样的级别
首先看到这里 也就是说我们到底需要检查多少条
弧
也就是说这个队列里面最多会有多少条弧需要检
查
也就是说我们有n个变量 n个变量的话呢
大家想一下 也就是说它最多的约束弧就是
n（n-1）
也就是说n平方个数量级的弧进来
那么本身 本来就是最多有这么多个弧进来
那么大家想一下 但是呢我们就发现有一些弧呢它
需要重复检查
那么大家想一下每一条弧最多会重复多少次呢
也就是说每一条弧它的终点每删除一个值
它可能就要重复一次
那么每一个变量它的可能取值最多就是d
那么它最多就是删除d次
那么所以每一条弧呢最多就重复检查d次
所以呢我们这个队列里面 它的这个弧的
需要检查的弧的数量级最大就是n平方乘以d
那么这个是这个弧这个数量级就是n平方乘以d
那么弧的检查 每一条弧的检查
它的这个时间复杂度又是多少呢 大家看到这里哈
也就是说看到这个主体就是一个for循环
也就是说这个大循环呢就是这个Xi的每一个合法取
值
它都要迭代一次 那么它最多合法取值就是d次
我们说了假设每一个变量的最大取值个数就是d
那么就是d次 外循环就是d次
那么再看内循环 那么对于它的每一个 每种取值
我们都要去Xj里面去找有没有配对的y
那么Xj里面去找的时候我们也要从它的所有的取值
里面去找
找一下是不是符合 找不找得到一种配对的值y
满足它们之间的约束 那么这个找的工作量的话
那也是看这个Xj它可以取多少种值
那么Xj最多取值也是d
所以这种找到工作量 这种查找的工作量也是d
所以外循环是d 内循环也是d
也就是说去看这个这种赋值x、y赋值方案
这种赋值方案最大可能就是d的平方就是d乘d
所以呢这个 检查这个弧的相容性
单条弧的相容性 它的工作量就是d的平方
它的时间复杂度就是d的平方
这两个汇在一起就是n平方乘以d条弧
每一条弧它的时间复杂度是d平方
所以呢算在一起就是n平方乘以d的立方
所以这是我们弧相容算法AC-3它的时间复杂度
就是n平方乘以d的立方 也就是我们这个时间复杂
度
那么这个时间复杂度总体上看来还是一个多项式
表达是 不是指数级的
-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卡尔曼滤波器
-结课测试
