Video在线视频

那么来看一下 如果用前面讲过的标准的系统化搜
索算法

来求解这个约束满足问题的话

那这个约束满足问题应该如何来进行形式化

那么我们前面讲过所谓的标准系统化搜索指的就
是

对状态空间按照一定的规则

一个状态一个状态进行搜索

比如说像这个层次优先 深度优先 代价一致

都是属于标准的系统化搜索

那么这种搜索算法来形式化约束满足问题的话

其实上它就是一种递增式的形式化方法

也就是说它这个状态就用已经赋的值来表示

也就是说我们的约束满足问题它的值是由变量来
表示的

那我们如果用标准搜索算法来解决约束满足问题
的话

我们的状态就用已经赋的值来表示

那么初始状态的话当然是空的

就是所有的变量都没有赋值

那么后续函数我们就定义成给一个没有赋值的变
量赋值

当然这个赋值不能随便赋的 要求赋值的时候这个
值不能给

不能和已经赋的值违反约束

也就是说你赋的值必须是满足约束的

那么这个目标测试就形式化成

如果赋值是完整的赋值 那么这个

就已经表明找到了一个解 是一个目标

因为我每一次赋值的时候都已经检查了 要求它不
能违反这个约束的

那么这个就是用标准搜索算法来解决约束满足问
题的时候

这个约束满足问题的形式化 是这样形式化的

那么如果对于一个有n个变量的约束满足问题

那么用标准搜索形式化的约束满足问题呢

那么它的解都是在深度为n的这一层

那么什么意思呢 那么我们知道 刚才说了

它的后续函数就是定义成每一次给一个没有赋值
的变量赋值

并且赋的这个值要符合约束

要和已经赋的值不能与约束冲突

那既然你每一次产生后续给一个变量赋值

那当然给所有的变量都赋了值 那么这个结点一定
是在第n层的

那么一次给一个变量赋值 赋值下去

在第n层的话 并且我要求了 能赋下去的值一定是
符合约束的

所以你既然进行到第n层的时候所有的变量都赋了
值

并且赋的值都是符合约束的 所以这个就是一个解

所以这个是用这种标准搜索形式化约束满足问题
的时候呢

这个解是在第n层 所以我们就可以使用深度优先搜
索

因为它 既然我们的深度是有限的

那么我就不怕深度优先搜索在某一条路径上回不
来

它一定是有限深度的 所以就可以使用这种算法

那么它的空间复杂度就比较低

那么我们来看一下 对于这种方法形式化的约束满
足问题

那么它的搜索空间 状态空间到底有多大呢

也就是说其实上就是它的时间复杂度有多大呢

我们来看一下 也就是说在深度为l的时候呢 这个

搜索树的的分支数 b是等于n-l乘d

那么这个什么意思呢 就是说

在深度为l的时候我已经给l个变量赋了值了

因为它每进行一次 每往后拓展一次 就给一个变量
赋值

那么你在进行到深度为l的时候 已经给l个变量赋了
值了

所以你就剩下n-l个变量没有赋值

那么n-l个变量没有赋值的话

那就意味着我每一个结点都可以从n-l个变量里随
机选择一个变量出来进行赋值

所以它有n-l种选择

然后呢选择出来一个变量进行赋值的时候

对这个变量进行赋值又有d种选择

这个d的意思我们前面讲过 就是这个变量的取值

范围大小 也就是说它有d种选择

所以呢 那么对于深度为l的时候 每一个结点呢

它的可能最大分支数 就是n-l乘d

也就是说n-l个变量 不同的变量选择 选一个出来

然后对这个变量进行赋值的方案又有d种

所以是n-l乘d 当然它这么多种选择（赋值方案）
里面

可能有的是不符合约束的 这里指的是最大分支数

所以这个搜索树它总共进行到第n层的时候

它就会有n的阶乘乘以d的n次方个叶子

那么这个是怎么算出来的呢 大家来看一下这里

也就是说 我们的状态表示 假设我们有n个变量

x1、x2.........xn 有n个变量来表示约束满足问题的
一个状态

那么它的每一个变量的取值范围用Di表示

那么假设我们的变量的最大取值范围大小呢

就是我们的d来表示

那么我们来看一下 一开始的话初始状态是空的

就是它没有给任何的变量赋值

那么我就可以从这n个变量里面选择任何一个变量

那么就有n种选择

那么选择出来一个变量以后 对这个变量进行赋值

赋什么值又有d种选择

所以这个时候你其实上可以产生nd个分支

所以对于初始结点这一层它的分支数就是n乘d

也就是说 打个比方 我可以选择x1进行赋值

给它赋第一种值a1 也可以选择

给x1赋值给它赋第二种值

那么x1其实上它就有d种

然后呢 你可以继续下去 比如选择给xi赋值ai

然后也可以选择给xn赋值给它赋值ad

那么总共就是有n乘以d种选择

所以这个对初始结点的分支数（branch）

这个分支数就是n乘d

那么进行到了第一层的时候 也就是说这是第一层

初始结点是第零层

第一层的时候我们总共的结点个数就是n乘d

因为它的初始结点只有一个 那么n乘d乘1

所以呢 它的第一层 我们总共的结点个数就是nd

那么再往下走 也就是说往下走进行第二层的拓展

那么第二层拓展 我们第一层的每一个结点

它最多可以分支拓展出来多少个结点呢

分支数是多少呢 我们也同样的道理去算

也就是说它可以 也就是说我对x1等于a1这个结点
进行拓展

那么它就可以在剩下的x2到xn 这n-1个变量里选
一个进行赋值

那么每一个变量的赋值选择又有d种

所以它可以选择x2等于a1来进行赋值

也可以选择xi等于ai 当然这个i是不能等于1的

因为它已经给x1赋了值了

然后呢也可以选择xn等于ad来进行赋值

所以它总共可供选择的变量个数是

从x2到xn 所以是n-1个不同的变量选择

然后变量选择好了之后 给这个变量赋值的选择又
有d种

所以它的分支数就是n-1乘以d

也就是说呢对于第一层每一个结点它的分支个数

它最多可以拓展出来（n-1）*d个儿子

那么我们第一层又总共有nd个结点

那么每一个结点可以拓展出来（n-1）*d个儿子

所以到了第二层我们总共的结点个数就是
nd*（n-1）d

所以就是n（n-1）再乘以d的平方个

所以这个就是第二层结点

那么依次类推下去到了倒数第二层 也就是n-1层

那么到了n-1层的时候我们总共有多少个结点个数
呢

那就是 应该是 n（n-1）一直乘到2再乘以d的n-1
次方

也就是说依次类推下去到了n-1层的时候呢

它的这个结点个数就是d的n-1次方 前面就是n乘以
n-1一直乘到2

就像这里为什么第二层是这么多结点一样 是推下
来的

那么到了第n-1层的时候它已经给n-1个变量赋了
值了

那么就剩下最后一个变量没有赋值

那么假设这个结点我是给x1到xn-1赋了值

剩下xn没赋值

也就是说这个n-1层的时候就是给 n个变量里面的
n-1个赋了值

还有一个变量没赋值 不一定是1到n-1赋了值的

这个我是举个例子 这个结点假设对应的是这么一
个结点

它给x1，x2.......xn-1赋了值 剩下xn没有赋值

那么它接下来就只能给xn赋值

那么给xn赋值的时候呢 它只有d种选择

所以对于n-1层的话 因为它只剩下一个变量没有赋
值

所以它变量的选择只有一个

然后给这个变量进行赋值的选择有d种

所以对于n-1层的这个结点它的每一个结点的分支
个数 或者说能产生的最大儿子数就是d个

所以这里是d个 假设这个就是它的一个儿子

就是给所有的变量都赋了值

所以对于n-1层结点它的分支就是d

所以我们看到n-1层有这么多个结点

每一个结点可以产生d个儿子

所以到了第n层会产生多少个结点呢

那就是这么多个结点乘以d

所以最后我们这一层就是n乘n-1一直到2

d的n-1次方再乘以d那就是

n一直乘到2乘以d的n次方

那么n一直乘到2再乘个1就是n！

所以就是n的阶乘乘以d的n次方

这就是我们前面讲过的为什么这个标准搜索方法

进行形式化约束满足问题的话

它会有n的阶乘以d的n次方个叶子结点

也就是说这个空间是很大的 这个搜索空间

也就是说它产生的这个结点个数很多很多