科學(xué)研究：逼近近似算法的極限


圖片來源：Pixabay
計算機很擅長解決問題。比如像這些問題，例如從我家到美國51區(qū)怎么走最近？8675309是素數(shù)嗎？一湯匙有多少茶匙？計算機都能很好地幫你解答。
但是，計算機科學(xué)家們相信一些聽起來天馬行空的問題，計算機永遠(yuǎn)都無法給出答案，至少是在我們的人生結(jié)束以前。這就是P對NP問題，即答案可以被快速檢驗的問題是否可以被快速解答。
我最喜歡的難題是旅行商問題。這個問題給定一個城市集合，問經(jīng)過所有城市而后回到起點城市的最有效路徑是哪一條？為了得到在現(xiàn)實世界中有實際意義的答案，計算機科學(xué)家們使用近似算法，這些算法不能完全解決這些問題，但又足夠接近最優(yōu)解，從而能在一定程度上解決實際問題。到目前為止，最好的算法是在1976年被提出的，能夠保證其結(jié)果與最優(yōu)解的誤差最高為50%。
我也是一位研究近似算法的計算機科學(xué)家。我和合作者Anna Karlin、Shayan Oveis Gharan一起想出了一個辦法去解決剩下的50%的問題。我們證明有一種特殊的近似算法，它能給這一停滯已久的研究帶來一絲曙光，同時為更具實質(zhì)性的進展鋪平道路。
這一發(fā)現(xiàn)的重要性不僅僅局限于路線規(guī)劃問題。任何這類難題都可以被抽象為旅行商問題。反過來，解決其中一個問題就能夠解決所有問題。你可能會覺得這些難題就像是算算怎樣讓一群小精靈戴不同的帽子。
很難找到最佳路徑
旅行商問題經(jīng)常被表述為“找到最短路徑”。但是，最有效率的方案在現(xiàn)實世界中會受到許多因素的影響，比如時間、花費和距離。
為了直觀地感受該問題有多么困難，想象如下場景：有人給了你一張有100座城市的清單，以及兩兩城市之間航空、鐵路、公路的旅行費用表。你認(rèn)為你能找到游遍100座城市同時花費最少的路線嗎？
可以算一算一共有多少種可能路徑。如果你想要游遍這100座城市，那么可能的旅行順序就是100的階乘，即100×99×98……×1。這一數(shù)字比宇宙中所有原子的總數(shù)還大。


圖片來源：Pixabay
夠好就行
很遺憾的是，這一問題難以解決的事實無法阻礙它們出現(xiàn)在現(xiàn)實中。除了為旅行商（或者更現(xiàn)代一點，送貨卡車）尋找最佳路徑，旅行商問題還廣泛存在于許多領(lǐng)域，例如基因組圖繪制和電路板設(shè)計。
為了解決現(xiàn)實生活中的這類問題，實踐者們做了很多人經(jīng)常做的事情：找到未必是最佳但已經(jīng)是足夠好的解決方案。對旅行商來說，解決方案雖然比最佳路徑長了幾英里，但也可以接受。沒人會特別在意一塊電路板的加工尺寸長了一點或者Uber司機多花了幾分鐘才把乘客送到家。
計算機科學(xué)家們已經(jīng)能接受“足夠好”，并且大約50年來一直致力于研究所謂的近似算法。這些算法能被快速運行并得到結(jié)果，雖然不是最佳結(jié)果，但是可以證明它們接近最佳結(jié)果。
近似算法中的常勝將軍
最早并且最著名的近似算法之一是用于解決旅行商問題的Christofides-Serdyukov算法。20世紀(jì)70代，Nicos Christofides和Anatoliy Serdyukov分別獨立提出這一算法，但后者的工作最近才廣為人知。
Christofides-Serdyukov算法相當(dāng)簡單，至少算法運行起來很簡單。你可以把旅行商問題想象成是一個網(wǎng)絡(luò)，每座城市就是一個節(jié)點，兩兩城市之間的路徑就是一條邊。每條邊對應(yīng)一定的成本，比如城市之間的旅行時間。Christofides-Serdyukov算法首先選擇能夠連接所有城市同時花費最小的邊集。
可以證明這做起來不難：只需不斷添加新城市，且滿足花費最少即可，但這不是最終解。連接完所有城市后，有些城市可能會出現(xiàn)奇數(shù)條邊，這是錯誤的，因為每次通過一條邊進入一個城市，那么也一定會通過另一條對應(yīng)的邊離開它。因此，算法隨后會添加成本最低的邊集，使得每座城市都有偶數(shù)條邊，據(jù)此產(chǎn)生最終路徑。
這一算法運行速度快，并且產(chǎn)生的結(jié)果最多只會比最優(yōu)解差50%。如果Christofides-Serdyukov算法給出的路徑長150英里，那么最佳路徑不可能短于100英里。
當(dāng)然，如果無法真正知道最優(yōu)解，那么也無法得知近似算法在某個具體算例中，究竟有多接近最優(yōu)解；并且一旦知道了最優(yōu)解，那么也沒必要使用近似算法。但是，有辦法能證明算法的下限是多少。舉例來說，Christofides-Serdyukov算法能夠保證其產(chǎn)生的路徑最多是連接所有城市最短邊集總長度的1.5倍，那么其結(jié)果最多是最優(yōu)解的1.5倍。


圖片來源：Pixabay
確實微小卻也重要的進步
自Christofides-Serdyukov算法于1976年被提出以來，計算機科學(xué)家們根本無法對其進行改進。不過，去年夏天我和合作者們證明了存在一個特殊的算法，平均來說其產(chǎn)生的路徑只比最優(yōu)解差49.99999%。雖然我覺得寫出這么多個9很挺慚愧（實際上后面還有很多9），但是這的確跨越了長期以來存在的50%鴻溝。
我們分析的算法與Christofides-Serdyukov算法非常相似。唯一的不同是第一步選擇了連接所有城市的隨機邊集，平均來看像是巡回的旅行商問題。我們用這種隨機性表明我們并不總是被困在和先前算法一樣的地方。
雖然我們的進步很微弱，但我們希望其他的研究者能受此啟發(fā)，從其他角度看待這一問題并取得進一步的成果。在一個研究領(lǐng)域中，類似50%的閾值通常會存在很長時間，但一旦被推翻，閾值就會更快地降低。我們最大的期望之一就是理解我們從旅行商問題中所得到的結(jié)果，同時證明這一結(jié)果能夠帶來更大的進步。
趨近完美
我們樂觀地認(rèn)為在未來幾年內(nèi)將能看到更多進展的另一個理由是：我們所分析的算法于2010年提出，我們認(rèn)為該算法的性能比我們能夠證明的要好得多。與擁有50%硬極限能力的Christofides算法不同，我們懷疑該算法可能只會比最優(yōu)解差33%。
的確，比較近似算法結(jié)果和已知的最優(yōu)解的實驗結(jié)果表明，該算法在實踐中表現(xiàn)優(yōu)異，常常得到僅比最優(yōu)解差幾個百分比的結(jié)果。
目前的理論界限大約在1%，這意味著沒有算法能夠只比最優(yōu)解差1%。理論學(xué)家們希望回答這么一個問題：我們究竟能多接近最優(yōu)解？
翻譯：常灝杰
審校：曾小歡
引進來源：theconversation


關(guān)注【深圳科普】微信公眾號，在對話框：
回復(fù)【最新活動】，了解近期科普活動
回復(fù)【科普行】，了解最新深圳科普行活動
回復(fù)【研學(xué)營】，了解最新科普研學(xué)營
回復(fù)【科普課堂】，了解最新科普課堂
回復(fù)【科普書籍】，了解最新科普書籍
回復(fù)【團體定制】，了解最新團體定制活動
回復(fù)【科普基地】，了解深圳科普基地詳情
回復(fù)【觀鳥知識】，學(xué)習(xí)觀鳥相關(guān)科普知識
回復(fù)【博物學(xué)院】，了解更多博物學(xué)院活動詳情
?