第535章 44年，關於一個PP問題的10???的關鍵突破i
你是一位辛苦而忙碌的推銷員，需要穿梭在許多城市之間。假設現在你有一係列目的地城市需要逐一拜訪，並最終返回你生活的那座起點城市。你已經做了充足的準備，知道任意兩座城市之間的距離，那麽，應當如何規劃旅行路徑，才能使得整個旅程最短呢？
雖然描述和理解起來並不複雜，但這絕不能算是一個簡單的問題，尤其是當“城市”的數量遠不止三五座，而是一個龐大的數字時，問題的複雜程度也可能變得超乎想象。
這個問題有個專屬的名字，它通常被稱為旅行推銷員問題（travelling salesman problem， TSP），是理論計算機科學中一個最著名的存在已久的基本問題之一。理論計算機科學家為了檢驗有效計算的極限，對這一問題進行了反複研究。幾十年來，它也激發了計算機科學中許多基礎的進步，幫助闡釋了線性規劃等技術的能力。一些科學家甚至把探索TSP稱為一種“癮”。
TSP也並非單純的“紙上談兵”，而是具有廣泛的實際意義，在物流、製造業，甚至DNA測序中都有應用。在這些情況下，“城市”就代表著客戶、DNA片段等，而“城市間的距離”則可以指時間、距離、相似度等。
兩年前，當Nathan Klein開始研究生學習時，他的導師Anna Karlin與Shayan Oveis Gharan提出了這樣一個規劃——共同研究理論計算機科學中這個著名問題。Klein的導師都認為，即使他們無法解決這個問題，Klein也能在這個過程中學到很多東西。當時仍是研究生新生的Klein同意了這個計劃，他還不知道自己在接下來兩年將會麵臨什麽。
如今，在上傳至預印本網站的一篇論文中，導師與Klein終於實現了他們的目標，事實上，這也是計算機科學家近半個世紀以來一直所追求的——他們證明了找出TSP近似解的更優算法。
大多數計算機科學家相信，沒有一種算法可以有效地為TSP所有可能的城市組合找到最優解。雖然如此，找到接近最優解的方法還是有可能的。
1976年，尼科斯·克裏斯托菲德斯（Nicos Christofides）提出了一種算法，可以有效地找到TSP的近似解，並保證這種近似解中的往返旅程最多比最優解長出50%（近似比不超過3/2）。這種算法利用了連接所有城市的最短“樹”，也就是沒有閉合回路的連接（或者叫“邊”）網絡，然後將這種樹作為主幹，隨後添加額外的連接，將它轉換成完整的往返路徑。
這是一個簡單的TSP例子，在這個例子中，最優解並不複雜。而克裏斯托菲德斯算法會先找到連接所有城市的最短樹，然後再將它轉換成完整的往返旅程。
在任何往返旅程中，連接每座城市的邊都必須是偶數條，這不難理解，因為每次到達後都會離開。事實證明反之亦然，也就是說，如果網絡中的每座城市都有偶數條連接，那麽網絡中的連接一定能構成一個往返旅程。
連接所有城市的最短樹則缺乏這種“偶數性”，因為位於分支末端的城市隻存在一條連接。克裏斯托菲德斯算法找到了最佳的方式，將擁有奇數條連接的城市相連，就讓最短樹變成了一個往返旅程。隨後他證明，由此產生的往返旅程最多比最優解長50%。
克裏斯托菲德斯算法是理論計算機科學中最著名的近似算法之一，它也成了不少教科書和課程中經常出現的最佳案例。但計算機科學家一直相信，應當存在比克裏斯托菲德斯算法更優的近似算法。畢竟，克裏斯托菲德斯算法雖然簡單直觀，但並非總是那麽高效，因為連接城市的最短樹或許並非可選擇的最佳主幹。比如，如果這個樹有許多分支，那麽分支末端的每座城市都需要與另一座城市相匹配，這可能會帶來大量昂貴的新連接。
當時許多人認為，不久就會有人對克裏斯托菲德斯的簡單算法提出改進。但事情並沒有這麽簡單。
直到10年前，Gharan和他的博士導師以及合作者開始研究提高克裏斯托菲德斯算法的可能。他們受到了另一種版本的TSP的啟發。在這個版本中，你可以選擇一種組合路徑。例如，如果你想去A地，可以選擇3/4的B到A的路徑，加上1/4的C到A的路徑。這種“分段版本”的問題雖然沒有實際的物理意義，卻能夠有效地求解。對計算機科學家來說，它也可以作為對求解一般性TSP的一種思路引導。
因此，Gharan等人沒有選擇連接所有城市的最短樹，而是從一個精心篩選的集合中隨機選擇一個樹。他們創建了新的算法，利用一種隨機過程創建出樹，在這樣的樹中，擁有奇數條連接的城市傾向於有鄰近的“搭檔”。接著再用類似克裏斯托菲德斯算法的方式，將這些城市與其“搭檔”相連，就能創造出一個完整的往返旅程。
Gharan等人提出的新算法的近似解，先利用隨機過程創建樹，然後再將它轉換成完整的往返旅程。
這種方法似乎很有前景，他們相信這是一種更好的算法，但嚴謹地證明出這種優越性並非易事。
2011年，Gharan等人成功證明，他們的新算法在“圖形化”TSP上比克裏斯托菲德斯算法更優。“圖形化”TSP可以理解成TSP的一類特例，也就是城市之間的距離由一個網絡（不一定包括所有連接）表示，每邊長度相同。但他們一直沒能將結果推廣到一般性TSP中。
幾年來，Gharan仍然在一直思考這個問題。他認為，數學中的多項式幾何（geometry of polynomials）領域可能是解決問題的關鍵工具，但理論計算機界對這一數學領域知之甚少。Gharan在與Karlin共同指導研究生Klein時，他們決定共同推進對這個問題的研究。
在第一年裏，他們先從一種簡化版本入手。盡管困難重重，但他們開始對所用的工具有了感覺，尤其是多項式幾何。
多項式是由常數和變量的冪運算等組合而成的表達式，比如x2y+2yz?。在TSP中，研究人員將一張城市地圖提煉成一個多項式，其中每座城市之間的連接是一個變量，可以連接所有城市的每個樹是一項。數值因數隨後為這些項加權，反映出旅行售貨員問題的分段解中每條邊的值。
他們發現，這個多項式有一種迷人的性質，也就是“實穩定性”（real stability），也就是說，讓多項式為零的複數永遠不在複平麵的上半部分。實穩定性帶來的優勢是，即使對多項式做出許多改變，它仍然有效。例如，當研究人員操控一些更簡化的多項式時，他們操控的結果仍然具有實穩定性，這就為各種各樣的技巧打開了大門。
這使得研究人員能夠更好地處理一些問題。終於，在一份80多頁的論文中，Karlin、Klein和Gharan證明出，10年前設計出的算法確實比克裏斯托菲德斯算法要更好。新算法在克裏斯托菲德斯算法（3/2近似比）的基礎上，將近似比提高到了3/2 - 10?3?。
雖然這一微小的數字看似不足為道，但許多理論計算機學家相信，它突破了理論和心理上的僵局。研究人員希望，這能為進一步的提高開辟道路。