計(jì)算機(jī)科學(xué)中，有一類(lèi)問(wèn)題叫作NP難問(wèn)題（NP-hard problem）。這里的“難”不是指沒(méi)辦法解決，而是指找到這類(lèi)問(wèn)題的最優(yōu)解所需的時(shí)間會(huì)隨著問(wèn)題規(guī)模的擴(kuò)大而急劇增加。

圖片來(lái)源：圖蟲(chóng)創(chuàng)意

典型的NP難問(wèn)題是旅行銷(xiāo)售員問(wèn)題。關(guān)于這個(gè)問(wèn)題的描述非常的簡(jiǎn)單：

【資料圖】

地圖上有若干個(gè)城市，每?jī)蓚€(gè)城市之間的距離是已知的，現(xiàn)在讓你求出一條經(jīng)過(guò)所有城市，并且最終回到出發(fā)點(diǎn)的距離最短的路線。

費(fèi)力不討好的“暴力窮舉”

這個(gè)問(wèn)題非常重要，小到餐廳送餐，郵遞員送貨；大到幾個(gè)城市之間工業(yè)運(yùn)輸路線的規(guī)劃，背后都是旅行銷(xiāo)售員問(wèn)題。數(shù)學(xué)家從理論上證明，要想找到最優(yōu)路線，只能暴力窮舉（brute force），即把所有的路線都列舉出來(lái)，然后分別計(jì)算長(zhǎng)度，最后找一條最短的路線。

用這種方法雖然可以保證找到最優(yōu)路線，但算法所需的時(shí)間會(huì)隨著節(jié)點(diǎn)（城市）數(shù)量的增加而急劇增加。

例如，7個(gè)城市共有720種排列方式，列出720條路線并找到

最短的路線看起來(lái)還不算太麻煩，但是這只是針對(duì)7個(gè)城市。10個(gè)城市的排列方式猛增至362880種。若有26個(gè)城市，排列方式就有1.5×1025種，這已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)科學(xué)家估測(cè)的宇宙中所有恒星的數(shù)量。

而在實(shí)際應(yīng)用中，旅行銷(xiāo)售員問(wèn)題所涉及的節(jié)點(diǎn)數(shù)量可能有成百上千個(gè)。

那么面對(duì)這樣的問(wèn)題，我們?cè)撊绾谓鉀Q呢？

一個(gè)接近最優(yōu)解的解，可能是正是你需要的

計(jì)算機(jī)科學(xué)家設(shè)計(jì)了很多啟發(fā)式算法（heuristic algorithm）。簡(jiǎn)單來(lái)說(shuō)，這個(gè)算法可以幫助我們得到一個(gè)接近最優(yōu)解的解，并且其計(jì)算出解的速度比正常計(jì)算最優(yōu)解的速度快得多。

針對(duì)旅行銷(xiāo)售員問(wèn)題，有一個(gè)簡(jiǎn)單的啟發(fā)式算法叫“最近鄰居法”：從任何一個(gè)城市開(kāi)始，每訪問(wèn)的下一個(gè)城市都是距離當(dāng)前城市最近、同時(shí)尚未被訪問(wèn)的城市。

計(jì)算機(jī)科學(xué)家在設(shè)計(jì)一個(gè)啟發(fā)式算法時(shí)，會(huì)試圖從數(shù)學(xué)上找到該算法的近似比（approximation ratio），即最優(yōu)解和用啟發(fā)式算法找到的解的比值。例如，有一個(gè)啟發(fā)式算法的近似比是2，這意味著該算法可以快速為旅行銷(xiāo)售員問(wèn)題找到一個(gè)解，并保證這個(gè)解對(duì)應(yīng)的距離在最差情況下不會(huì)超過(guò)最佳路線對(duì)應(yīng)的距離的2倍。有人可能會(huì)問(wèn)：“如果你無(wú)法有效地找到最優(yōu)解，如何保證用啟發(fā)式算法找到的解的大小不超過(guò)最優(yōu)解的2倍？”這確實(shí)令人驚訝，而且看起來(lái)很神奇，但是在數(shù)學(xué)上是可以做出這樣的保證的。

為旅行銷(xiāo)售員這個(gè)問(wèn)題找到啟發(fā)式算法，就是用弊（性能下降或距離變長(zhǎng)）來(lái)?yè)Q取利（速度快）。并且更重要的是，近似比表示了弊的大小，讓弊變得可控。如果你可以接受某個(gè)啟發(fā)式算法的弊，那么你就可以放心地用它解決實(shí)際生活中的問(wèn)題。

這就是用“可控的弊”換取“更大的利”。

怎樣用“可控的弊”換取“更大的利”

上文中的思想在實(shí)際生活中有很多應(yīng)用。

在美國(guó)，森林野火每年都造成很?chē)?yán)重的破壞。過(guò)去很多年，美國(guó)林務(wù)局應(yīng)對(duì)森林野火的治理政策是野火必救：一旦在野外發(fā)現(xiàn)小火苗，就立刻派人撲滅。但是這種方法似乎沒(méi)有降低發(fā)生大規(guī)模森林火災(zāi)的概率。

美國(guó)生態(tài)學(xué)家艾倫研究發(fā)現(xiàn)，干旱使很多樹(shù)木枯死，這時(shí)候一旦發(fā)生火災(zāi)，這些樹(shù)木會(huì)瞬間讓森林燃起熊熊烈火。因此他建議，火災(zāi)發(fā)生時(shí)，應(yīng)該在可控范圍內(nèi)讓枯死的樹(shù)木適時(shí)地被燒光，不要因累積過(guò)多枯木造成不可收拾的大火。

于是美國(guó)林務(wù)局在 2013 年修改了野火治理政策，不再實(shí)施“野火必救”，而是強(qiáng)調(diào)消防規(guī)劃和燃燒控制，主動(dòng)在可控范圍內(nèi)讓森林的野火把枯木和其他易燃物一起燒掉。這樣做降低了大規(guī)模森林火災(zāi)發(fā)生的概率。

這就是用可控的弊，換取更大的利的實(shí)際應(yīng)用之一。

此外，打疫苗也是如此。打疫苗的本質(zhì)是讓少量病毒感染你，從而讓你產(chǎn)生抗體。疫苗中的病毒對(duì)身體造成的傷害非常輕微，這個(gè)弊是可控的。而打完疫苗后，我們的機(jī)體產(chǎn)生了免疫力，這個(gè)好處遠(yuǎn)大于打疫苗帶來(lái)的不適。

類(lèi)似的例子還有，2013 年某影星宣布自己接受了乳腺切除手術(shù)以降低患癌風(fēng)險(xiǎn)。因?yàn)樗腥橄侔┘易迨罚⑶宜砩蠑y帶一種特 殊的突變基因，而攜帶該突變基因的婦女一生中患乳腺癌的概率為80%，術(shù)后患乳腺癌的概率則會(huì)降至5%。這種預(yù)防性的乳腺切除，就是主動(dòng)用可控的弊，換取更大的利。

兵書(shū)中有一個(gè)被稱(chēng)為“圍城必闕”的心理戰(zhàn)術(shù)，是指在攻城之時(shí)不將城池全部包圍起來(lái)，而是打開(kāi)一個(gè)缺口讓敵人逃跑。因?yàn)槿绻麛耻娚钕葜貒瑹o(wú)處可跑，覺(jué)得沒(méi)有活路，就必定會(huì)拼死抵抗，而放開(kāi)缺口可能會(huì)放跑少數(shù)敵人，但帶來(lái)的好處是瓦解敵人的士氣，殲滅大部分?jǐn)橙恕?/p>

這也屬于主動(dòng)用可控的弊，換取更大的利。

綜合來(lái)說(shuō)，“凡事有一利，必有一弊；凡事有一弊，必有一利”?！袄c弊”并不絕對(duì)，很多情況下其實(shí)沒(méi)有絕對(duì)的利弊，只有特點(diǎn)。某個(gè)特點(diǎn)是利還是弊，這個(gè)要根據(jù)情況判斷，因此最關(guān)鍵的，是找到把特點(diǎn)變成長(zhǎng)處的位置，讓長(zhǎng)處得以發(fā)揮。

主動(dòng)用可控的弊，換取更大的利，是解決問(wèn)題的有效策略之一。

文章由科普中國(guó)-星空計(jì)劃（創(chuàng)作培育）出品，轉(zhuǎn)載請(qǐng)注明來(lái)源。

作者：北京航空航天大學(xué)副教授、博士生導(dǎo)師 劉雪峰

審核：華中師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 副教授 鄧清泉

標(biāo)簽：