漫话人工智能系列 | 智能的支柱：算法

分治算法顾名思义是“分而治之”的意思。

这种算法的主要思路是将复杂的大问题分解成几个类似的小问题来解决。

这和我们生活中应对复杂问题时的思路类似。请看下面这个经典问题：

用图1所示的方法，我们可以知道解决这个问题，只需要3步操作：

■图1 步称出特殊的小球

这个找出特殊小球的思路就是分治算法的体现，每次划分，我们都是将一个大问题化为 小问题，小问题的规模（球数量）比大问题小，但是解决原理和方法均与大问题相同。

在将大问题划分到足够小的时候（即只有两个小球时，我们且称此为“最小问题”），“最小问题” 是很容易解决的。同时在这个“最小问题”中，那个特殊的球同样也是大问题中的特殊球。

分治算法能够很好地将大问题化解为小问题，从而更好地解决问题。在我们的生活中，将一个看起来难以实现的大目标分解为几个小目标，通过一个个完成小目标最终完成大目标，也是分治算法的体现。

动态规划算法是一种优化算法，在程序设计过程中也很常用。

这种算法也会对大问题进行分解，但与分治算法不同的是，动态规划往往是将问题划分为几个相互关联的小问题。

这样说有点难以理解，我们不妨看一个生活中的小例子。

如果我们想从北京开车到上海，打开手机导航软件，导航就会给我们推荐如图 2 所示的最短线路，选择这个最短路线就使用了动态规划算法。

■ 图2 北京到上海的路线规划

当你开车到天津之后，你又一次搜索了路线，想看看有没有更近的道路，但搜索的结果还是如此。

于是你继续沿着这条线路开车到南通。在南通，你想着之前两次搜的路线分别是从北京到上海,以及从天津到上海，路程跨度太大，可能不够精确，于是你在南通又一次拿出手 机搜索路线，结果还是和我们最初搜到的路线相同。

为什么会有这样的结果呢？这是由动态规划算法的特点决定的。

如果你想得到从北京到上海的最优路线，首先要将这个大问题分解为几个小问题，例如分解为从北京到天津、天津到东营、东营到连云港、连云港到南通、南通到上海这几个步骤。

如果希望找到从北京到上海的最佳路线，就意味着从北京到天津也是最佳路线（通过反证法就可以轻松证明），同理，从天津到东营、从东营到连云港、从连云港到南通以及从南通到上海的路线也需要是最佳路线。

最后，程序将这些最佳路线合并在一起，就成了从北京到上海的最佳路线，我们在沿途各个城市搜索线路时，得到的路线都是一样的。

除此之外，动态规划在一些预测模型上也有广泛应用，例如对于水体污染物的扩散预测。我们可以将水体污染物浓度变化这一过程按照一定的时间间隔分解成多个小过程。

每一个过程污染物的起始浓度都是上一个过程污染物的终浓度，并且这个过程是无后效性的。通过动态规划，我们能够提前预测污染物的扩散和稀释，采取相应的措施。

动态规划在预测天气方面也能发挥较好的预测效果，是一种优秀的、有着广泛应用的优化算法。

回溯算法与分支限界算法有一定相似性，因此我们将二者一起介绍。

回溯算法的思路是不断地进行试探，如果试探的方向不可行，它会回到上一个可行的步骤，去探索另一条道路；如果试探的方向可行，则继续进行下一步，并且将这条路得到的结果记录下来，作为一个解。

因此，无论多么复杂的问题，都能够用“不断探索”的回溯算法来解决。

分支限界算法的思路与回溯算法非常接近，但回溯算法能够搜集出所有的解，而分支限界只会求出一个解。

因为一个问题可能会存在多个解，因此分支限界需要提前设定规则，以找到最合适的解，例如直接将最先得到的解作为最优解，或是让算法按照某个特殊规则进行判断，找出最优解。

这两个算法的具体步骤是先搜集所有解的可能性，然后按照一定的规律逐个尝试，直到找出所有的解或某一个特定解。

回溯算法最典型的应用是“八皇后”问题，即在国际象棋的棋盘上放置八个皇后（皇后能够在横、竖、斜三条线上随意直线移动），每个皇后之间不能相互攻击，见图3。

按照回溯算法的思路，首先会确定第一个皇后的位置，然后依次确定后面皇后的位置。假设在放置第六个皇后时发现没有位置可放，则会重新退回第五个皇后的位置摆放，在调整 第五个皇后位置之后再摆放第六个皇后；如果第五个皇后的所有摆放位置下都无法摆放第六个皇后，则会退回第四步（摆放第四个皇后位置）……以此类推，直到找出所有的摆放方式为止。

如果用分支限界算法的方法，则为找到其中的某一个摆放方式。通过上面的例子我们可以看出，只要是能用穷举法解决的问题，几乎都能够用回溯法来解决。

■ 图3 “八皇后”问题示例

我们经常听到“人类是贪婪的”这句话，人的贪欲往往造成各种各样的灾难，小到邻里关系的破裂，大到国家间的战争。

但是，你有没有想过计算机算法也可以是“贪心”的呢？一个“贪心”的算法不仅不会带来巨大灾难，反而能解决生活中很多的实际问题。

我们常常在生活中不自觉地使用了贪心算法。

在详细介绍贪心算法之前，我们来回想一下在没有支付宝和微信支付的时候，我们用现金买东西的过程。

在炎炎夏日，你走进一家店铺， 拿了一支雪糕，标价为2.3元。这时你刚好没有零钱，只好递给收银员一张百元大钞，收银员算了几秒钟后知道需要找回你 97.7 元。

问题来了，收银元会怎么把这97.7元给你呢？

收银员当然希望找钱时给你尽可能少的钞票数，这样才能保证有足够的零钱找给其他顾客。

所以，你大可不必担心收银员找给你977 张1角的纸币，或是 97张1元纸币外加7张1角的纸币。假如收银员手里各种面值的纸币都很充足，那么收银员最可能找给你的是1张50元、2张20元、1张5元、2张1元的纸币，加上1个5角、2个1角的硬币。即使收银员没有50元，那也最有可能用2张20元和1张10元来代替，而不是用5张10元或 10张5元代替。

买东西找回零钱，这几乎是生活中再平凡不过的一幕了，但恰恰是这平凡的一幕蕴含了计算机算法中的贪心算法原理，很多超市收款机的找零提醒程序采用的就是贪心算法。

顾名思义，贪心算法就是要和贪心的人一样，只做出在当前看来最好的选择，而不是站在统观全局的角度来做出选择。

虽然“贪心”是一个贬义词，但贪心算法的运用极大地提升了社会运行效率，如为物流机器人、外卖配送员规划路线等方面，贪心算法都能提供够更好的服务。

贪心算法的思路较为简单，且能够很好地解决生活中的很多实际问题，因此在现代程序设计中占有一席之地。

• 三段论是什么，它与人工智能有哪些关系？

• 计算机是怎样从笨重的庞然大物变成如今千家万户的必需品的？

• 如何理解看起来高深莫测的计算机算法？

• 如何判断和你在网上对话的“人”是不是一台电脑？

• 所谓的“机器学习”如何理解，机器是如何学习的？

• 机器视觉是怎么一回事？机器如何感知万物？

• 我们未来应该如何与人工智能共存？