使用启发法

计算机科学所面临的最难的问题是超多项式时间问题，这类问题的输入规模一增加，所需的计算步骤就翻倍，或者比翻倍还快的增长！当输入规模很小时，计算机还能解决这类问题，但随着输入规模的增长，很快，计算机就需要数月或者数年的运行时间。

计算机科学家使用不同的方法来解决这类棘手的问题：不试图找到 最优解，而是寻找一个 近似最优解。就算近似最优解也比没有解要好。

寻找问题的近似解可以使用启发式算法，这是一种寻找较优算法的技巧。启发式算法并不是彻底搜索所有可能并找出最优解，而是用更快的速度得出一个还不错的近似解。也就是说，启发式算法牺牲了准确性和全面性，换取了较高的执行效率。

为了更好的了解启发式算法，我们把计算机科学中最负盛名的难题拿出来练练手。

一个旅行推销员提出了这样一个问题：

“给定一系列城市，以及任意两个城市之间的距离，能不能找到一条不重复不遗漏的、能够访问每座城市并回到起点的最短路线？”

例如，下图显示了46个德国城市之间的最短访问路线：

旅行推销员问题（TSP）最早是推销员所面临的问题，但实际上它跟很多领域都相关：在网络中数据发送的路线、微芯片的制造、用天文望远镜观察各个目标、甚至还有DNA测定排序。所有这些例子，都包含求解通过各点的最短路径的问题。

TSP 是个组合问题，这也是它这么困难的原因。计算机得到最优解的唯一方法是“暴力解法\枚举法”：尝试所有可能的路线，计算每条路线的路程，然后找出路程最短的路线。

下面的图形区域生成位置随机的四个城市，计算所有可能的路线，并标出最优路线。你可以点击路线查看图中的演示，或者重新生成新的城市。

你注意到总是有 两条 最佳路线了吗？两条路线看上去一样，但是反向的。实际上这都是最佳路线，推销员选两条最佳路线的任意一条都行，路程一样。

计算机解出4个城市的所有路线并不会花很久——用我的电脑只花了不到十分之一毫秒。而5个城市问题、6个城市问题以及7个城市问题也仍然很快如果你信任自己的电脑的话完全可以亲自试试。但运行时间是指数增长的，从几毫秒迅速增加到几秒。

下表是我的电脑运行4城市问题到11城市问题的时间：

注意到最后从520直接跳到5770了吗？从那一刻起我决定不再继续折磨我可怜的笔记本了。

照此速度计算，电脑计算最开始图中的46个德国城市的所有路线，则需要 $2^{53}$‍ 毫秒。这大约是 $6^{42}$‍ 年，远比宇宙的年龄还要长的多。当然，世界上有很多比我笔记本快得多的计算机，但就算是再快 200,000 倍，仍然需要 $3^{37}$‍ 年。

那之前的46城市的最佳路线是怎么算出来的？当然是用启发式算法！

有一种产生启发的方法是将你自己带入问题中：如果你是那个推销员，你会怎么办。人类不喜欢在看起来没用的方向上浪费时间，所以我们一般都会找到些窍门，使用这些窍门来得到一个足够好的解。

下面的图形区域显示5个随机城市。你可以从A开始点击城市点，规划你自己的路线，完成之后，你就会看到你的路线跟最优路线相比表现如何。

与最佳路线比，你选的路线表现如何？你决定城市顺序的时候使用了什么启发式？计算机能使用这个启发式吗？

启发式和启发式之间有不同，但是所有启发式都能为我们提供不同的思路，来引导计算机更快的找到一个还不错的解。

TSP问题的一个常见的启发式是“最近邻居法”：从任何城市开始，每次访问的下一个城市都是距离当前城市 最近、同时又是尚未被访问过的城市。

在下面的图形区域试一试。现在我们在用启发式算法，你可以尝试计算更多的城市。就算46个城市我的电脑也只需要几毫秒时间。

大开眼界对吧？不用启发式的时候，要找到最优路线，我们可能得等到宇宙热寂。现在有了一个简单的启发式算法，我们几乎瞬间就能得到结果。

但请记住，启发式算法只能得出 近似 解。这个最近邻居法找到的路线，平均来说比最优路线长25%。而有的时候最近邻居法给出的路线不但不是最短的，反而是 最长 的。

计算机科学家为TSP问题找到了数十种其他的启发式算法，包括“蚁群算法”，这是受到蚂蚁在寻路过程中释放信息素行为的启发而发明的算法。对每个启发式算法，科学家们都会分析该算法的解与最优解的差异大小，计算效率的高低，以及最坏结果出现的频率。

除了TSP问题之外，还有很多其他问题从启发式中获益。

这里列出几例：

背包问题：你有一个背包，以及一系列类型的货品，每种类型都有自己的重量和价值。若你想要背包中的货物总重不超限额，而且总价值最大，那么每种类型的货物装多少？这类问题在很多不同的行业领域都会出现，比如投资顾问如何选择投资组合，以及加工厂如何最节省的切割原材料。一个启发式算法是在选择下一个货物装进背包时，把货物按价值/重量的比值排序，最靠前且不超重的货物被选中。

博弈问题：如果计算机想要在跟人类下棋中获胜（或者至少输得体面），那么在每一步时计算机都需要找到获胜可能性最大的一步棋。为了真正预测获胜，计算机需要遍历从当前步到最终步的 整个 决策树，其中要包含人类对手所有可能的应招。最简单的井字棋共有 $362,880$‍ 种可能的下法，而更复杂的国际象棋的可能性则有 ${10}^{120}$‍ 种！幸运的是，类似“极小化极大算法”的启发式可以帮我们砍掉决策树中不必要的分支，大大减少计算量。

选址问题：一个大型连锁超市在本省内有 20 个门店，现在需要建造 5 个仓库，向各超市运送食品。其目标是尽量减少成本并最大限度的提高运送速度。选址问题就是找到这 5 个仓库的最优位置。而一个网络应用如何安排自己的服务器，以便对用户请求做出最快速的响应，这样的问题同样也是选址问题。类似“局部搜索算法”的启发式可以减小可能地址的数量，从而提高效率。

所有这些问题都是组合问题，计算机为得到最优解所需的计算量是以指数增长的。组合问题在现实生活中很常见，因此相关公司和计算机科学家都对能得到最好近似解的启发式算法非常关注。