Video在线视频

那我们前面讲过回溯搜索算法

回溯搜索算法在本质上是一种深度优先搜索算法

那么这种深度优先搜索算法的效率

就取决于你优先试探的那条路径上是否有解

如果你能够优先试探一条有解的路径

那么这个算法的效率就可以得到提高

所以我们就可以对这个回溯搜索算法

采用一些启发式的 通用的准则来提高它的效率

那么首先我们来回忆一下这个回溯搜索算法

那么回溯搜索算法呢 看到这条语句

就是说我们要从还没有赋值的变量里选择出来一
个变量 先进行试探着给它赋值

也就是说这里面的选择其实就是

我们选择一条路优先进行试探

那么如果你选择的好这条路上可能有解

那么你的算法的效率就更高

那同样的再看到这条语句 那么这条语句说

对选出来的这个变量以一种顺序对它尝试着赋值

也就是说这个变量可以赋ABC三种值

那我是应该先给它尝试赋A呢 先给它尝试赋B呢
还是先给它尝试赋C呢

也就是说这种尝试赋值的顺序也是决定你优先试
探哪一条路

那么这个也同样的影响着你这个算法的效率

那么在这两方面我们都可以找到一些

启发式的准则来提高我们算法的效率

那么还有一个方面就是 可能某一个结点往下搜索
根本就没有解

我们能不能够提前检测到这样的结点

从而让算法不用去搜索这个结点下面的空间

从而提高这个算法的效率

那么下面我们就来讲述这个三方面应该如何来做

那么像这个 如何在没有赋值的变量里面

选择一个变量来进行优先的尝试 给它赋值往下走

那么这种选择变量的原则呢 我们有一个启发式原
则叫做

最大受限变量 什么叫最大受限变量呢

就是它受到的约束是最大的

这样的一个变量我优先的让它出来给它赋值

那么也就是说 大家看到这里

就是most 这里一个被动态 就是被人家限制的

这样子 最多的 这样子的一个变量

那么这种变量其实上也就是说它具有最少的合法
赋值

因为它被人家限制的很死 所以它的合法赋值选择
余地是很小的

所以你要优先的把这种变量拿出来赶快给它赋值

否则到后面它就没有 不存在合法赋值了

所以这是这么一个原则

那么比如说像这里 一开始我们所有的变量都是没
有赋值的

那么所有的变量都具有三种合法赋值

也就是说这个时候你用这个最大受限变量原则呢

大家是同等的 那么 比如说我没有办法

我就随机的选一个给它进行赋值

比如说先试探给它赋红色

那么这个时候还没有赋值的变量里面这两个变量
就受到了限制

受到了限制使得它们的合法赋值就只剩下两个

也就是说剩下绿色和蓝色

那么像这些人 这四个人 他们就还有三种合法赋值

所以这两个人就是属于最大受限变量

那么我下一步就从这两个人里面选一个

优先进行 试探给它赋值

那么假设我选它 那么给它赋一种绿色

那么到了这一步的时候呢

没有赋值的变量里面谁受到的约束最大呢

那么这个人受到的约束最大 它只能赋一种颜色 就
是蓝色

那么它只剩下一个合法赋值

它呢剩下两个合法赋值 就是红色和蓝色

那么这里三个变量就是没有受到限制

还有三个合法赋值

所以最大受限变量就是我们的这个变量

所以下一步我们就应该优先把它选出来 进行试探
给它赋值

那么就这样一步步往下走这个就叫做最大受限变
量原则

那么也称为什么呢 最少剩余值原则

也就是最少剩余值启发式

也就是说它的合法赋值呢 剩下的合法赋值是最少
的

那么也叫MRV 简称为

那么这个是在选择变量的时候的一个启发式原则

那么这个启发式原则有的时候呢 不够用

就像我们这里一样 那么一开始所有的变量它的合
法剩余值都是一样的

那么这个时候就不知道该如何选择

那么在这种情况下呢我们还有一种启发式原则

叫做最大约束变量

也就是说你发现有多个还没有赋值的变量

它的这个最大 它的剩余合法值 合法赋值

它的这个相同的时候呢 我们就要采用另外一个原
则来从这些

具有相同的剩余合法赋值的变量里面选一个

也就是说打破这种均衡

那么这个也 另外一种原则叫做最大约束准则

这个最大约束准则 约束这个单词它用是ing形式

就是主动的 也就是约束别人最多的这个变量

用这个原则来选择这些具有相同的剩余合法赋值
的这些变量

那么比如说像这里 一开始我所有的变量

它的剩余合法赋值都是三个

那么我不知道如何选择 那么怎么办呢

我就利用第二个准则 最大约束变量准则

就是看谁赋值之后约束了 就是受牵连的变量最多

比如说像这个变量我赋值之后

就会影响到这两个人 就会约束到了它俩

就是说它约束别人 约束两个 那么像这个也是

那么像这个也是 它赋值之后约束到了1、2、3三
个人

那么这个变量如果赋值之后它约束到了
1、2、3、4、5五个人

也就是说它一旦赋值到了 就会影响到它周边的五
个变量

也就是说它约束别人 给别人造成的不方便最多

那么像这个也是 它赋值之后 它就约束到这三个变
量 1、2、3

它赋值之后约束到两个变量 它赋值之后也是约束
到两个变量

它赋值之后没有约束到任何 因为它没有和任何人
相邻

所以我们根据第二个准则我们就知道

这个变量赋值之后呢约束其他变量的个数最多

所以呢我们就选择它 进行优先的尝试给它赋值

所以我们就选择它 比如说尝试给它赋蓝色

那么它赋完值以后 其他的这些未赋值变量里面

我们首先根据最小剩余值原则来选择

那么它剩下两种颜色 它也剩下两种 它也剩下两种
它也剩下两种 它也剩下两种 它剩下三种

那么同样的道理1、2、3、4、5这五个变量

具有相同的剩余值 那么同样的你不知道如何选择

你要利用这个最大约束变量准则打破这个均衡

那么我们就看一下它赋值之后影响谁 影响它 一个

那么它赋值之后影响谁 影响两个

然后它赋值之后影响两个 它赋值之后也影响这两
个

那么这三个人在第二个准则的时候还是一样的

所以那么没有办法 利用了两个准则它们三个人都
是一样的

那么我们就从这三个变量里面随机选择一个

那么它就选它了 把它选出来

那么把它选出来那么我们就 比如说给它赋一个绿
色

那么赋了绿色以后我们看一下 谁具有最少合法剩
余值

那么它剩下了一种 它也剩下了一种

它剩下了两个 它还可以赋红色和绿色

它也剩下了两种 它剩下三种

那么我就知道这个和这个它们两个人 就具有相同
的这个 最少剩余值

那么这两个人都具有最少剩余值 那么怎么打破这
种均衡呢

同样的利用这个最大约束变量 看谁约束别人最多

那么它的话 它赋值之后其实上对还没有赋值的变
量的约束是没有的 它没有约束别人

那么它赋值之后呢 它会对这个人造成约束

也就是说它约束未赋值变量的个数是一个

然后呢所以呢 在这两个人之间呢选择的时候呢 所
以我们就选择它

利用第二个准则 发现我们应该选它

所以就把它选出来进行赋值 赋成红色

那么这个就是这两个准则用来帮助你选择

也就是说应该优先选择哪些没有赋值的的变量进
行赋值

那么我们看到也就是说呢 首先呢就是运用最少剩
余合法值原则来挑选变量

如果挑选出来发现有多个变量有最少剩余值

这个的时候呢 我们就利用第二个准则 最大约束变
量准则

从这个多个最少剩余值变量里面选择这种

你赋值之后对还没有赋值变量造成的影响最大的
这样的变量进行赋值

那么这个是这两个准则

那么选择好了变量之后呢 如何按照一种顺序来试
探着给它赋值

那么我们也有这种启发式原则

这个启发式原则叫做最少约束值

也就是说我们选择好了变量之后应该选择一个

具有最少约束值的这个值来尝试赋值

所谓的最少约束值就是对其他的没有赋值变量的
合法赋值影响最小的值

所以你因该给它赋一种值 这个值对其他还没有赋
值的变量造成的影响最少

那么这里的影响当然就是让其他的

还没有赋值变量的合法赋值

这个剩余合法赋值越多越好

也就是说你选择赋了这个值之后

使得我们的剩余合法赋值减少的最少 影响最少

那么这样子的值你优先给它进行尝试

这样给其他没有赋值的变量留下更多赋值的空间

那么使得你这条路更有可能走到底找到一个解

就是这个意思

所以呢我们来看一下 就像这里一样

那么这里的话我们单独的来考虑如何尝试给它赋
值

那么像这里一开始的话是一个空的

那么我再给这个变量尝试赋值的时候 比如说我尝
试红色

那么对这两个变量的合法剩余值都会

影响1 这个人减少一个 这个人减少一个 其他人没
有变化

那么给它赋绿色也是它减少一个 它减少一个 其他
人没有影响

给它赋蓝色也是它减少一个 它减少一个 其他人没
有影响

所以在这一步如果你选择给这个变量尝试赋值的
时候

红绿蓝它们三个值 它们的顺序是一样的

用这个原则是你选择不出来的 所以你只能 比如说
就随机给它赋一个红色

那么赋好红色之后呢

那么假设你选这个变量进行尝试

那么你尝试红色不合法 尝试绿色

那么如果你尝试的是绿色的话呢 这个人它的合法
剩余值就减少一个

本来原来人家有两个 现在变成一个了

那么这个人呢剩下两个 这个人呢没有影响 这个人
也没有影响 这个人也没有影响

所以这个绿色呢它对它的影响是1

那么如果是蓝色呢对它的影响也是1

那么对它的影响也是减少1 那么其他人没有影响

所以呢在这一步呢 绿色和蓝色对其他变量的影响
也是一样的

所以假设就给它赋绿色

那么走到这一步的时候我们再往下走

比如说走到给这个变量尝试赋值的时候

如果尝试给它赋红色 赋红色的时候呢

那么你对这个变量的剩余合法赋值是没有影响的

这个本来原来人家的剩余合法赋值就只剩下蓝色

那么如果你给它赋红色它还是有蓝色

所以对它的影响是没有 那么对这个人的影响呢

就使得它只剩下两种颜色 那么对这两个人没有影
响

那么如果你假设给它尝试用蓝色

那么这个变量的合法剩余合法赋值就受到了影响

它呢就变成 剩余合法赋值就变成零了

这个减少一个 这两个没有影响

所以比较而言给这个变量应该优先赋红色

因为赋红色比赋蓝色对其他还没有赋值变量的影
响更少

也就是说它对这个变量的影响更少

所以呢 我们应该优先给它赋红色 尝试给它赋红色

这个就是所谓的最少约束值原则 来选择一个最有

对其他的没有赋值的变量影响最少的值

来优先进行试探搜索

这个是对于这个值的尝试试探顺序的一种启发式
原则

叫做最少约束值原则

就是对其它没有赋值变量影响最少的值 优先进行
试探