人工智能不智能-非递归深度优先搜索的简述

人工智能？

现在人工智能很火爆，人们普遍认为计算机可以自己思考、自己决策，从而使人类的能力倍增。实际上，计算机本质上并不怎么智能，与它的名字相符，它只是计算能力很彪悍、很暴力而已。例如，计算机其中一项彪悍的能力，就是可以比较轻易的帮人类穷举生活中成千上万种排列组合事物的价值（不依靠计算机的话，穷举排列组合会很耗时），估值结果可以帮助人类做出最经济的决定，这可以理解为计算机辅助统筹学。人类常见的一些活动，例如工程项目建设计划、棋类游戏求解、运输路径规划等，都可应用这类统筹方法。这种统筹方法，其中一种基本思路就是穷举所有需统筹的推向的所有可能排列组合，并分别计算各种排列组合的价值，最终挑选价值最优的方案，这在计算机算法中一般被称为搜索。

搜索算法有很多种，最基础也是最常见的是深度优先搜索算法，其本质方法是，穷举排列组合时，每次列出其中一种排列（或组合），然后计算其价值，接着再列下一种，直到所有排列（或组合）被穷举，有时候这种方法也叫回溯法。

深度优先搜索=回溯法？

“深度优先”搜索这个名字，是比较充满想象力的，它把对排列组合的搜索想象成对一棵树的遍历，每次都完成一条从树根到树叶的路径的遍历，所以叫深度（从树根直落到树叶）优先搜索。

“回溯法”这个名字，则突出这种搜索算法的关键点，也就是在某种排列（或组合）已经无法再穷举下去的时候，要回退到之前的状态，也就是回溯，形象点来说，就是我们玩高难度游戏时喜欢在关键点存档，等后续游戏过关失败的时候，就读档，回退到关键点，换一种打法来过关。我觉得，“回溯法”这个名字更能表现这个算法的关键之处，就是要在必要时，回退到之前的状态，并寻找另一种可能的路径。下面，就以一条中学题目为例子来介绍一下回溯法。

实例解释

设要将n件工作分配个n个人，每个人只能被分配一件工作，每一件工作只能被分配给一个人，人和工作都以0到n-1编号，将第i号工作分配给第j号人所需的费用为C(i,j)，对于给定的n和集合C，设计一个算法，计算最佳的工作分配方案，使总费用达到最小。

算法伪代码

很显然，这是一个求n的全排列的题目，共有n!种排列。可以用回溯法来解，时间复杂度是O(n!)。如前面说的，回溯其实就是存档，要先设计一个存档数据结构，保存每一个关键点的全部信息，并在当前状态无法再穷举时进行回溯（回退到上一个可以继续进行穷举的状态）。一般来说，这个数据结构会包含以下内容。

一、当前已完成工作分配的人数。

二、当前工作分配的方案。

三、当前工作分配方案的费用。

四、用于辅助计算工作分配可行性的变量。

有了关键点的数据结构，我们就可以着手构建回溯算法了，其基本的思路如下。

一、初始化i为0。

二、初始化j为0。

三、如果j大于n-1，说明本次分配方案已不可行，需要触发回溯，跳转至步骤九。

四、如果第j号工作没有被分配过，说明第j号工作可以用于分配，跳转到步骤五；否则，尝试下一种可能，将j加1，再跳转至步骤三。

五、为第i号人分配第j号工作；标记第j号工作为“已分配”。

六、如果i小于n-1，说明还没有完成分配方案，应该做下一个人的工作分配，将关键点数据结构存档，i加1，跳转至步骤二。

七、如果i等于n-1，说明已完成一次分配方案，计算该分配方案所需的总费用，如果总费用小于“最小费用记录”，则把该分配分案记录为“目标方案”，并用总费用替代“最小费用记录”。

八、再尝试下一种可能的工作分配，将第j号工作标记为“未分配”，j加1，跳转至三。

九、进行回溯，读出最近一次存档，如果已经没有更多的存档，证明已经尝试完所有的方案。输出之前记录的“目标方案”和“最小费用记录”，结束整个搜索过程。

十、如果有存档信息，则用存档中的信息重置“当前已完成工作分配的人数”、“当前工作分配的方案”、“当前工作分配方案的费用”等信息。

十一、用重置后的状态，尝试下一种可能的分配方案，j加1，跳转至步骤三。

算法重点

上面是一个完整的回溯法实现思路，其关键的执行过程可以总结为四个小过程。

一是依次尝试给第i号人分配0到n-1号工作。

二是将成功分配的状态存档

以上两步，如下图所示

三是在第i号人已经完成从0到n-1的所有工作分配尝试时，触发状态读最近一次的存档（回溯）。

四是读档后，要用读到的数据，重置所有状态，并继续尝试给第i号人分配下一个工作。

以上两步，如下图所示

为什么不用递归

学过“栈”数据结构的同学或许已经看出来，实际上这几个过程刚好能用得上“栈”先进后出的特性，因此很多人直接用“栈”来实现存档的动作。也由于一般的编程语言都支持函数调用，而函数调用刚好就是用操作系统自带的“栈”来实现函数调用上下文的保存和恢复，因此很多人为了省事就直接用函数递归调用来模拟这个回溯的存档读档过程。一般来说，这样做是没问题的。但是，在搜索深度很大时（也就是n很大时），有些操作系统的“栈”往往不够用，会溢出崩溃，这点在嵌入式系统的开发中尤为明显。所以，我们应该鼓励自己编写回溯的全过程，尽量少依赖函数递归调用。

优化

由于回溯法的时间复杂度为O(n!)，相对是一个低效的算法。因此，在搜索的过程中，应该尽早摒弃无用的搜索分支。以上题为例，如果在进行工作分配时，即使未完成所有人的工作分配，如果发现累积的费用已经比的“最小费用记录”要大，则继续分配下去已经没有意义，应该果断尝试下一种分配方案。为了提升程序的效率，保持算法的实用性，使用回溯法时，通过缩减搜索量提升效率是不可或缺的工作。

后记

写这篇短文的原因，是由于有位初中小朋友问我搜索方面的问题，解答过程中，感觉学校里的老师对这方面的介绍有点不够全面，因此把自己的经验和理解写下来，希望可以帮到对此有兴趣的大小朋友们。同时，这也是缅怀自己儿时求学路，人生易老，且行且珍惜。