第六十七章 ：兩秒！
「這並不難看出來。」
對上許志遠那帶著些詫異疑惑的目光，韓川輕輕笑了笑，開口解釋道。
「因為與普通的分層結構相比，基於公共運輸系統建立的分層繞不開換乘樞紐。」
「你剛才說用協調參數來處理交叉變量，這在交通流量那道題里是可以的。」
「因為交通流量那道題的交叉變量只有一對一的耦合，第一層的區域A和第二層的區域B共享一條道路。一對一的耦合，協調參數就夠了。」
「但更複雜的公交-地鐵-步行立體線路很難。」
說著，他指了指屏幕上的公交系統網絡示意圖。
「一個換乘樞紐在很多時候會對應多條線路，它不僅可能是骨幹層，還可能是支線層，甚至連入接駁層都是可能的。」
「就比如西直門、東直門這些站點，它們不僅交通流量巨大，而且還連接了多個不同分層，不同結構的路線。」
「在分層框架里，這種被多個層共享的節點，就是交叉變量。」
「普通的協調參數是很難處理這種複雜的共享關係的。你在用協調參數疊代的時候，會同時收到來自幾十條線路的更新信號，這些信號互相衝突，協調參數很難進行同時處理。」
「所以你即便是通過分層結構來在一定程度上分離了不同線路的數據，但在涉及到換乘樞紐的時候，傳統的方法依舊很難甚至是無法處理這個問題。」
聽完韓川的解釋，許志遠盯著屏幕上的網絡示意圖思索了起來：「如果不用協調參數的話，這裡能用什麼方法解決這種多對多的耦合數據？」
的確，在構建模型和代碼的時候，出現的問題正如韓川所說的一樣，在計算這些換乘樞紐的時候，數據量過於龐大難以通過協調參數處理。
韓川想了下，從桌上拿過一張空白的稿紙，在上面畫了一個對應的分層圖層。
不過相對比許志遠在電腦上建立的多層結構來說，他畫的圖層要多一個新的結構。
將紙張遞了過去，他開口道：「我覺得可以把這些交叉變量，也就是換乘樞紐統一歸到一個獨立的層級里去處理。」
「這個層級不負責任何具體的公交線路優化，只做一件事，匯總所有層對同一個換乘樞紐的使用需求，然後通過算法進行統一分配。」
「這樣一來，整套交通系統就可以並行兩種不同的算法。」
「你設置的骨幹層、支線層、接駁層在求解自己的線路優化問題時，都會用到換乘樞紐。但它們不能自己決定樞紐怎麼用。」
「它們把自己的需求報給共享層，共享層再匯總所有層的需求，在樞紐容量的約束下，統一分配。分配完了之後，各層再根據分配結果調整自己的線路方案。」
「如果調整之後產生了新的需求變化，就再報給共享層，再來一輪分配。」
「反覆疊代，直到所有層的線路方案和共享層的樞紐分配方案互相一致。」
聽完韓川的解釋，許志遠詫異地看了過來，蹙眉問道：「這樣計算量不同樣還是很大嗎？」
韓川搖搖頭，道：「並不會。」
「因為共享層處理的不是原始的線路數據，而是各層提交上來的需求匯總。」
「需求匯總的數據量相對較小，因為一個換乘樞紐，不管連接多少條線路，在共享層里只對應一個變量：該樞紐的總換乘流量。」
「你原來用協調參數處理的時候，每一條經過西直門的線路都要和其他所有經過西直門的線路做配對協調。」
說著，他提起筆，在稿紙圖層邊重寫了一個算式。
「假設西直門有n條線路經過，協調參數的數量是O(n²)。」
「那麼在共享層里，這n條線路各自向西直門提交一個需求值，共享層只需要處理一個變量。」
「也就是說，西直門的樞紐容量分配，那麼複雜度從O(n²)降到了O(n)。」
「更重要的是，這個O(n)的過程是有解析解的，即【L(x，λ)=i=1∑n(x−di)2+λ(x−C)】」
「其中d_i是第i條線路提交的需求值，x是共享層分配給該樞紐的總流量，C是樞紐容量上限，λ是拉格朗日乘子。對x求導，令導數為零.....」
許志遠看著那個矩陣表達式，沉默了幾秒。
然後他把韓川的稿紙拉過來，對照著上面的公式，開始修改自己的MATLAB代碼。
屏幕上的代碼一行行流暢地刷過，不到半個小時左右的時間，許志遠把代碼粘進主程序里，然後打開題目附件里的站點數據文件，配好輸入參數，按下了運行鍵。
屏幕上沒有立刻跳出結果，MATLAB的命令窗口裡，光標一閃一閃地，正在跑疊代。
等了大概兩秒的時間，結果出來了！
兩秒！
看著屏幕上的結果，許志遠下意識地以為是程序出buG了。
這速度，是不是也太快了？
他滾動滑鼠，仔細地檢查了一下疊代日誌，從頭到尾看了一遍。
第一輪疊代，共享層收到來自三層共一百二十條線路的需求數據，匯總成三十七個樞紐的容量分配方案。
第二輪疊代，需求變化量比第一輪下降了百分之七十。
第三輪，再降百分之五十。
到第五輪的時候，各層的線路方案和共享層的樞紐分配方案已經基本一致，偏差量降到了初始值的千分之一以下。
「嘶！」
「這怎麼可能！？」
「五輪收斂，每一輪的計算時間不到一秒！」
「這不是超算啊？！」
看著屏幕上的結果，許志遠的喉結滾動了一下。
他參加過這屆建模大賽，這道題拿國一的隊伍有十七支，而其中從建模到計算出結果，用時最短的也花費了足足六個小時的時間。
即便是單純看模型計算的速度，最短也耗時半個多小時。
而現在，他用自己的筆記本電腦做測算，僅僅是兩秒的時間，就完成了線路規劃。
雖然說測試用的數據量遠比不上正式建模大賽的資料庫，但別忘了，他跑模型用的設備，也遠比不上建模的計算機啊。
兩秒鐘！
這速度，如果放到07年的建模大賽上，用爆殺全場來形容都太保守了。
真要說，這種級別的產品，理論上已經不再是單純的競賽建模了，它具備了商業化的可能性！
對上許志遠那帶著些詫異疑惑的目光，韓川輕輕笑了笑，開口解釋道。
「因為與普通的分層結構相比，基於公共運輸系統建立的分層繞不開換乘樞紐。」
「你剛才說用協調參數來處理交叉變量，這在交通流量那道題里是可以的。」
「因為交通流量那道題的交叉變量只有一對一的耦合，第一層的區域A和第二層的區域B共享一條道路。一對一的耦合，協調參數就夠了。」
「但更複雜的公交-地鐵-步行立體線路很難。」
說著，他指了指屏幕上的公交系統網絡示意圖。
「一個換乘樞紐在很多時候會對應多條線路，它不僅可能是骨幹層，還可能是支線層，甚至連入接駁層都是可能的。」
「就比如西直門、東直門這些站點，它們不僅交通流量巨大，而且還連接了多個不同分層，不同結構的路線。」
「在分層框架里，這種被多個層共享的節點，就是交叉變量。」
「普通的協調參數是很難處理這種複雜的共享關係的。你在用協調參數疊代的時候，會同時收到來自幾十條線路的更新信號，這些信號互相衝突，協調參數很難進行同時處理。」
「所以你即便是通過分層結構來在一定程度上分離了不同線路的數據，但在涉及到換乘樞紐的時候，傳統的方法依舊很難甚至是無法處理這個問題。」
聽完韓川的解釋，許志遠盯著屏幕上的網絡示意圖思索了起來：「如果不用協調參數的話，這裡能用什麼方法解決這種多對多的耦合數據？」
的確，在構建模型和代碼的時候，出現的問題正如韓川所說的一樣，在計算這些換乘樞紐的時候，數據量過於龐大難以通過協調參數處理。
韓川想了下，從桌上拿過一張空白的稿紙，在上面畫了一個對應的分層圖層。
不過相對比許志遠在電腦上建立的多層結構來說，他畫的圖層要多一個新的結構。
將紙張遞了過去，他開口道：「我覺得可以把這些交叉變量，也就是換乘樞紐統一歸到一個獨立的層級里去處理。」
「這個層級不負責任何具體的公交線路優化，只做一件事，匯總所有層對同一個換乘樞紐的使用需求，然後通過算法進行統一分配。」
「這樣一來，整套交通系統就可以並行兩種不同的算法。」
「你設置的骨幹層、支線層、接駁層在求解自己的線路優化問題時，都會用到換乘樞紐。但它們不能自己決定樞紐怎麼用。」
「它們把自己的需求報給共享層，共享層再匯總所有層的需求，在樞紐容量的約束下，統一分配。分配完了之後，各層再根據分配結果調整自己的線路方案。」
「如果調整之後產生了新的需求變化，就再報給共享層，再來一輪分配。」
「反覆疊代，直到所有層的線路方案和共享層的樞紐分配方案互相一致。」
聽完韓川的解釋，許志遠詫異地看了過來，蹙眉問道：「這樣計算量不同樣還是很大嗎？」
韓川搖搖頭，道：「並不會。」
「因為共享層處理的不是原始的線路數據，而是各層提交上來的需求匯總。」
「需求匯總的數據量相對較小，因為一個換乘樞紐，不管連接多少條線路，在共享層里只對應一個變量：該樞紐的總換乘流量。」
「你原來用協調參數處理的時候，每一條經過西直門的線路都要和其他所有經過西直門的線路做配對協調。」
說著，他提起筆，在稿紙圖層邊重寫了一個算式。
「假設西直門有n條線路經過，協調參數的數量是O(n²)。」
「那麼在共享層里，這n條線路各自向西直門提交一個需求值，共享層只需要處理一個變量。」
「也就是說，西直門的樞紐容量分配，那麼複雜度從O(n²)降到了O(n)。」
「更重要的是，這個O(n)的過程是有解析解的，即【L(x，λ)=i=1∑n(x−di)2+λ(x−C)】」
「其中d_i是第i條線路提交的需求值，x是共享層分配給該樞紐的總流量，C是樞紐容量上限，λ是拉格朗日乘子。對x求導，令導數為零.....」
許志遠看著那個矩陣表達式，沉默了幾秒。
然後他把韓川的稿紙拉過來，對照著上面的公式，開始修改自己的MATLAB代碼。
屏幕上的代碼一行行流暢地刷過，不到半個小時左右的時間，許志遠把代碼粘進主程序里，然後打開題目附件里的站點數據文件，配好輸入參數，按下了運行鍵。
屏幕上沒有立刻跳出結果，MATLAB的命令窗口裡，光標一閃一閃地，正在跑疊代。
等了大概兩秒的時間，結果出來了！
兩秒！
看著屏幕上的結果，許志遠下意識地以為是程序出buG了。
這速度，是不是也太快了？
他滾動滑鼠，仔細地檢查了一下疊代日誌，從頭到尾看了一遍。
第一輪疊代，共享層收到來自三層共一百二十條線路的需求數據，匯總成三十七個樞紐的容量分配方案。
第二輪疊代，需求變化量比第一輪下降了百分之七十。
第三輪，再降百分之五十。
到第五輪的時候，各層的線路方案和共享層的樞紐分配方案已經基本一致，偏差量降到了初始值的千分之一以下。
「嘶！」
「這怎麼可能！？」
「五輪收斂，每一輪的計算時間不到一秒！」
「這不是超算啊？！」
看著屏幕上的結果，許志遠的喉結滾動了一下。
他參加過這屆建模大賽，這道題拿國一的隊伍有十七支，而其中從建模到計算出結果，用時最短的也花費了足足六個小時的時間。
即便是單純看模型計算的速度，最短也耗時半個多小時。
而現在，他用自己的筆記本電腦做測算，僅僅是兩秒的時間，就完成了線路規劃。
雖然說測試用的數據量遠比不上正式建模大賽的資料庫，但別忘了，他跑模型用的設備，也遠比不上建模的計算機啊。
兩秒鐘！
這速度，如果放到07年的建模大賽上，用爆殺全場來形容都太保守了。
真要說，這種級別的產品，理論上已經不再是單純的競賽建模了，它具備了商業化的可能性！