這道哥尼斯堡七橋問題是18世紀著名古典數學問題之一，這七橋如果是在今天絕對是網紅，當時每天散步過橋已經成為當地市民非常熱門且有趣的一項消遣活動。但在相當長的時間裡，沒有人能解出來。

29歲的尤拉發表了《哥尼斯堡七橋》的論文，圓滿解決了這一問題，同時開創了數學新一分支---圖論。

尤拉巧妙的將過橋難題轉化等同為上面圖中的一筆畫問題，很快他就判斷出要一次不重複走遍哥尼斯堡的7座橋是不可能的。也就是說，多少年來，讓無數人燒腦、試圖發現的不重複的路線，根本就不存在。

一個號稱最燒腦且困擾無數人的難題，居然就是這樣的最簡單答案。

在論文中，尤拉將七橋問題抽象出來，得到歐拉回路關係：

要使得一個圖形可以一筆畫，必須滿足如下兩個條件：1. 圖形必須是連通的。2. 圖中的“奇點”個數是0或2。（連到一點的數目如是奇數條，就稱為奇點）

大道至簡，尤拉硬是天才地把一道著名古典數學難題簡化成一道小學生習題，並寫進了小學課本，叫做“七橋問題”。

七橋問題是圖論的第一個問題，但是圖論最著名、出成果最多的問題是四色問題：“是否只用四種顏色就能為所有地圖染色，使得任意兩個相鄰的區域不同色？”四色問題出人意料地異常困難。到目前為止，100多年過去了，還只能靠計算機驗證證明。

四色定理是第一個主要由計算機驗證成立的著名數學定理。

從小學生習題入門，到非常困難的四色問題，圖論發展迅速，應用廣泛，甚至成為計算機科學中最重要、最有趣的領域之一。

尤拉被普遍認為是圖論的創始人。

特別難得的是，在解決七橋問題的前一年，1735年，尤拉得過一次幾乎致命的發燒，隨後三年，他的右眼近乎失明，弗雷德裡克把他譽為“獨眼巨人”。

變身“獨眼巨人”後的尤拉依然是最勤奮的天才。

為什麼最佳化如此重要？

從幾百萬年前人類生命起源開始，為了提升生活質量，提高在地球上的生存技能，人類利用睿智的腦袋進行了一次次的科技創新和發明。從火（藥）到車輪，從電力到量子力學，我們對於世界及周遭事物複雜性的理解水平已經到了難以僅憑直覺去判斷的程度。

如今，飛機、汽車、輪船、衛星以及用於其他目的複合結構的設計師們，極大地依賴於運用演算法來提升其能力，而這種提升方式往往微妙到人們自身永遠無法實現。

除了設計，最佳化在日常生活中也扮演著至關重要的角色，比如網路路由（網際網路和移動終端）、物流、廣告投放、社交網路甚至是醫藥資訊。未來，隨著科技水平的不斷改進與複雜化，解決大規模難題的能力將會迎來更高需求，同時，我們也需要在演算法最佳化上有所突破。

廣義上來說，組合最佳化問題即是解決從有限物件集合中尋找“最佳”物件的問題。這個語境中的“最佳”是由給定的評價函式來衡量的，該函式將物件對映到某個分數或成本，其目標是找到成本最低的物件。大多數在實際中看起來有意思的組合最佳化問題(後文都簡略為COPs)很棘手，因為即使問題的規模大小隻增加一點點，集合中的物件數量也會以極快的速度增加，這使窮舉搜尋顯得不切實際。

為了讓問題更加直觀明瞭，我們把關注點放在一個特定的問題上，即著名的旅行商問題(TSP)。在這個問題中，假設有N座城市，銷售人員必須訪問所有的城市。無論如何，在城際間旅行會產生一定的成本，而我們必須找到一條路線，使整個出行成本降到最低。例如，下圖顯示了行遍美國各州首府的最佳路線圖：

這個旅行商問題廣泛存在於許多重要領域的應用，例如規劃、交付服務、製造業、DNA測序以及其他許多方面。尋找更好的路徑與解決財務等問題息息相關，這也促使科學界和企業投入大量物力財力來尋找更好的方法。

以K個城市為TSP例子構建一個旅遊路線，在路徑構建過程的每個階段會刪除一個城市，直到沒有剩餘的城市為止。在第一個階段，有K個城市可供選擇，在第二個階段，有K-1個選項，接著是K-2個選項，以此類推。我們能夠構建的潛在路徑總數量是每個階段所擁有選項數量的乘積，這個問題的複雜性為O(K!)。

然而，這種方法比較適用於數量較小的計算。比方說，假設有5個城市，則潛在旅遊路線的總數量為5!=120。但是對於有7個城市的情況來說，這個計算結果會立增到5040，10個城市已經達到則是3628800，100的結果更是驚人地高達9.332622e+157，而這數量遠遠超過了宇宙中原子的數量。

在現實生活中TSP的運用例項涉及到的是成千上萬的城市數量運算，為了能在合理的時間(可能是幾個小時)內解決問題，通常需要運用那些高度複雜的搜尋演算法和啟發式演算法，而這些演算法是通過幾十年下來的大量文獻所開發形成的。

不幸的是，在實際應用中出現的許多COPs具有獨特的細微差別和條件約束，它們阻止我們用最先進的解決方案來解決諸如TSP之類的已知問題，並且要求我們開發針對該問題的方法和啟發式。這個過程可謂長路漫漫障礙重重，可能需要相關領域專家來檢測特定問題組合，搜尋空間中的某些結構。

這些年來，由於深度學習在許多領域都取得了巨大的成功，讓機器自主學習如何解決問題似乎有望在未來實現。將演算法的設計過程自動化，使其能夠自發解決難以應對的COPs——這樣不僅能節約大量財力和時間，也許還能生成比人工設計更加可行的解決方案（就像我們目前在AlphaGo等成果中所能看到的一樣，它已經打敗了人類過去透過數千年所取得的經驗成就）。

早在2016年，一篇名為《基於圖表學習組合最佳化演算法》的論文就對這個問題進行了早期嘗試。在這篇文章中，作者訓練了一種叫structure2vec的圖神經網路，針對幾個有難度的COPs制定貪婪的構造解決方案，並獲得了非常好的近似比值(生成成本與最優成本之比)。

它的基本思路是這樣子的：用圖譜來表示待解決的問題，然後讓圖神經網路依據圖譜建立解決方案。在解決方案構建過程的每次迭代中，神經網路會觀察當前的圖表，並選擇一個節點新增到解決方案中，然後根據該選擇更新圖表，接著重複這個過程，直到得到一個完整的解決方案。

論文作者們使用DQN演算法來訓練神經網路，並證明了習得模型在運用到比所受訓練更復雜的問題例項時的泛化能力。這種模型甚至可以很好地泛化到1200個節點的例項中（同時在大約100節點的例項進行訓練），同時還能在12秒內生成比商業求解程式用時一小時所求得的更佳解決方案。

但是這個方法有一個很大的缺陷，就是他們會使用一個“輔助”方程來幫助圖神經網路尋找更好解法。這個輔助方程是人為設計用於解決特定問題的，而這恰恰是我們想要避免的。

這種基於圖例的展現方式非常容易理解，因為許多組合最佳化問題可以自然而然地以這種方式呈現出來，就如下面這個TSP圖例所展示的一樣：

圖中的每個節點代表每個城市，節點邊緣包含了城際間的距離，如果不考慮邊緣屬性，類似的圖形也能夠構建起來（如果我們出於某種原因不考慮距離因素在內的話）。近年來，基於圖形的神經網路模型（無關乎是否具備架構知識）以令人難以置信的速度流行開來。尤其令人矚目的是自然語言處理領域，它所使用的Transformer架構模型已經成為業內眾多工處理的最先進技術。

有許多優秀的文章詳細地解釋了Transformer 架構，所以本文不再深入剖析，而是做一個簡述。Transformer架構是由谷歌研究人員在一篇題為“Attention Is All You Need”的論文中所介紹的。在這篇著名的論文中，Transformer架構被用於處理NLP中所面對的序列難題。不同之處在於，我們可以向遞迴神經網路，如長短記憶網路（LSTM），直觀輸入一系列的輸入向量，而Transformer架構中只能以一系列物件的形式輸入，且必須採用特殊的方式來讓它看見“序列”的排列順序。這個Transformer是由一個多頭自注意力子層和一個完全連線的子層所組成的。

它與圖譜的關係在注意力層變得明顯起來，而這個注意力層實際上是輸入“節點”間的一種資訊傳遞機制。每一個節點都會觀察其他節點，同時定向那些對於它們自己看起來更“有意義”的節點。這與在圖譜注意力機制（Graph Attention Network）中執行的過程非常相似。實際上，如果使用一個掩碼來阻止單個節點向不相鄰的節點傳遞資訊，我們將會得到一個等價的過程。

在論文《注意！學習解決路由問題》中，作者們嘗試解決了幾個涉及圖解路由代理的組合最佳化難題，包括我們現在熟悉的旅行商問題。將輸入資料視為一個圖，並將其投入一個經過調整的Transformer構架並在構架中嵌入了圖的節點，然後依次選擇新增到路由的節點直到完成構建一個完整的路由為止。

將輸入資料視為圖形是一個比向其提供節點序列更為“正確”的方法，因為只要它們的座標不變，就能夠消除對所輸入城市順序的依賴性。這意味著，不同於上述的節點序列法，無論我們如何改變輸入城市的排列，給定圖神經網路的輸出值都將保持不變。

在論文所提及的構架中，圖譜是由Transformer 編碼器嵌入的，它在為所有的節點生成嵌入層的同時也為全圖生成單個嵌入向量。為了生成解決方案，每次給予一個特殊的上下文向量時都會給出一個單獨的解碼器網路，這個網路由圖嵌入、最後一個和第一個城市以及未訪問城市的嵌入組成，並會輸出一個未訪問城市的機率分佈，然後取樣生成下一個將要訪問的城市。這個解碼器會按順序生成要訪問的城市直到整個行程結束，然後根據旅程的長度給予反饋。

文中使用了一種名為REINFORCE的強化學習演算法來訓練模型，這是一種基於策略梯度的演算法。其版本所使用的虛擬碼如下圖所示：

文中使用一個滾輪網路來確切評估例項的難度，並定期使用策略網路的引數來更新這個滾輪網路。這種方法在解決幾個難題上取得了不錯的成效，效能上超越了前文所提到的其他方法。儘管如此，作者們仍在擁有至多100個節點的小型例子上訓練和評估模型。雖然這些結果很有希望，但這些例子與現實生活中其他情況相比，猶如小巫見大巫。

最近，一篇題為《透過深度強化學習在大型圖上學習啟發式演算法》的論文中向解決現實世界那般規模大小的問題邁出了重要一步。在文中，作者訓練了一個圖卷積網路來解決諸如最小頂點覆蓋(MVC)和最大覆蓋問題(MCP)這樣的大型例項問題。

針對這些問題，他們採用一種流行的貪心演算法來訓練神經網路進行嵌入圖並預測每一階段需要選擇的下一個節點，在此之後使用DQN演算法對其進行進一步的訓練。

他們在含有數百萬個節點的圖上測評了其方法，並取得了比當前標準演算法更優異快速的結果。雖然他們確實透過使用動手搭建的啟發式來幫助訓練模型，但在未來，這種方式可能會消除這種約束，並從白板狀態學會解決巨大難題。

總之，在無邊的搜尋領域中，尋找架構是強化學習的一個重要且實用的研究方向。許多批評強化學習的人聲稱，到目前為止，這項技術僅被用於解決遊戲和簡單的操作問題，想要將其應用到解決現實問題中還很有很長的路要走。

我們一起分享AI學習與發展的乾貨