Video在线视频

接下来我们来讲局部搜索算法

那么这个局部搜索算法为什么叫做局部呢

它和前面讲过的搜索算法有什么不一样呢

也就是说我们前面讲过的搜索算法

它都需要返回从初始状态到目标状态的这条路径

作为这个问题的解

而实际中有很多最优化的问题

它是不需要知道到达目标的这条路径

也就是说它不关心路径，它只关心状态本身

它需要算法找到一个符合要求的目标状态

那么这个目标状态本身才是问题的解

针对这一类问题我们可以采用局部搜索算法

也就是说这个局部搜索算法不记录它的搜索过程

也就是说它只记录一个或多个当前状态

然后通过不断的改进修改当前状态

直到它满足目标约束，也就是说是一个目标状态
为止

那么这个目标状态本身返回去作为这个问题的解

那么它叫做局部的原因就是因为它只储存当前状
态

那么它并不像前面一样，系统的记录从初始结点
到达后续结点、目标节点的路径

并不储存这些东西，它只是在当前状态这个局部
领域里记录它的搜索

那么这个是局部搜索算法的思想和它适用的问题

那么这种算法可以看得出来它有一个很大的优点

就是它对存储空间的要求非常的低

它只需要存储当前状态，并不需要把它走过的结
点都记录下来

所以它对于现实世界的问题

一般都是无限空间状态的问题

那么它是很有实用性的，也就是说它可以用来解
决一些实际的大问题

那么我们来看一下这里有一个n皇后问题

那么前面我们讲用系统化搜索树搜索算法来做的
话呢

它的初始状态就是一个空的棋盘

然后通过不断的每一次放置一个皇后到棋盘上面

来产生后续，通过这样的方法来搜索到目标状态

也就是树搜索算法给出的解会告诉你

第一步第一个棋子放在哪里，第二步第二个棋子
放在哪里

第三步第三个棋子放在哪里，第四步第四个棋子
放在哪里

而实际上对于这个n皇后问题我们并不关心这四个
皇后的摆放顺序

而只关心最终皇后是怎么摆放的

所以我们可以采用局部搜索的方法来做

也就是说一开始就随机的初始化一个摆放位置作
为当前状态

比如说这个就是一个随机的初始状态

当然可以约定它每一列只能摆放一个皇后

这样这个状态空间会更小一点

那么这么一个当前状态通过不断来改进它

比如说通过移动这个皇后到一个新的位置

产生一个新的状态，看这个新的状态是不是比这
个老的状态更好

如果更好它就记录下来这个新的状态作为当前状
态

然后把这个老的状态删掉，让它不占内存

然后又在新的当前状态的基础上又进行改进

也就是说它把第二列的皇后移到第四行这个位置
去产生一个新的状态

也就是说它把第二列的皇后移到第四行这个位置
去产生一个新的状态

然后他去评估这个新的状态是不是要比这个老的
状态更好

如果更好它就把这个新的状态记录下为当前状态

把这个老的状态又删掉了

所以通过这样不断的改进让这个当前状态慢慢的
向目标状态靠近

从而找到一个目标状态作为问题的解

那么这个就是用局部搜索问题来解决这个n皇后问
题的形式化以及它的思想就是这样的

那么首先我们来看到第一种局部搜索算法叫做爬
山搜索

那么爬山搜索的意思就是不断地向更高点前进

那么当然我们爬山都是一步步爬过去的所以它是
一点一点爬过去的

但是这种爬山搜索算法它有两个问题

所以大家看到这一句话

这句话就是很形象的比喻出来了爬山搜索算法的
两个问题

它就说就像有失忆的人在浓雾中攀登珠峰

这个意思就是说一个人有健忘症，那么他是不记
得他曾经到过什么地方

也就是说它只记得它自己现在处在什么位置，周
边是什么样的

然后它还是在浓雾中攀登珠峰

在浓雾中攀登珠峰那肯定就是看的不远

他只能看到他周边的地形，远处他是看不到的

所以他就会有一个什么问题呢

就是说它可能不知道别的地方有一个更高的山峰

那么我们来看到这个算法

首先看到这个算法的名字就叫爬山

它的输入就是问题的形式化

那么它返回的是一个状态

不再像以前的系统化搜索返回的是一个路径

那么这里返回的是一个状态

这个状态呢是一个局部最值点

也就是说它只能保证返回一个局部最值点给你不
能保证返回一个全局最值点

那么来看一下它的输入就是问题的形式化

然后它定义了两个局部变量

一个就是当前状态（当前结点）

也就是说它用来储存它这个当前状态

然后还有一个就是neighbor就是用来储存这个邻居
结点

那么来看一下这两个结点分别是代表什么

首先看到这个当前结点的初始化是用

问题的形式化里的一个初始状态来生成一个初始
结点来初始化的

也就是说从初始结点出发这个是我们的当前结点

然后开始往前搜索，往前爬山

首先根据当前结点产生它的后续结点

那么当然这种产生方法是根据问题的形式化

来知道它能够产生多少个后续结点

然后从当前结点产生的后续结点里面去找一个

具有最大值的后续结点

这个值就是你定义的函数用来评估这个结点的好
与坏

所以它为什么也归到启发式搜索这一大块

原因就是你同样的要定义一个评估函数来评估这
些结点的好与坏

那么在这里我们便于讲述就认为这个评估函数值
越大越好

所以它是挑一个有最大值的后续结点出来

也就是说具有最好的后续结点出来放到neighbor里
面去

然后看一下这个neighbor（最好后续）的值，是不
是要比当前状态这个结点的值要小

那么要小的话就是说更差

我们刚才讲了这个值越大越好

那么如果你的评估函数值是越小越好你换一下符
号就行了

就是这个地方换成大于等于就行了

那么假设我们当前结点产生的后续结点里面

最好的一个后续都比当前结点要更差

也就是说要更差，要更差那就意味着什么

那就意味着我当前这个结点所在的状态就已经是
一个局部最值点了

也就是说我周边，我的邻居，我的儿子们

无论我怎么做我都会走向一个更差的结点

那他就不动了，它就把这个结点对应的状态返回
去作为问题的解

所以就是返回一个他认为是找到一个最值点了

尽管这个最值点可能是局部最值点，返回去了

否则的话，也就是说最好的这个儿子结点比当前
结点要更好

那么它就往前走了，它就开始爬山了

我一看我的周边有个更高点，它就走到周边去了

它就走到这个更好的最好的后续结点去了

也就是说当前结点存储的就是这个最好的儿子结
点

然后进行下一次的迭代，慢慢的往高处走

知道走到一个地方发现它怎么走都会更差，就把
这个状态返回去

这个就是爬山搜索

所以我们看得出来为什么是在浓雾的天气中爬山
呢

因为当它走到这个局部最值点的时候

他并不清楚前方更远处有一个更高的山峰

它看不到所以它就把这个局部的最值点返回给你

另外一个有失忆就是说它任何时候都只储存一个
当前状态

也就是说它只储存当前状态

那么这个旧的当前状态老的状态都全部删掉了，
不记得了

那么我们可以看得出来这个爬山搜索算法非常的
依赖于这个初始状态

很容易陷于局部最值点

就像这里一样，这是我们的一个目标函数

你要去找这个目标函数的一个最值点

那么这个是我们的状态空间

假设我们的初始状态在这个位置

那么在这个位置的话呢

比如说初始状态也就是说当前状态在这里

那么它的两个儿子状态也就是说两个邻居状态

它发现这个邻居状态往上走，这个邻居状态的目
标函数值更大

所以它就会选择慢慢的往上走，慢慢的往上走

走到这里的时候它发现它的两个邻居状态

也就是说它的两个后续状态值都比它更差

值都更小，所以它就会把这个值返回去，不再搜
索了

那么其实是这个值是一个局部最值点

但是如果你的初始状态在这里

那么它就可以慢慢往上走找到一个全局最优点给
你

但是你的初始状态在这里

慢慢往上走走到这里的时候它也会发现我的邻居
状态都不比我好

它也会把这个山肩值返回给你

所以它是很容易陷于局部最值点的

如果你的目标函数有很多很多的局部最值点

那么用爬山搜索算法是极有可能是找到一个局部
最值点

当然有一种方法就是你使用不同的初始状态

多运行几次爬山搜索算法，然后从里面挑一个最
大的值作为这个问题的解

那么我们来看一下用爬山搜索算法来解决这个八
皇后问题

那么这个八皇后问题，假设我们采用的是这么一
个评估函数

这个评估函数定义成互相攻击到的皇后对数

那么当然互相攻击到的皇后对数越多越差

所以这里面就是越多越差

所以我们好的话就应该是这个值小的更好

那么比如说这个状态它的h值就是等于17

也就是说有17对皇后可以互相攻击的到

比如说像这里这三个，这三个两两之间都攻击的
到

那就有三对皇后互相攻击的到

那么这里有四个有六对皇后互相攻击的到

也就是说三四一十二除以二，二三得六除以二

所以这个是3，这个是6就有九

然后再看这条线这有一对10

然后再看这个，没有，这个11，12

然后再看这个行13，再加这个16，然后这个17

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

那么对于这个状态它的评估函数值就等于17

那么像这么一个状态它就是

我们来看一下这个状态，它的评估函数值等于1

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

我们来看一下是哪一对呢

是这一对，这一对皇后可以互相攻击的到

那么对于这么一个状态它就是一个局部最值点

为什么呢，不管你怎么动这个皇后

当然我们限定它一次只能动一个皇后

也就是说它的邻居状态是通过对当前这个状态动
一个皇后得到的

才是它的邻居状态、后续状态

那么不管你怎么样动一个皇后

它所得到的后续状态都会比当前这个状态要更差

也就是说这个互相攻击到的皇后对数都会更多

所以如果你的爬山搜索到达这个状态

它就会把这个状态返回来，作为这个问题的解

而这个状态其实上只是一个局部最值点

也就是说它还并不是完全符合要求的

也就是说它里目标要求还是差一点

那么这个是爬山搜索的一个问题

它很容易陷于局部最值点