「弄明白蛋白質如何折疊成特定形狀；通過DNA來重新構建一系列物種的進化史；在命題邏輯中證明定理；利用交易成本來發現市場中的套利機會；從二維視圖中推出三維形狀；將數據壓縮到磁盤上；在政治活動中組成穩定聯盟；在剪切流中模擬湍流；按照給定回報率找出最安全的投資組合；到達幾個城市的捷徑、微芯片上元件的最佳布局方案、生態系統中傳感器的最佳布局、自旋玻璃門最低的能量狀態；安排好航班、課程、工廠工作；最優化資源分配、城市交通流、社會福利，以及提高你俄羅斯方塊分數(最重要的)——這些都是NP完全問題[註1]，意思是，如果你能有效解決其中的一個問題，就能有效解決所有NP類問題，包括相互間的問題。誰會猜到，這些表面上看來迥然不同的問題，會是同一個問題？如果它們真的是同一個問題，就可以說一種算法能學會解決所有問題(或更準確説，所有能有效解決的例子)。 在計算機科學中，P和NP是兩類最重要的問題(很遺憾，名字不是很有助於記憶)。如果我們能夠有效解決它，那麼這個問題就屬於P；如果我們能有效找到其解決方案，那麼這個問題屬於NP。著名的P=NP的問題就是，能夠有效找到的問題是否可以得到有效解決。因為NP完全問題回答這個問題需要只是證明某個NP完全問題可被有效解決(或者無法被有效解決)。NP在計算機科學領域並不是最難的一類問題，但可以說，它是最難的“現實”類問題：如果在宇宙滅亡之前，你無法找到問題的解決方法，那你努力解決這個問題的意義在哪裡？人類擅長給出NP難題的近似解，而相反，我們感興趣的問題(如俄羅斯方塊問題)往往涉及NP問題。人工智能的其中一個定義是，人工智能包括找到NP完全問題的所有啓發性解決方案。為了找到解決方案，我們常常把問題變成可滿足性問題，也就是NP完全問題：給定的邏輯公式是否永遠都是對的，或者它是不是自相矛盾？如果我們發明一種學習算法，能夠學習解決可滿足性問題，那麼有充分理由認為，這個算法就是終極算法。」* 作者說，一般計算機的應用，是拿數據做輸入，然後經過一套算法(Algorithm)之後，產生了我們要的結果作為輸出。 而機器的學習則是顛倒了過來：輸入數據和所想要的結果，輸出的則是其中的算法(Algorithm)。 由於輸入數據和所想要的結果之間，往往牽涉多種因素(多項式)，而且也不見得是線性的關係。因此求解的算法(Algorithm)，也就變成是要解決前述NP問題的困難。 不是很懂為何作者對於終極算法的存在那麼多有信心。意思是說全世界待解的問題的背後，有一個共通的算法可以通通予以解決，那個算法就叫做終極算法。 孔子說，吾道一以貫之。「忠恕」是孔子的終極算法，只有極簡的4個bytes。不知道未來計算機科學家的終極算法會是什麼。讓我們拭目以待。 2017/11/14 終極算法 Damakey ［註1］NP完全問題(Non-deterministic polynomial completeness，即多項式複雜程度的非確定性問題) *《終極算法》，［美］佩德羅•多明戈斯 著，黃芳萍 譯
留言列表
