用數學告訴你成功的最短路徑在哪兒，楊武建的科學成功學第一期
其實打小我就喜歡數學，不論其他學科怎麼樣，數學一直保持著名列前茅。只是後來發現社會上不按數學出牌的太多，不講理性的人太多，甚至是不講理性的男人也不少（女權主義者請拍磚）。慢慢地讓自己學一些商業的東西，開始世故一些，學會社交學會客套。但骨子裡自己真不是一個情商太高（當然智商也不高）的人。
好像有點走題了，我想說成功來著。
成功有捷徑嗎？有？沒有？相信有捷徑的人往下看，不相信有捷徑的按左上角的箭頭退出（免得說我在安利，在洗腦。。。）
其實捷徑是有，但成功是什麼大家可能概念不一致。那我們就先研究研究捷徑。所謂捷徑其實我們計算機專業的同學們都學過：最短路徑。就是從起點到終點最短的路。
下面直接上數學知識了，系好安全帶，老司機（公眾號：超級數學建模）帶你燒腦超車。
保持對同一個問題的思考
在那一個瞬間找到了答案
1
人們總是在做一件事情：
找最短路徑
公元前32世紀，蘇美爾人在粘土片上製作了城市地圖，圖上描繪了神廟、公園、城牆、河流。這幅地圖是世界上現存最古老的地圖。隨著人類的發展，地圖的形式越來越豐富，但其核心都是一致的，也就是幫助人們找到去某個地方的最短路徑。
蘇美爾人製作的地圖是世界上現存最古老的地圖
18世紀初，在普魯士的格尼斯堡，普瑞格爾河從市中心流過，河中心有兩座小島，島和兩岸之間建築有七座古橋。
哥尼斯堡的七座橋
當地居民有一項消遣活動，就是試圖每座橋恰好走過一遍並回到原出發點。這個問題俗稱七橋問題。有很多外地遊客慕名而來，躍躍欲試，但從來沒人成功過。
於是有人寫信給當時著名數學家歐拉，希望他能解決這個問題。歐拉通過簡化七橋問題為一個簡單圖形，證明了這種走法是不存在的。證明過程非常簡單，但不經意間他開創了一個新的學科：圖論。
時光輪轉，20世紀30年代，旅行商問題（Travelling salesman problem， 簡稱TSP）正式載入史冊：
「有一個旅行商人要拜訪n個城市，每個城市只能拜訪一次，而且最後要回到原來出發的城市。這位商人如何設計拜訪順序，使走過的路徑最短？ 」
雖然已經誕生了非常多的啟發式演算法和精確解法，但一直沒有出現能夠解決旅行商問題的有效演算法。旅行商問題的難度非常大，但是科學家們對它熱情不減，希望能找到更加高效的演算法。從誕生至今，它一直是優化領域最經常研究的問題之一。
TSP問題歷史悠久，最早的描述來自18世紀的騎士環遊問題（Knights Moves）
在歷史長河中，人們從各個角度致力於尋找最短路徑，然而只能做到將路徑的表示形式越來越簡單，卻沒有一個機械化演算法可以幫助人們快速尋找最短路徑。
直到1956年，Dijkstra演算法，一個為求最短路徑而生的演算法，它的誕生改變了這個局面。
2
在咖啡館誕生的
Dijkstra演算法
Dijkstra演算法的發明者，叫Edsger Wybe Dijkstra。
故事要從1952年開始說起。當時Dijkstra剛完成學士學位，參加了劍橋大學開設的一個課程。在他的課程導師，也是著名的英國計算機科學家威爾克斯（Maurice Vincent Wilkes）推薦下，Dijkstra來到了荷蘭國家數學研究中心（Mathmetical Centre）。在荷蘭數學家阿德里安·范韋恩哈登（Aad van Wijngaarden）領導下開始了編程生涯，參與了新計算機的程序研發，包括ARRA I、ARRA II和ARMAC，開始研發荷蘭最早期的第一批計算機。
由於這些計算機還在設計當中，Dijkstra的工作實際上是為這些並不存在的機器寫程序，而且只能用紙和筆把程序寫出來，驗證它們的正確性，和負責硬體的同事確認需要的指令是可以被實現的，並寫出計算機的規範說明。因此後來他很習慣於不測試自己寫的程序，因為無法測試。
時間來到了1956年，Dijkstra從事編程工作到了第4個年頭，此時新計算機ARMAC已經研製完成，為了方便向媒體和公眾展示ARMAC的計算能力，Dijkstra需要想出一個可以讓不懂數學的媒體和公眾理解的問題，來驗證這台計算機的實力。Dijkstra思考許久，始終沒有一個合適的答案。
就在一個陽光明媚的下午，Dijkstra和未婚妻在一家咖啡館的陽台上喝咖啡，他習慣性地思考這個問題。
而此時Dijkstra的未婚妻並沒有察覺獃獃的Dijkstra，一個勁地跟Dijkstra聊起，準備出門去另一座城市拜訪貴族的事情。
Dijkstra突然間靈光一閃，如果讓計算機演示如何計算荷蘭兩個城市間的最短路徑，這樣問題和答案都容易被人理解。
Dijkstra也不管未婚妻的詢問，在沐浴在暖和的陽光下，埋頭想著自己的問題，終於在20分鐘內想出了一個簡潔且高效計算最短路徑的方法，也就是我們所熟知的Dijkstra演算法。
Edsger Wybe Dijkstra
3
Dijkstra演算法
是一個既貪心又最優的演算法
大名鼎鼎的Dijkstra演算法是怎麼工作的？
設兩個集合，S和U。初始狀態下，S只包含源點v，即：S＝，U包含除v外的其他頂點，即：U=。
設dis[u]表示源點v到u的最短距離，若v與U中頂點u有邊，則dis[u] = d(v,u)（d(v,u)表示v到u這條邊的長度），否則dis[u] = ∞。
第一步，從U中選取一個距離源點v最小的頂點k，即dis[k]最小，把k加入S中，同時在U中剔除k。
第二步，以k為中間點，修改源點v與U中各頂點的距離。若從源點v經過頂點k到頂點u的距離，比原來的dis[u]小（dis[k] + d(k,u) < dis[u]），則更新dis[u]。
第三步，重複第一步和第二步，直至S包含所有頂點，演算法結束。
事實上，Dijkstra演算法思想非常簡潔：
Dijkstra演算法對圖中的頂點分成兩類，一類是已經求出最短路徑的頂點集合，用S表示，初始時在S中的只有源點。另一類是其餘為未確定最短路徑的頂點集合，用U表示。
Dijkstra演算法不斷在U中挑出與源點距離最短的頂點，加入S中，同時每挑出一個頂點，則利用這個頂點的信息更新U中所有頂點與源點的距離數值。
這種演算法有種貪心演算法的意味：總是做出在當前看來最好的選擇，看似不從整體的角度上考慮，不可能得到最優解。
實際上，Dijkstra演算法能夠得到最優解，其正確性已被確認，兼具快速和最優的特性。
以Dijkstra演算法尋找頂點a與頂點b之間的最短路徑
信號傳輸經過多個節點，必須使用演算法計算最短的傳輸路徑
關於成功的捷徑欲知後事如何，請聽下周分解。。。（下周解不了咱們一起解）
TAG:楊武建 |