认真聊AI | 搜索技术

原创内容

No.704

认真聊AI | 搜索技术

书接上回，本期AI的内容到了搜索技术~

图片由海艺AI绘制

提到搜索技术就不得不提到搜索问题。你或许曾经见到过一些智力游戏，其中有一类问题就属于搜索问题：

一个农夫需要带着一只狼、一只羊和一筐白菜过河。他的船很小，每次只能装下他和一样物品。如果农夫不在场，狼会吃掉羊，羊会吃掉白菜。农夫需要找到一种方法，使得所有物品都能安全过河。

这种问题我们通常是需要进行反复的努力和试探才能最终找到解决方案的。现实情况下，遇到这种问题，我们需要找到的东西可不止可行解，可能还会涉及到最优解的问题。现实的问题可能不像狼菜过河这种问题一样有着非黑即白的规则，但是找到最优解的场景非常多。

上面这种问题，如果要是定义成比较技术化的描述就是这样的：

定义状态：用一个元组或四元组表示当前的状态，例如 (农夫, 狼, 羊, 白菜)，每个元素可以是 0（在河这边）或 1（在河对岸）。

确定合法状态：在任何状态下，如果农夫不在场，狼和羊不能在同一侧，羊和白菜也不能在同一侧。

生成状态转移：从当前状态出发，生成所有可能的下一个状态。

搜索解决方案：使用广度优先搜索（BFS）或深度优先搜索（DFS）找到从初始状态到目标状态的路径。

剪枝条件：在搜索过程中，如果发现某个状态已经搜索过了，或者某个状态不符合问题的约束条件，就可以将其从搜索路径中剔除，以避免无效搜索。

这种解决问题的方法也就是搜索技术。如何在一个比较大的问题空间中，只通过搜索比较小的范围就找到问题的解。

暴力穷举看起来简单，但是暴力穷举排列组合在搜索问题中往往会有爆炸的问题。在搜索问题中，最重要的就是要通过搜索策略解决组合爆炸的问题。换句话说，就是要寻找一种能够最短时间内得出结论的搜索策略。

搜索策略有两种基本的方式，一种是不考虑给定问题所具有的特定知识，系统根据预先确定的某种固定顺序排序，依次调用规则或者无序调用规则。我们称这种搜索方法为盲目搜索或无信息引导的搜索方法。另一种方法则是刚好相反，我们在搜索的时候考虑问题本身可应用的知识，动态地进行排序，优先搜索合适的规则。这种方法也被称作启发式搜索方法或者有信息引导的搜索策略。

以下是一些常见的搜索策略：

接下来我们逐个简单介绍一下这些搜索策略。

图搜索策略对于各位数据分析师来说看起来是个新鲜陌生的词汇，但是这个东西大家一定不陌生。

看到上面这些图大家有没有一种熟悉的感觉涌上心头？没错，图搜索策略如果有图示表示的话和小学的时候学得概率问题二叉树是基本一样的。事实上很多问题都可以用这样的二叉树来表示，只不过相比我们小学就学到的二叉树要复杂一些。但思路是一致的，说白了都是一种类似穷举的操作。

我们在实际执行的时候，为了提高搜索的速度，图搜索并不是先生成所有的状态连接图再进行搜索的，而是边搜索边生成图，一旦找到了合适的答案搜索就停止了。在搜索的过程中，生成的无效的状态越少，搜索的效率就越高，所对应的搜索策略就越好。在一些关键的节点，我们还可以通过已有的知识对这选择进行干预，如果有干预了则称之为启发式搜索，否则就是盲目搜索。

盲目搜索看起来有种纯靠撞大运的感觉，但是盲目搜搜可能没有你想象中那么盲目，我们可以分为深度优先策略和宽度优先策略。

深度优先搜索策略，顾名思义，就是优先扩展深度最深的一个节点，如果有相同深度的多个节点，则按照事先的约定从中选择一个。如果该节点没有子节点，则选择一个除了该节点以外的深度最深的节点进行扩展。依次进行下去，知道找到问题的解结束。

然而深度优先策略有时候会遇到死循环的问题，比如在N皇后问题上（在一个N*N的翻译胡想起棋盘上拜访N个皇后棋子，要求每行、每列和每个对角线只能有一个皇后）。为了防止这种问题的出现，一般情况下我们会人为地设置一个最大深度，这个深度的设置和具体的问题有关，稍微有点看经验，设置得太深了影响解题效率，设置得太浅了又有可能找不到问题的解，这就是所谓的玄学调参吧。

和深度优先策略相反的就是宽度优先策略，优先搜索深度最浅的节点。省略到复杂的证明过程，直接说结论，在问题有解的情况下，宽度优先策略一定可以找到最优解。但是由于宽度优先策略需要保存之前搜索的结果，所以宽度搜索策略需要占用较大的存储空间，而深度优先策略虽然不能保证找到最优解，但是可以大大节省存储空间。

在搜索的过程中引入启发信息，减少搜索范围，以便更快地找到问题的解，这种搜索策略称为启发式搜索。

A算法和A*算法是常用的两种启发式搜索算法，我们首先介绍一下A算法。

搜索算法最终的目的就是为了找到一个从初始节点到目标节点上一条最近的路径，那么如何评价一个节点在最佳路径上的可能性呢？A算法给到了一个评价函数的定义：

f(n)=g(n)+h(n)

n：待评价的节点；

g(n)：从初始节点S到节点n的最佳路径耗散值的估计值；

h(n)：从节点n到目标节点t的最佳路径耗散值的估计值，称为启发函数；

f(n)：从初始节点s经过节点n到达目标节点t的最佳路径耗散值的估计值；

耗散值：路径的代价，可以是路径是长度也可以是需要时间或者花费的费用等。

如果f(n)能比较准确地估计出s-n-t这条路径的耗散值的话，我们每次从叶节点中选择一个f(n)值最小的节点进行扩展，则有理由相信这样的搜索策略有利于我们尽快搜索到一条从初始节点s到目标节点t的最佳路径。

在A算法中，我们并没有对h(n)做出什么界定，这就会带来另一个问题，A算法的结果如何其实不好评价。如果我们给h(n)这么一个限制：

h(n)≤h*(n)

这样我们就可以证明，当问题有解的时候，A算法一定可以得到一个最优解。因为多了一个对h(n)的限制，这种算法也被称为A*算法。

看到了上面的内容之后，或许已经有朋友联想到了计算机在围棋领域的成就。计算机下围棋其实也是一种搜索问题，但并不是穷举的暴力解法，这种搜索问题的解法被称为博弈搜索。

被写入历史书的国际象棋大战深蓝，采用得算法叫做α-β剪枝算法。该算法的基本思想就是利用已经搜索过的状态进行剪枝，以提高搜索效率。算法首先按照一定原则模拟双方下棋，直到向前看几步为止，然会对棋局进行打分，并将该分数向上传递，搜索其他可能的走法时，会利用已有的分数剪掉对我方不利的走法。

这一套算法在国际象棋、中国象棋、日本将棋领域都表现得非常出色，但是到了围棋的领域却不灵了。这种不灵的原因一方面来自于围棋本身的状态更多，但更大的原因在于围棋很难对棋局进行打分。“算人常欲杀，顾己自贪生。”围棋中没有一个将军这样的获胜标志，计算一下现在的牌局打分就得考虑到所有的棋，还是有点难的。于是在很长一段时间里，计算机围棋都达不到业余棋手的水平。

直到2006年蒙特卡洛树搜索方法的出现，计算机在围棋这件事上才有了突破。

蒙特卡洛方法是一类随机模拟方法的总称，比如著名的蒲丰投针：

取一张白纸，在上面画上许多条间距为 a 的平行线；

取一根长度为 l（其中 l≤a）的针，随机地向画有平行直线的纸上掷 n次，观察针与直线相交的次数，记为

m；

计算针与直线相交的概率，这个概率可以用来估计圆周率 π的值。

由于围棋不同于象棋的特殊点，就有人想到了用蒙特卡洛随机模拟的方法对棋局进行估值。思路也不难，随机地模拟双方走步直到分出胜负为止，通过多次模拟就能算出下棋点获胜率最大的走。这个思路确实简单，但是计算量非常大，于是围棋程序在执行的时候会边模拟边建立一个搜索树，父节点可以共享子节点的模拟结果，以提高搜索的效率。

这个过程就有点像人在下棋时的思考了，人在思考的时候会考虑可能的走棋点的轻重缓急，重要的点多考虑，次要的点不考虑。那么计算机又是如何做到的呢？答案是引入了一个信息上限决策的方法。按照这个方法，计算机要考虑两个因素：一是优先选择模拟过程中到目前为止胜率最大的节点，以进一步考察它是否是一个好的点；二是优先选择那些到目前为止模拟次数比较少的点，以考察这些点是否有潜在的好处。

当然，AlphaGo实际采用的算法和思路远比这里介绍得要复杂得多，这里就不做更多的介绍了。

总的来说，搜索技术/算法还是很值得大家去了解的，这种求最有解的思路在商业分析的实战中其实也是非常实用的。毕竟我们做商业分析，经常要输出的一个结论就是老板做商业决策的最有解嘛。

下一期，我们来聊聊群智能算法。

二号姬

半路出家自学成才的文科数据人，看过了大厂的风景也做过了小厂的CDO~目前是闲职，写写稿带带学生，欢迎勾搭~