身陷高維多面體
我們陷入了一些稀奇古怪的幾何體的包圍之中，它們似乎來自我們身處的時空之外的時空！不過別害怕，它們是來幫助我們的，有了它們，我們的世界才運轉的更好。
高維世界裡的多面體
我們周圍的世界裡有各種形狀的物體，為了描述物體的形狀，數學家很早就創造出了幾何學。在古希臘雅典的柏拉圖學院的大門上，曾經寫著這樣一句話：「不懂幾何學莫入」，以體現該學院的大門是向有學問的人敞開的。
在當時，幾何學是很高級的學問，在柏拉圖看來，宇宙是由幾何多面體構成的。他挑選出了5個三維幾何形狀，認為它們代表了宇宙的本質，其中四面體、立方體、八面體和二十面體分別代表了構成宇宙的基本「元素」——火、土、氣、水，另一個形狀十二面體則是宇宙自己的形狀。
從那時起到現在，幾何學變得越來越高深了。由於我們的身體包括大腦處於長、寬、高構成的三維空間中，所以我們比較容易理解三維幾何形狀。但如今數學家們在研究一些柏拉圖不能理解的稀奇古怪的幾何形狀——一些存在於更高維度空間的物體形狀，數學家可以用數學的語言，來描述高維度空間里的多面體。
我們沒辦法拿出筆和紙，畫出這些高維多面體，因為我們自己、筆和紙都處於三維空間中。但是數學家可以用一些數學語言來描述這些多面體的性質，這些數學語言就是所謂的「演算法」，不論是四維、五維還是成千上萬維，數學家都可以用演算法來描述其中的多面體，進而揭示高維世界的古怪性質。
要理解高維度的確很難，不過我們已經知道，如果我們把時間這個維度引入三維空間中，就得到了所謂的四維時空，我們的宇宙可能就是四維時空構成的。不過時間這個維度與空間的三個維度不一樣，空間的每個維度都有兩個方向，可時間這個維度在真實的世界裡卻只有向前的方向。這些性質都可以通過演算法來描述。
10維空間里的餡餅
其實，高維空間沒有可怕到我們一輩子都理解不了的程度，真實世界裡就有可以類比的事例。比如說，你想要製作一張餡餅，需要10種不同的配料，有麵粉、肉餡、蔬菜以及各種調料。實際上，這10種配料就可以看成是餡餅的10個維度，你要確定每種配料的用量。當你把所有配料的用量都確定好後，你實際上就得到了10維空間中的一個點，這個點代表了你的餡餅配方。
另外，你製作餡餅的配方會受到配料的一些限制。比如，你的冰箱里只有2兩肉餡，所以你的餡餅中肉餡維度上的值只能是0到2兩；或者你還缺少了胡椒這種調味料，於是胡椒的值就只是0……配料的各種限制實際上可以看成是10維空間中的各個面，對你的配方的值形成了限制。所有的面集合在一起，形成了一個10維空間中的多面體，我們可以把它稱為「10維餡餅多面體」，這個多面體中的所有點，代表了你所有可能採用的餡餅配方。
所以你看，10維空間並不是那麼神秘莫測，那麼不可理喻，你在製作餡餅的時候，就在和10維餡餅多面體打交道。
先別為自己能處理10維問題而得意，實際生活中，我們要面對的麻煩比做一張餡餅大多了。比如一個水果商人建立了5個水果批發配送中心，要滿足200個商店的進貨需求。這位水果商人要處理的配送問題，實際上就是一個1000維的問題！
所以，我們每時每刻被大量的高維多面體包圍著，我們的一舉一動都正在與高維多面體發生著聯繫。
對於製作一張餡餅，我們可以根據自己的口味來調整那10個變數，讓製作出來的餡餅達到令自己最滿意的味道。在這個過程中，我們就在無意之中尋找到10維餡餅多面體上最優的那個點。但對於那個水果商人來說，要找到一個最佳的配送方案，使得自己的水果運輸成本最低，可不是一件容易的事情。類似的尋找最佳的點的事例還有很多，比如一位基金經理要從幾千個股票中根據風險、預期回報等條件，尋找一個最佳的投資組合；列車時刻表的製作人員要對幾百輛列車和幾千個站點進行合理調配；工廠的廠長要考慮如何分配有限的原材料，製作出更多的產品和更好的產品；醫院的院長要考慮如何分配不同科室的病房空間最合理……
所有這些事例的共同之處是，人們需要在高維度空間中尋找最符合要求的那個點，即最優點。
劍指多面體上的最優點
要在這些高維多面體上找到最優點，我們就需要演算法的幫忙了。
20世紀40年代，正值第二次世界大戰期間，美國數學家喬治·丹特齊格受邀，研究讓美國空軍的後勤保障更有效率，這就是一個類似水果商人配送水果的問題。這位數學家採用了幾何學的方法來研究，換句話說，他利用高維多面體的數學演算法來尋找最優點。根據他的研究，他得出了一個定律，「目標函數」的最優值位於多面體的一個角上。
目標函數就是包含了各種變數的函數，人們可以通過函數求解最優點。有了丹特齊格的這個定律，問題就變得簡單一些了，我們不用像沒頭蒼蠅一樣在高維多面體的內部亂竄，尋找那個最優點了，只需要考察多面體上的那些角，比較那些角的值，就能夠找到最優點了。多面體內部的點有無窮多，但不論維度多高，一個高維多面體的角總是有限的。
這就是丹特齊格的「單純形演算法」，利用這種演算法，人們可以沿著多面體的邊尋找每個角，然後比較這些角的值，直到最終找到最優點。
單純形演算法在1952年首次被用到商業領域，當時美國的一個石油公司要找到一種最佳方案，把四種不同的石油產品摻入一種航空燃油中，以達到最佳的辛烷值（汽油等燃料抵抗爆震的指標，辛烷值越高，抗震爆越好），最有利於充分燃燒。自那以後，單純形演算法逐漸征服了世界，無論是商業上的優化包裹還是定製軟體產品，都涉及到這種演算法。當人們試圖解決大規模的優化問題時，往往要用到計算機。而在計算機中，也許每分鐘有成千上萬次要使用該演算法。
沿著邊，尋找角
聽上去問題變得簡單多了，但高維空間又向我們展示了它可怕的一面。即使是一個有50個限制條件的10維空間問題，形成的多面體上的角，可能有幾十億個！這個問題就好比要把50個學習時間各不相同的人分配到10個不同的課堂，尋找一個最佳的學習安排表。
於是，自從單純形演算法問世以來，數學家們殫精竭慮地對演算法進行優化，盡量地減少在多面體上搜索最優點的步驟。
1957年，美國數學家沃倫·赫希提出一個關於多面體的法則：連接多面體上任意兩個角之間的邊的最大數目，不大於多面體的面的數目減去維的數目。也就是說，你從多面體一個角出發，沿著邊走到另一個角，經過的邊的最大數目，不會超過這個多面體的面的數目減去這個多面體所處的空間的維度數。例如在三維空間中，一個六面體的一對角最多通過三條邊連接起來，沒有一對角是通過四條邊或更多條邊連接起來的。
這個法則對於在高維多面體上尋找最優點是個基礎性的法則，當數學家沿著多面體的邊挨個搜索各個角，找到最優點時，這個法則可以起到簡化步驟的作用。但是這個法則是否真的正確無誤呢？
數學家早就證明，赫希的這個法則對於所有三維空間中的多面體都是成立的。但是在更高的維度空間中，法則還沒有得到數學證明。不過人們相信它在高維空間也是成立的，因為另外的一些幾何法則曾經被證明在高維空間中成立，也許赫希的這個也沒問題。
於是，赫希的法則與單純形演算法一道，被廣泛用於生活之中。演算法描述的多面體掌控了我們真實世界的運轉，那些稀奇古怪的多面體決定了我們每天的日常生活：我們吃什麼樣的食物，我們工作的最優日程表，以及火車幾點鐘到站……
我們真實的世界就建立在這些多面體的「地基」之上，它們可別出現「施工質量問題」啊！
多面體世界不太「結實」
2001年，一個「壞消息」傳來了，一位西班牙青年數學家研究了43維空間中的86面體。根據赫希的法則，這個多面體上連接兩個角之間的邊數最多只有86減43，也就是43條邊。但是這位數學家證明，這種多面體上至少包含了一對角，兩個角之間聯繫的邊數達到了44條。
也就是說，赫希的法則在高維空間中並不總是成立的，連帶著單純形演算法也遭了秧，也許我們的世界裡每天無數次使用的這種演算法，並不總是準確的，這種演算法幫我們找到的最優點，也許有些並不是最優點。
聽上去真是糟糕，我們的世界的運轉可能建立在錯誤的演算法之上，多面體「地基」其實並不穩固。
情況可能並不如想像的那麼糟糕，畢竟我們的世界還在正常運轉著，依賴大量高維多面體演算法計算的工作，好像也並沒有出現重大問題。也許在高維空間中絕大多數情況下，演算法還是正確的，只是在一些極特殊的情況，演算法不成立，但這些極特殊的情況非常罕見，我們在生活中應用演算法是幾乎碰不到。因此我們在生活中尋找最優點的無數計算還是正確的。
高維多面體「地基」雖然有點小紕漏，我們的世界並未因此坍塌。數學家正在不斷尋找更好的演算法，讓各種食物更加美味，火車更加準點，世界更加穩固而有效率。
超級鏈接：演算法2000年掠影
演算法在很久以前就已經出現了……
公元前300年 歐幾里得演算法
古希臘數學家歐幾里得是演算法的鼻祖，在《幾何原本》中他提出，兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。
公元820年 二次演算法
一位波斯數學家兼醫生探索了如何解決二次方程問題的演算法。
公元1936年，通用圖靈機
英國數學家阿蘭·圖靈把演算法和機器編程聯繫起來，這成為編程計算機的理論模板。
公元1946年，蒙特卡洛演算法
當問題過於複雜，難以解決時，可以考慮引入概率。這個演算法告訴我們如何在賭場中用概率統計的知識獲勝。
公元1957年，FORTRAN編譯器
當時，編程是一個繁瑣而且艱苦的工作，直到美國IBM公司的研究人員發明了第一種高級編程語言——FORTRAN。利用該演算法，程序員可以把指令轉換成機器語言。
公元1962年，快速排序
從一本字典中找到一個字的準確位置，這很輕鬆；把所有的字都按照順序擺放，則很困難。英國數學家發明了一種重要的演算法工具，能夠管理各種資料庫。
公元1965年，快速傅立葉變換
許多數字技術取決於把不規則的信號變成純粹的正弦波組件，能夠完成此事的演算法是世界上應用最廣泛的演算法之一。
公元1994年，肖爾演算法
美國貝爾實驗室的彼得·肖爾發現一個新的快速演算法，能夠把一個整數分解為組成它的素數，但它只能由量子計算機來演算。這種演算法如果真能運轉，就將破解目前所有的互聯網密碼，因為使用素數來編製密碼是互聯網中最常見的加密方法。
公元1998年，網頁排名演算法
互聯網是一個龐大的信息庫，但如果不能有效地在裡面搜索信息，那它就是毫無價值的垃圾堆。美國斯坦福大學的謝爾蓋·布林和拉里·佩奇發明了一種演算法，能夠對每個網頁給出排名，在此基礎上，世界上最著名的搜索網站——谷歌（GOOGLE）誕生了。
本文源自大科技〈科學之謎〉 雜誌文章 歡迎您關注大科技公眾號：hdkj1997
TAG:大科技雜誌社 |