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的立方 也就是我们这个时间复杂
度

那么这个时间复杂度总体上看来还是一个多项式
表达是 不是指数级的