Video在线视频

那么我们除了可以用标准的系统化的搜索算法

回溯搜索算法来解决这个约束满足问题之外呢

我们还可以用这个局部搜索算法来解决这个约束
满足问题

那么前面我们讲过这个局部搜索算法它

最大的一个好处就是它是对这个存储空间的要求
是非常低的

所以它可以用来解决这个规模很大 很复杂的问题

那么如果要运用这个局部搜索算法来解决这个约
束满足问题

那么我们这个约束满足问题的形式化和前面就会
不一样

也就是说这个时候我们约束满足问题里面我们状
态的描述呢

就是描述成一个完整的赋值

也就是说每一种赋值方案对应着一种状态

并且呢这种赋值方案呢并不是说一定要符合约束

就是说随便给这个变量赋一种值

没有必要要求它满足约束

那么任何一种赋值呢都是对应着一个状态

这是它的这个状态描述

然后呢这个动作的定义呢就定义成给这个已经赋
值的变量重新赋值

也就是说这个是它产生这个后续 产生这个儿子结
点的一个动作或者说后续函数

就是给已经赋值的变量重新赋值

那么你既然所有的变量都赋了值 那么你要选择给
哪一个变量重新赋值呢

这个的话呢 如果没有其它的原则就是随机选择一
个违反约束的变量给它重新赋值

使得它朝着目标前进 因为我们的目标就是找到一
个符合所有约束的赋值

所以这个就是变量的选择

那么我们在给变量重新赋值的时候我们这个赋值
方案

采用的是这个最少冲突启发式原则

什么叫最少冲突启发式原则呢

就是选择违反最少约束的值来给它赋值

也就是说我们选择一个变量重新赋值的时候

给它重新赋的值呢 这个重新赋的值呢

就是让它 使得它竟可能少的违反这些约束

那么当然不违反约束是最好了

那么这个就是叫做最少冲突启发式原则

那么来看一下这个用局部搜索算法来解决这个四
皇后问题

这是一个很简单的四皇后问题

那么我们的这个状态的描述就是一个完整的赋值

比如说像这里就是对应着一个状态

那么这个状态就是每一列摆一个皇后

那么我们总共有多少个状态呢

那么每一列比如说这一列我可以摆放在

四个行里面的每一行 所以它有四种选择

那么每一列都有四种选择它就是4的4次方

所以呢对于这个问题呢我们就有256个不同的状态

那么用局部搜索算法来做的话

它就是相当于在256个不同的状态去找一个 搜索
一个目标状态

那么我们的这个 定义的这个动作或者后续函数

就是你选择某一列的皇后将这个皇后在同一列内
移动

就是规定它只能在同一列内移动

因为最终的话这个皇后肯定是每一列有一个的

也就是说你不可能同一列放两个 那明显就不是目
标状态

所以这种方法也是使得这个问题简单化

所以呢这个就是这样子规定它的动作

那么目标测试的话就是 我的这种摆放 我的这种赋
值方案呢

就是使得所有的皇后都相互攻击不到

那么我们对于这个因为我们知道我们这个用局部
搜索

进行解决问题的时候 对它产生的后续我们是要评
估的

这个后续是不是比我当前状态要更好

更好的话它才会走向这个后续状态

如果它发现这个后续状态都比自己更差

那么它就会把这个局部最优点返回去的

所以它是有一个评估函数来评估这个状态的好坏
的

那么对于这个例子的话假设我们定义这个评估函
数为攻击到的皇后对数

也就是说如果你是定义成这么一个皇后对数的话
那么当然是评估函数值越小这个状态越好的

也就是说对于这个n状态这个评估函数值就定义成
能够攻击到的 能够攻击到的皇后对数

那么比如说像这里针对这个例子的话

那么我们形式化好了之后我们用局部搜索算法来
求解这个问题的话

都是任意给一个初始状态 比如说像这里任意给一
个初始状态

那么计算它的评估函数值它是等于5的

5的话就是有5对皇后互相攻击的到

请大家看到这里 每一条线就表示这是一对

这是一对 这是一对 这是一对 这是一对

所以总共有五对皇后可以互相攻击的到

所以它的评估函数值是等于5

然后呢它就利用我们刚才定义的动作或者后续函
数去产生这个后续

那么产生后续的话 它可能会产生很多个后续的

因为这个 我们看到这个动作就是将皇后在同一列
内移动

那么你可以选择在这个皇后移动 这个皇后移动

这个皇后移动 这个皇后移动

所以它产生的后续呢可以有很多种 比如说3

想这个可以移它3种 这里移它三种

这里移它三种 这里移它三种

所以其实上会有3的四次方个不同的儿子产生

那么你要看你用的是哪一种局部搜索算法

如果使用的是爬山搜索算法的话

它要从所有后续里面选一个最好的后续来

判断它是不是比当前状态要更好

那么假设我们最好的一个后续是这个

那么大家看到这个后续的话呢 其实上移的是这个
皇后

这个皇后它把 这个皇后从第二行移到了第一行

那么就变成了这么一个状态

那么这个状态它的评估函数值算出来是等于2的

也就是说只有这一对和这一对皇后互相攻击的到

那么这个算出来这个状态要比当前状态要更好

所以呢它就会走向 就像爬山一样就是走到这个

这个更好的这个后续状态来 所以当前状态就变成
这个状态了

也就是说我就是在前进了 在不断地前进 在爬山了

所以呢这个就到了这里 那到了这里之后这一步

那么假设在这一步的基础上我又去产生它的后续

那么产生它的后续呢假设我有一个最好的儿子是
这个儿子

这个儿子怎么产生的呢 就是将这个皇后移到这里

移到这里来了之后呢 这个最好的儿子的评估函数
值是等于零

也就是说没有任何一对皇后可以互相攻击的到

所以呢它发现这个儿子呢比我当前状态要更好

所以它肯定义无反顾的走向它

然后呢走向它之后呢 这个当前状态一看呢 已经是
一个目标状态

也就是说呢他都没有任何一对皇后可以攻击的到

所以他就返回去了 它就把这个状态呢就返回去了

就找到了一个全局最优点 就找到了一个解给你

那么所以这个局部搜索算法呢 看似它好像很盲目
的

就是只看到周边一点点提高 不断地改进当前状态

然后呢来找到 从而向目标前进来找到一个解给你

这个局部搜索算法就是 它的解决问题的能力是非
常强的

也就是说我们任意给定初始一个状态

这个局部搜索算法呢能够以很高的概率 也就是说

它很大的可能性 就是说我是不能保证百分百能帮
你解决问题

但是我的这个解决问题的概率是很高的

并且呢我解决问题的时间是固定的

是常数时间 也就是说我不会随着你这个问题的规
模增大

而指数级 平方级的增大

就是在常数时间内解决大规模的n皇后问题 可以解
决

像这个的话它可以解决皇后问题的规模

可以规模达到 看到没有这么一个数量级

这个数量级就是比前面的要多的多

前面我们讲了回溯搜索算法如果没有用那些提高
效率的启发式原则的话

它只能解决25皇后问题 用了那些启发式原则之后
它能解决1000皇后问题

那么像我们的这个局部搜索算法呢

它能够在常数时间内以很高的概率 解决大规模的n
皇后问题

也就是说这个n可以达到这么一个数量级

所以呢这个是局部搜索算法它的优势所在

那么我们来总结一下这一章的内容

我们知道这个约束满足问题是一类特殊的问题

也就是说它的状态是固定变量集的赋值来决定它
的这个状态

就是说不同的赋值呢对应着不同的状态

那么它的这个目标测试就是由这个变量之间的值
的约束来定义的

也就是说如果满足所有约束的赋值就是一个目标

那么这个是约束满足问题

那么我们讲到了用回溯搜索算法来解决约束满足
问题

那么回溯搜索算法其实上是一个深度优先搜索算
法

只不过是它要求这个深度优先搜索算法

这个结点产生后续的时候只给一个变量赋值

那么只给一个变量赋值的话 所以每个结点它最多
就是产生d个儿子

也就是说它的分支树最多就是d

所以呢这个是回溯搜索算法

那么回溯搜索算法呢

它可以使用变量选择和值选择策略来提高这个算
法的效率

也就是说如果没有运用这些启发式的这些策略呢

这个回溯搜索算法大概只能解决25皇后问题

那么应用了这些策略之后呢 它可以解决1000皇后
问题

所以呢这个算法的效率是提高了40多倍

那么我们还讲到了用前向检查来阻止这个

结点的这种无谓的搜索

也就是说可以来阻止这个导致将来失败的赋值

也就是说如果我能够

也就是说通过前向检查能够提前检测到这个赋值
呢是不可避免的失败的

所以呢提高这个算法的效率 这是前向检查

那么约束传播的话就能比前向检查更早的检测到
不可避免的失败

那么它在约束值和检测不相容性方面比前向检查
看的更远

也就是说它不单单是把这个约束从这个

赋值变量传到没有赋值的变量

还在没有赋值的变量之间传播 所以它比前向检查
看的更远

能够更早的检测到这种不可避免的失败

那么这个是这一章的内容