Video在线视频

那么我们看到就是在用标准搜索方法来形式化约
束满足问题的时候

其实它的状态空间里面产生的很多状态

对于我们约束满足问题来讲都是等同的

也就是说它 比如说有一种状态它对应着

先给WA赋了红色 然后给NT赋了绿色

然后另一个结点对应着先给NT赋了绿色

然后WA赋了红色

也就是说这肯定是在刚才说过的标准搜索形式化
状态里面两个不同的状态

但其实这两个不同的状态对于这个约束满足问题
来讲

其实上效果是一样的 是等同的

也就是说这个约束满足问题并不在意你是先给哪
个变量赋了值 后给哪个变量赋了值

它在乎的是 它要的是 最终这些变量赋了什么值

所以这个变量赋值的顺序无所谓 是可以交换的 也
就是说这个顺序

那么既然是这样的话呢

刚才那种形式化方法就会有很多没有意义的状态

重复状态产生

所以我们可以考虑每个结点只给一个变量赋值

而不去考虑每个节点去给剩下的没有赋值的变量
都考虑个遍

使得这个分支这么多

那么我们既然不在乎这个变量赋值的顺序

那么每一个结点的时候呢 我们只考虑给每一个没
有赋值的变量进行赋值

那么这个的话就会使得每一个结点的分支数都是d

也就是说只考虑给一个变量赋值 那么这个变量赋
值它的选择就是d嘛

所以这样子去做这种改动的话 简化的话

那么它的每一个结点的分支个数都减小了d

那么这样子的话整个搜索树到了第n层的时候

就只有d的n次方片叶子

所以就不会是n的阶乘乘以d的n次方片叶子了

因为每一层它的分支都是d

所以第一层就是d 第二层就是d平方 第三次就是d
的三次方

一直到第n层就是d的n次方

所以这个状态空间就会大大的减少

那么采用这种简化之后的形式化方法

来描述这个约束满足问题的话 来解决这个约束满
足问题的话

那么我们在简化的基础上采用深度优先搜索算法

那么这种深度优先搜索算法就叫做回溯搜索

也就是说采用这种每一次只给一个变量赋值的

这种深度优先搜索来解决约束满足问题的算法称
为回溯搜索

那么我们来看一下这个回溯搜索的过程 它的伪代
码

那么大家看到这里这个回溯搜索

也就是说它这个英文就是回溯搜索

那么他的这个输入就是我们这个约束满足问题的
形式化

就是刚才那种简化了的形式化

初始状态就是空 然后后续函数就是给一个没有赋
值的变量进行赋值

当然是不能违反约束的

然后目标测试就是所有的变量都赋了值

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

然后呢它返回 它返回是返回一个解给你

就是所有的变量都赋了值 或者它找不到这样的赋
值方案 返回失败给你

那么它呢 这个回溯搜索算法呢它

我们在这里它是利用这个递归的方法来实现的

所以呢它首先就去调用递归回溯搜索

也就是说这个是一个递归函数 递归回溯搜索

然后呢递归回溯搜索它的参数有两个

第一个参数就是状态描述 那么一开始就是初始状
态

就是当前状态描述 相当于当前结点 就是当前结点

那么我们的当前状态 当前结点 就是我们的初始状
态

那就是空的 所有的变量都还没有赋值

那么再把这个约束满足问题的形式化作为第二个
参数

那么所以它的主体就是递归回溯搜索算法

那么大家看到这个递归回溯搜索算法

所以它的第一个参数就是已经赋的值

就是当前结点已经赋的值 赋值方案 当前赋值方案

就是已经赋好了的值 当前状态 或者称为

然后第二个参数就是我们刚才讲的

约束满足问题的问题描述

然后它呢 这个递归回溯搜索算法呢

它返回也是 要么返回一个解给你 就是所有变量都
赋了值

并且不违反约束 或者说它找不到这样的赋值方案

返回一个失败给你

那么我们来看一下这个递归方法实现的回溯搜索
算法

它的整个的主体是一条两条三条 四条语句

那么这里有一个for循环 那么我们来看一下

首先第一条语句 它先判断一下当前这个状态 这个
赋值是不是完备的（完整的）

就是所有的变量都赋了值 如果所有的变量都赋了
值 表明已经找到了一个解

那么它就把这个解返回去 就一层一层返回去 就退
出了

否则的话就根据你当前赋值 看一下那些变量赋了
值

然后呢 根据这个问题的形式化描述

然后我就知道哪些变量还没有赋值

然后呢从这些还没有赋值的变量里面去选择一个
还没有赋值的变量出来

这就是我们刚才讲的用单变量赋值形式化

就是我只对一个变量进行赋值 进行后续的搜索

所以它的分支数呢永远都是d

所以我在这里的话呢有一个选择

只选一个出来进行往下搜索试探

所以他就选了一个还没有赋值的变量出来

放到这个var变量里面

然后呢就开始了我们的试探 往下搜索

对于你这个已经选择出来的变量

就是说还没有赋值的这个变量 就是准备对它进行
赋值的变量

然后呢根据这个问题的形式化 我们来看一下这个
变量

它可以取 它的取值范围里面的这些值呢 一一的进
行尝试

也就是说你选择出来的变量它有多少种可供赋的
值

每一个值执行一次迭代

那么我们来看一下 比如说它选出来的这个值

比如说你有d种 对于你选出的这个变量有d种不同
的赋值方案

那么每一个赋值方案都要进行试探

都循环一次这个for循环

比如说有d种这个for循环就要循环d次

那么对于你挑选出来的 比如先试探第一个value

那么对于这个值我们先看一下

这个值和我们已经赋好的这些值是不是符合这个
约束

也就是说是不是符合这个约束

如果是的话 那么才执行下面的四条语句

不是 不符合约束的话那么就尝试下一种

那么我们来先看到 假设它符合约束

也就是说就像它刚才一样

如果我给它赋红色它是不违反前面给NT赋的绿色

那么我就开始试探 就把变量赋了这种值加到这个

相当于这个变成一种新的状态加到这个已经赋值
的方案里面去

那么你这个赋值方案就多了一个变量赋值了

加进去意思就是我要准备试探了 看一下成不成功

然后我给它加进去变成一种新的状态 一种新的赋
值方案

加进去之后当然你这种状态就变成了一种新的状
态

然后在这个新的状态的基础上再往下进行搜索

那么它就变成了一个同样的一个问题

也就是说在这个已经赋值的基础上去给剩下的变
量赋值

那么是同样的一个问题 所以它调用的是

递归的调用的是自己同样的这个算法去解决这个
问题

所以它就递归调用 递归回溯搜索算法

去解决当前这个 当前这个状态 已经赋值的这个这
个状态下面 给剩下的变量应该如何赋值这个问题

就调用这个递归调用

那么递归调用出来 那么它往下走

也就是说在这个新的状态尝试下面往下走

解决这个问题 这个新的问题 它会有一个结果回来

那么这个结果回来之后 我们要根据这个结果来判
断我应该怎么做

也就是说假设我给这个变量赋了这个值

它往下找 找得到解 也就是说这个解

我们知道这个算法呢可能返回两种情况 一种是解
一种是失败

那如果你找到了一个解 找到了一个解就意味着你
这个result不是失败

那么它就把这个解呢就退回去了

也就是说从这里就开始回去了 一层一层回去 把解
返回去

这个下面的什么值它也不再去试探了

这些其他的语句它也不再执行了

它就直接一层一层退回去 return return回去 就
return回去了

那么就把这个完整的解返回去了

那么假设 这个if成立就表明找到了解 回去了

那么如果不成立就表明这个result就是一个失败

也就是说你给这个变量赋这个值这个结点下面是
没解的

没解那意味着你可能给变量赋这种值

可能就不行 就导致你给这变量赋这个值 这个结点
下面压根就没解

所以你给变量赋这个值就不对 就没解

所以呢我就要把这个 这个变量赋这个值从这个状
态里面移出去

也就是说恢复原来的这种状态 就是回溯嘛 就回去

回到原来的那个初始的状态 选择另外一条路

选择另一个赋值方案进行尝试

也就是说给它移出去之后我们就执行for循环的下
一次迭代

就是选择另一种值来进行试探

那么就是这么一个过程 那么再看一下这个值

看一下符合约束 符合约束的话就给它赋这个值

然后同样的赋好值之后就看一下赋好值之后的新
的结点下面有没有解

如果有解那就一层层回去了

没解同样的我就回溯回去把这个值撤销

回到原来的状态去试探下一个值

那么假设有一种情况就是 我这个变量的每一种赋
值都没有解

也就是说这个for循环我都执行完毕了 没有从中间
退出来

这个for循环每一个值我都尝试过了 都不行

都要撤销 也就是说都撤销了 那怎么办呢

那就执行这条语句 for循环结束了都没有找到解

那就执行这条语句 这条语句什么意思呢 就是

返回失败 那么这个返回失败是谁返回去的呢

是你这个状态返回去的 是调用它的时候这个初始
的父亲

这个结点 这个状态 它就没有解

所以呢它就告知上一层你这个赋值不行

要撤回去 撤回上一层去 试探下一个赋值

所以它整个的思路 就是这么一个思路

为什么叫回溯搜索 就是一旦失败它就尝试下一个
值

一旦所有节点的所有的尝试 都尝试过了 都失败了

它就告知上一层 你上一层的赋值出现了问题

那么上一层回溯回去尝试下一个赋值

那么这个就是回溯搜索算法它的这个思想

那么我们来看一下 回溯搜索的一个例子

这个例子就是我们的这个给澳大利亚地图上色的
一个问题

那么这个是一个初始状态这个初始状态就是所有
的区域都还没有赋值 就是空的

那么假设我选择给这个变量进行赋值

那么我这个初始结点它就有三个儿子

也就是说我们每个变量的取值范围大小就是三个

就是只能取红绿蓝

所以它的分支数d 就是3

所以呢第一种尝试呢就是我们的for循环

进来for循环了 我选择了这个变量进来了

进来之后for循环就是三次 第一次这个value就是
红色

那么等于红色呢 我们就往下走

那么我看一下等于红色之后呢 同样的又去调用这
个算法

那么只不过是在这个的基础上调用

那么我们选择一个没有进行赋值的变量进行赋值

那么假设它选择的是这个变量进行赋值

那么对这个变量进行赋值的时候

同样的这个变量呢它也可以尝试三种红绿蓝

那么只不过是尝试红的时候它是违反约束的

所以在这个if语句它是不满足的 所以它就直接
pass掉了

然后尝试给它赋绿色 然后尝试给它赋绿色是符合
约束的

符合约束之后呢 然后呢 我们就变成了一种新的状
态

这种新的状态呢 我又去递归调用这种新的算法

那么在这个基础上呢在来解决这个问题

那么同样的在这个基础上再选择一个还没有赋值
的变量进行赋值

那么假设它选择的是这个变量进行赋值

那么给这个变量进行赋值的时候

本身它的取值范围也是红绿蓝三种for循环

那么你给它赋红是符合约束 if语句满足

if语句满足的话那么它又变成了一个新的状态

这个新的状态呢又去递归调用回溯搜索

那么同样的又按照同样的思维从这个没有赋值的
变量里面

选一个变量进行赋值 就这样一步步走下去

一直到它发现这个赋值方案往下走不通了

那么它就会把这个赋值方案撤销去尝试另一个赋
值

一旦某一种赋值方案往下走 走走走 走的通了

它就把这个解返回去不再试探其他的值

什么时候会回溯呢 就是当这个结点往下走走不通
了

它就回溯 回溯试探另一种值

如果整个这个结点都不同了 它就往上回溯试探另
一种值

那么这个就是这个回溯搜索算法的思想