令计算机也“烧脑”的NP难问题，怎样寻求最优解？-热讯书画网

令计算机也“烧脑”的NP难问题，怎样寻求最优解？

科普中国网 2023-06-28 11:22:07

计算机科学中，有一类问题叫作NP难问题（NP-hard problem）。这里的“难”不是指没办法解决，而是指找到这类问题的最优解所需的时间会随着问题规模的扩大而急剧增加。

图片来源：图虫创意

典型的NP难问题是旅行销售员问题。关于这个问题的描述非常的简单：

(资料图)

地图上有若干个城市，每两个城市之间的距离是已知的，现在让你求出一条经过所有城市，并且最终回到出发点的距离最短的路线。

费力不讨好的“暴力穷举”

这个问题非常重要，小到餐厅送餐，邮递员送货；大到几个城市之间工业运输路线的规划，背后都是旅行销售员问题。数学家从理论上证明，要想找到最优路线，只能暴力穷举（brute force），即把所有的路线都列举出来，然后分别计算长度，最后找一条最短的路线。

用这种方法虽然可以保证找到最优路线，但算法所需的时间会随着节点（城市）数量的增加而急剧增加。

例如，7个城市共有720种排列方式，列出720条路线并找到

最短的路线看起来还不算太麻烦，但是这只是针对7个城市。10个城市的排列方式猛增至362880种。若有26个城市，排列方式就有1.5×1025种，这已经远远超过科学家估测的宇宙中所有恒星的数量。

而在实际应用中，旅行销售员问题所涉及的节点数量可能有成百上千个。

那么面对这样的问题，我们该如何解决呢？

一个接近最优解的解，可能是正是你需要的

计算机科学家设计了很多启发式算法（heuristic algorithm）。简单来说，这个算法可以帮助我们得到一个接近最优解的解，并且其计算出解的速度比正常计算最优解的速度快得多。

针对旅行销售员问题，有一个简单的启发式算法叫“最近邻居法”：从任何一个城市开始，每访问的下一个城市都是距离当前城市最近、同时尚未被访问的城市。

计算机科学家在设计一个启发式算法时，会试图从数学上找到该算法的近似比（approximation ratio），即最优解和用启发式算法找到的解的比值。例如，有一个启发式算法的近似比是2，这意味着该算法可以快速为旅行销售员问题找到一个解，并保证这个解对应的距离在最差情况下不会超过最佳路线对应的距离的2倍。有人可能会问：“如果你无法有效地找到最优解，如何保证用启发式算法找到的解的大小不超过最优解的2倍？”这确实令人惊讶，而且看起来很神奇，但是在数学上是可以做出这样的保证的。

为旅行销售员这个问题找到启发式算法，就是用弊（性能下降或距离变长）来换取利（速度快）。并且更重要的是，近似比表示了弊的大小，让弊变得可控。如果你可以接受某个启发式算法的弊，那么你就可以放心地用它解决实际生活中的问题。

这就是用“可控的弊”换取“更大的利”。

怎样用“可控的弊”换取“更大的利”

上文中的思想在实际生活中有很多应用。

在美国，森林野火每年都造成很严重的破坏。过去很多年，美国林务局应对森林野火的治理政策是野火必救：一旦在野外发现小火苗，就立刻派人扑灭。但是这种方法似乎没有降低发生大规模森林火灾的概率。

美国生态学家艾伦研究发现，干旱使很多树木枯死，这时候一旦发生火灾，这些树木会瞬间让森林燃起熊熊烈火。因此他建议，火灾发生时，应该在可控范围内让枯死的树木适时地被烧光，不要因累积过多枯木造成不可收拾的大火。

于是美国林务局在 2013 年修改了野火治理政策，不再实施“野火必救”，而是强调消防规划和燃烧控制，主动在可控范围内让森林的野火把枯木和其他易燃物一起烧掉。这样做降低了大规模森林火灾发生的概率。

这就是用可控的弊，换取更大的利的实际应用之一。

此外，打疫苗也是如此。打疫苗的本质是让少量病毒感染你，从而让你产生抗体。疫苗中的病毒对身体造成的伤害非常轻微，这个弊是可控的。而打完疫苗后，我们的机体产生了免疫力，这个好处远大于打疫苗带来的不适。

类似的例子还有，2013 年某影星宣布自己接受了乳腺切除手术以降低患癌风险。因为她有乳腺癌家族史，并且她身上携带一种特殊的突变基因，而携带该突变基因的妇女一生中患乳腺癌的概率为80%，术后患乳腺癌的概率则会降至5%。这种预防性的乳腺切除，就是主动用可控的弊，换取更大的利。

兵书中有一个被称为“围城必阙”的心理战术，是指在攻城之时不将城池全部包围起来，而是打开一个缺口让敌人逃跑。因为如果敌军深陷重围，无处可跑，觉得没有活路，就必定会拼死抵抗，而放开缺口可能会放跑少数敌人，但带来的好处是瓦解敌人的士气，歼灭大部分敌人。

这也属于主动用可控的弊，换取更大的利。