程序員該怎麼送外賣？祖師爺300年前已經想好了答案

我的一位35歲的前程學員朋友 站在天橋上 要以最快的速度送完手裏的外賣 此刻他回想起大學離散數學課上 老師曾經說過一個故事 1735年 一位28歲的數學家 也在考慮一種送外賣的問題 在這個問題中 外圍人需要走過七座橋 他希望每座橋只走一遍 就能夠送完外賣 原來祖師爺300年前 就已經給自己鋪好了路 想到這裏 我的朋友不禁留下了感動的淚水 祖師爺開創了這門 可以用來送外賣的學問 叫做圖論 這門學問堪稱萬金油 如今開發搜索引擎 研究蛋白質摺疊 甚至量子場論都離不開它 大家好 歡迎來到量子味 今天我們就來和大家聊一聊 數學這個萬能而強大的分支圖論 有些朋友聽到開頭的故事 可能已經猜到了 那位祖師爺 這是數學家歐拉 他思考的便是大名鼎鼎的 科尼斯堡七橋問題 歐拉是如何解決它的呢 我們來看這張科尼斯堡的地圖 這座城市被普列格利亞河 分裂成四塊陸地 這樣科尼斯堡問題就變成了 從ABCD當中的某個點出發 每條邊只經過一次 最終走完這張地圖 歐拉抽象出來的這張 科尼斯堡簡化地圖 就是後來數學家們所說的圖 在數學裏 圖專門指點和連接點的邊 組成的圖形 從七橋問題出發 歐拉開創了一門新的數學 專門研究圖的各種性質的圖論 接下來我們引出圖論的一些基本概念 點上的邊的數量 叫做這個點的度 七橋問題中 每個點的度數分別是 3 3 5 3 連通某兩點之間的所有的邊 叫做路徑 如果一個路徑的起點和終點重合 那麼這個路徑叫做迴路 路徑和迴路有一種特殊的情況 如果我們正好能夠遍歷 圖中的每一條邊恰好一次 這種路徑或者回路 就叫做歐拉路徑或歐拉回路 所以科尼斯堡問題 實際上是找一條歐拉路徑 或者歐拉回路 假設起點和終點一樣 即存在一條歐拉回路 那麼每經過一個頂點 都會有一條進入的邊 和一條離開的邊 所有點的度數 那隻能是偶數 如果起點和終點不一樣 即存在一條歐拉路徑 起點多出一條只出不進的邊 而終點呢 多出一條只進不出的邊 這兩個點的度數可以是基數 而其他點的度數也必須是偶數 只有滿足以上兩個條件 才能夠找到一條歐拉路徑 或者歐拉回路 顯然科尼斯堡問題 不滿足以上兩個條件之一 所以不存在歐拉路徑 或歐拉回路 這條定理 便是圖論中的第一個定理 歐拉定理 科尼斯堡七條問題 算是圖論裏最簡單的問題了 我們只需要考慮走遍每一條邊 而我那個送外賣的朋友 要考慮的更多 他不僅要把外賣送出去 還要儘可能的快 在他的問題裏 走過每條路所需的時間 都不一樣長 因此他得仔細斟酌 尋找一條最短的路徑 我們可以在地圖上標註出 通過每條路所需的時間 這個時間在圖論裏 叫做邊的權重 加上權重的圖 便是加權圖 現在我們每畫出一條可能的路徑 把所有的權重加起來 就得到了一條路徑的權重 我的朋友 就是需要找到權重最小的路徑 這時候他又想起了 老師曾經教過的 代克斯特拉算法 是尋找圖中兩點最短路徑的一種算法 他是荷蘭物理學家 數學家 散文家 計算機專家 圖靈獎得主 代克斯特拉 1956年在一家咖啡館 和妻子喝咖啡時候想出來的 當時他沒有紙筆 更沒有鍵盤 完全是在腦海中設計出了這套算法 作爲一種經典的算法 每個計算機專業的學生 應該都在算法課上學過 最近 代克斯特拉算法 已經被證明了 是求解圖中兩點距離的最優算法 代克斯特拉算法的計算過程是這樣的 假如從7點A復發 有兩條路可選 到達B點需要5分鐘 到達C點需要2分鐘 我們首先在右邊的表格中 把它們記錄下來 接下來從B點出發到達D點 需要2分鐘 而從C點出發到達D點 需要7分鐘 經過計算不難發現 A到B到D需要7分鐘 而A到C到D需要9分鐘 我們選取最快的這條路 計下A到D最快7分鐘 淘汰比較慢的那條路 代克斯特拉算法的核心思想 就是嘗試每一條可能的路徑 不斷迭代比較 最終找出最短路徑 然而現實中的情況 可能比這還要複雜 比如剛剛有三個不同的客戶 都點了牛肉拉麪 我的朋友到店取出這三份外賣 分別要送往三個不同的小區 怎麼才能夠在最短的時間 送完三份外賣呢 這又是一個圖論裏經典的問題 旅行推銷員問題 便利途中的每一個點 並且走過的所有邊的權重 加起來最小 很不幸的是這個問題的複雜度 隨着點數N成階層級別的增長 好消息是外賣的送達點 並不是很多 我的朋友依然可以用窮舉法 找到最優路徑 如果點數太多呢 我的朋友想到了 用貪心算法 也可以找到一條近似最優路線 顧名思義 貪心算法是每一步都很貪心的 選擇當下的最優解 及選擇當前的最短路線 然後每一步往下推算 直到到達最終點 雖然不一定能夠找到最優解 但是對於送外賣這個問題 完全夠用了 從圖論的出現 到後來的幾個經典問題 圖論似乎總在送外賣 但實際上圖論的用途 遠遠超過你的想象 甚至可以毫不誇張的說 沒有圖論 就沒有我們現在的互聯網 因爲谷歌搜索引擎的發明 正是依賴於圖論 1996年 谷歌的兩位創始人 拉里佩奇和謝爾蓋布林 在斯坦福大學就讀時 發明了PageRank網絡排名算法 佩奇和布林想的 把一個一個網頁看作是圖中的點 而從某個網頁 跳轉到另一個網頁的超鏈接 看作是邊 假如現在有4個網頁ABCD 我們定義它們的初始排名參數 都等於0.25 如果BCD三個網頁都指向A 那麼A將吸收BCD的排名系數 實際上網頁BCD指向外部的鏈接 可能不只有一個 也就是說這些點的度不等於1 那麼A吸收的排名 還要除以BCD的度 另外網上衝浪的人 也不可能對網頁的超鏈接 無限點擊下去 它們最終會停留在某個網頁上 因此A的排名系數 還要稍微改動一下 同樣的 我們可以用類似的方法 更新BCD的排名系數 最終通過比較它們的排名系數 來決定搜索結果的先後 除了計算機專業本身以外 你可能想不到 現在特別火的蛋白質摺疊問題 也能用上圖論 蛋白質摺疊 是指蛋白質分子長鏈 從無規則捲曲 摺疊成特定功能性 三維結構的物理過程 實際上這個過程 是不同氨基酸分子之間 靠着氫鍵 離子靜電等 科學家們發現 最終蛋白質的構型 也可以用圖論來研究 我可以把氨基酸 看成圖的節點 不同劑團之間的非公價件 看作是邊 由此我們可以畫出 蛋白質結構對應的圖 在這裏邊也有權重 一般是兩個劑團之間的物理距離 或者是其他物理參數 科學家們還定義了 蛋白質分子的 基爾霍夫指數 它表示 劑團A到劑團B之間的 權重最小值 這和我朋友送外賣的問題 簡直是一模一樣 通過研究蛋白質的圖 生物學家們可以 更深的理解蛋白質問題 甚至還可以利用圖論 推測其他蛋白質 可能的摺疊結構 在量子場論中 物理學家們常用飛滿圖 來研究粒子間的相互作用 其實飛滿圖也是一種圖 它的邊代表粒子 點代表粒子之間的相互作用 飛滿圖的出現 讓物理學家們 不用再硬套複雜的數學公式 而直接用圖來直觀計算 粒子碰撞的反應概率 大大簡化了計算過程 以上只是圖論應用的冰山一角 圖論抽象而又簡潔的方法 讓它變成了一種強大的工具 圖論早已不是 簡單的數學問題 它已經廣泛滲透到 計算機科學 生物學 物理學 化學 乃至社會科學等重要領域 好的 今天的節目就到這裏結束了 如果你覺得我們的節目 讓你有所收穫的話 歡迎給我們點贊評論轉發 再見