Video在线视频

在利用这个最少剩余值原则 以及这个最大约束变
量和这个最少约束值

这三个启发式原则用来选择变量 以及选择赋值的
顺序

这些准则之后呢 这些启发式准则之后呢

我们的这个回溯搜索算法的效率是大大提高了的

我们是不是已经就是说对于一些这个

无谓的这个搜索是不是都能尽量避免呢

其实上我们还做的不够

也就是说我们还可以检测到一些不可避免的失败

从而及早的终止某一条路径的搜索

那么我们一种检测不可避免失败的方法就是利用
前向检查的方法

那么这个前向检查的方法就是跟踪还没有赋值变
量的合法赋值

也就是说我们建立一个表来跟踪这些还没有赋值
的变量的剩余合法赋值

那么如果你发现到了某一步的时候 搜索进行到某
一步的时候

发现这个表里面有哪一个变量的剩余合法赋值已
经是空了

那么这个时候尽管你这个搜索算法还可以进行下
去

但是你知道这条路走下去一定是行不通的了

因为已经有变量的剩余合法赋值是空的了

你再走下去已经是无谓的搜索了

所以你就应该停止 那么这个是它的一个方案

就是跟踪记录还没有赋值变量的合法赋值

那么比如说像这里 初始状态的时候就是

我们的所有变量的剩余合法赋值都有三种

所以你这个时候是可以进行下去的

所以比如说我给这个区域赋成红色之后 给它赋成
红色之后

那么其他的还没有赋值的这些变量的剩余合法赋
值就有变化了

那么像这个NT和SA 就是这两个变量 和它相邻的
两个变量

它的剩余合法赋值就减少了一种 它就不能赋红色
了 它就剩下两种

所以呢这个前向检查表里面这两个变量的剩余合
法赋值就只剩两种了

然后呢再往下走 比如说走到这一步的时候呢

我给Q这个区域赋了绿色之后呢

那么这个变量的剩余合法赋值就只剩下一种就只
能给蓝色了

还有这个变量它的剩余合法赋值也只剩下一种 也
只能赋蓝色

那么这个变量它的剩余合法赋值剩下两种 是红色
和蓝色 它不能赋绿色了

那么其他的这两个变量还有三种

那么这个时候呢我们就认为还可以走下去

因为所有的还没有赋值的变量它的剩余合法赋值
还都是存在的

那么继续往下走 那么走到这一步的时候呢

就是这个变量已经赋了蓝色的这一步的时候

我们就发现了什么呢 我们就发现这个变量

这个SA这个变量呢 它的剩余合法赋值已经变成空
了

它不能再赋蓝色因为和它相邻的这个区域 它这个
赋了蓝色

所以它的剩余合法赋值就变成空了

然后呢再看这个 这个人剩余合法赋值呢

它就只剩下蓝色 蓝色 没有动

然后呢这个人的剩余合法赋值就只剩下一种

这一种就是红色 也就是说NSW剩下红色

那么只有这个区域跟所有的区域都不相邻

它还有三种合法赋值

那么走到这一步的时候我们一看这个前向检查表

里面有一个变量它的剩余合法赋值已经是空了

那么意味着这个结点它再往下搜索它是没有解的

也就是说它是不可避免失败的

你去给这些变量赋值都没有意义

因为你最终要给SA赋值 给SA赋值的时候你发现

它根本没有值给它赋

所以这个结点往下搜索就毫无意义

所以到这个时候你一但发现这个前向检查表里面

有这个变量的合法赋值为空

那么这个节点你就应该终止 就应该返回 回溯

回溯回去呢 就是选择给这个变量赋另外一种值 回
溯回去

那么这个就是前向检查它的思想

就是跟踪记录没有赋值变量的合法赋值

当发现有变量它的合法赋值为空的时候 就停止这
个结点的搜索回去 回溯

就是说这条路走不通了 应该回溯去试探另外一条
路

这就是这个前向检查的意思

我们前面讲的前向检查相当于把已经赋值的变量
信息传播给没有赋值的变量

也就是说都传播给和它相邻的这个没有赋值的变
量

也就是说告诉你们 你们的合法剩余值就不能取这
个了

但是没有赋值的变量之间的约束信息传播其实他
是没有往下做下去的

所以呢它就不能提早检测到所有的失败

那么比如说像这个例子 那么这个例子话呢 比如说
我在给这个变量赋红色之后

然后呢它就把这个赋值信息传播给了这两个变量

和它相邻的NT变量和SA变量

所以他们的剩余合法赋值就剩两种

然后呢再给这个变量赋值之后呢

它又把这个赋值信息传递给和它相邻的这三个变
量

这三个变量 使得这三个变量的合法剩余值进行了
变化

然后其实上这个时候我们的检查表里面还不能够
检查到失败

也就是说这个时候呢 它们的合法剩余值都还有的

没有说哪个变量为空

但其实是到了这个状态的时候呢 其实上它已经是
不可避免的失败了

为什么呢 也就是说我们的NT和SA是不能同时为蓝
色的

也就是说这两个变量是相邻的

也就是说你也只剩下蓝色 它也只剩下蓝色

但其实是这两个变量是绝对不可能同时赋蓝色 同
时赋蓝色就没法约束了

所以其实上到这个时候呢 它就已经是不可避免的
失败了

但是我们的前向检查并没有检查到这个不可避免
的失败

它还要继续往下做无谓的搜索工作 浪费搜索资源

那么我们为什么这个前向检查不能检查到这个不
可避免的失败呢

原因就是因为它只是把赋值变量的信息传播给未
赋值变量

也就是说只把这个已经赋值传播给和它相邻的两
个变量

那么这两个变量引起的变化并没有继续往下传播

它引起的变化并没有传播给和它相邻的其他未赋
值变量

也就是说呢这种信息的传播还不是 不足够这种约
束的传播

所以呢它就不能够提早检测到所有的失败

那么我们有另外一种约束传播的办法呢

就是可以把这种约束信息呢 一层一层的往下传播

也就是说把这种已经赋值的传给未赋值的

未赋值的引起了变化之后再传给和它邻近的这些
变量

那么这种局部的这种约束传播一层一层的检查下
去

就能够提早检测到更多的失败

那么这个弧相容就是约束传播的一种方法

那么来看一下这个弧相容是一个什么样的概念

也就是说约束弧 X到Y的这么一个有向的约束弧是
相容的

那么它充分必要条件是什么呢

就是当且仅当对于这个变量X

就是这个起点的每一种赋值

也就是说它有三种合法赋值 它每一种赋值都要满
足这个要求

变量Y都存在着一个对应的合法赋值

那么我们就称这条弧是相容的

那么比如说像这里 到了这个状态的时候

我们的这个前向检查表里面 它这些还没有赋值的
变量的剩余合法赋值呢 是这么一种情况

那么我们这个SA到NSW这条有向的约束弧呢

它是不是相容的呢 我们来看一下定义

那么它说对于这个X 就是我们的起点

SA的每一种赋值 那么它只有一种赋值

我只要检查一个就行了

如果给它赋蓝色 那么我们的变量Y NSW

存不存在一个合法赋值满足这个约束

SA到NSW的这个约束呢

满足的 也就是说我可以赋红色 你赋蓝色我可以赋
红色

所以这条弧就是一条相容的弧

那么如果反过来 NSW到SA的这个有向弧是不是相
容的呢

那么我们来看一下 NSW的话它有两种合法赋值

那么我们先看它给它赋了红色

那么我们的SA是存在一个合法赋值的 蓝色

那么如果你给它赋蓝色 那么我们的SA就没有 就
不存在一个对应的合法赋值了

所以呢这个时候呢我们就称NSW到SA的这条有向
弧是不相容的

那么要把这条弧变成相容的那要怎么办呢

那么唯一的办法就是删除掉这个起点

NSW的另外一个合法赋值

让它的剩余合法赋值只剩下红色

也就是说把蓝色从它的剩余合法赋值里面删掉

那么这条弧就会变成相容的

也就是说呢为什么这条弧会变成相容的

也就是说它只剩一个红色 对于它的每一种赋值它
只能给它赋红色

那么我的Y当然就存在一个蓝色 那么我就满足这
个弧相融的这个定义

也就是说一条不相容的约束弧

要变成相容的 它的这个方法呢 就是删除掉这个起
点的合法赋值

使得它变得相容的

那么如果这个 你要使得这条弧变得相容的

发现不断的删 把NSW都删空了

那么其实上就意味着这个状态其实上你是进行不
下去的

往下搜索你是找不到解的 是这么一个意思

那么它就相当于呢这种约束信息在局部之间不断
地传播 往下传播下去

那么这个是弧相容的这个概念

那么我们 假设我们把NSW到SA的这条弧

从不相容变成相容 我们删除掉了这个NSW的一个
剩余合法值

那么本来原来的 比如说我原来的 比如说是Q到
NSW的这么一条弧呢

它本来原来是相容的 但是由于你NSW删掉了剩余
合法赋值

那么使得这个Q到NSW这条弧可能就会变得不相
容

那么这个时候呢 你就需要重新检查 它的这个相关
的约束弧

也就是说如果这个变量X删除了一个合法赋值

也就是说它删除了合法赋值 则它的邻居变量就需
要重新检查

也就是说NSW它删掉了合法赋值

那么这个邻居变量Q、SA、V这些弧

从这些邻居变量出发的这些弧

到它的这些弧都需要重新检查 就这么一个意思

那么也就是说我NSW删掉了一个合法赋值

那么我V到NSW的这道弧呢 就需要重新检查

那么我们就要来看一下

比如说我本来有三种合法赋值的

那么我们每一个都要检查 如果我给V赋红色

那么你本来有个蓝色对应着的 那么现在你蓝色删
掉了

我就没有合法赋值对应 所以V到NSW这条弧就变
得不相容了

所以我要把它变得相容 我就要把它这个V的这个
合法赋值 这个红色删掉

删掉之后呢我们就看一下 如果给V赋绿色

那么我可以赋红色 没错 如果赋蓝色那么我可以赋
红色 对了

这个时候呢 V删掉这个红色之后呢 这条弧就变得
相容了

也就是说如果你一旦删除了哪个变量的合法赋值

那么他的邻居变量出发到这个变量的这个弧呢

这些弧的相容性就需要重新检查

所以它就这样一个变量的合法赋值引起的变动

它这种约束信息呢就要不断传播给它的邻居变量

传播给它的邻居变量 这样层层传播 直到所有的约
束弧都相容为止

这个时候呢 你再来看一下 这个前向检查表里面有
没有变量它的合法赋值已经为空了

如果为空了那就表明这个状态往下搜索是没有解
的

是一个不可避免的失败

那么这个就是我们通过这个弧相容检查来检测不
可避免的失败

那么它呢由于把这个约束信息不断地往下传

从这个没有赋值的变量一层一层传给这个邻居变
量

邻居变量反过来又传给它的邻居变量

使得它可以比这个前向检查呢更早检测到失败

那么这种弧相容原则 这种检查呢

可以在给这个变量赋值之前进行 或者是在给这个
变量赋值之后

比如说我在给这个变量赋红色之后

那么我这个前向表是要变化的 前向检查表

那么我在这个变化之后的表上面进行一个弧相容
的检查

或者是我准备给这个变量赋值之前 我就进行一个
弧相容的检查

这个都无所谓的 那这个是弧相容检查