国产综合视频播放,亚洲肏逼网,在线免费观看A∨,黄色片网站视频看免费在线,就操在线观看免费视频,操学生妹在线播放,中日韩欧美一级A片免费,亚洲高清中文字幕

最短路問題與標號算法系列推文傳送門：
最短路問題與標號算法(label correcting algorithm)研究(1) - 開篇介紹

一、問題描述

在開始介紹最短路問題之前我們先來簡單討論網(wǎng)絡(luò)流問題（network flow problems）

在我們?nèi)粘Ｉ钪校W(wǎng)絡(luò)無處不在：為我們提供電力能源的電力網(wǎng)絡(luò)，為我們提供方便通訊的電話網(wǎng)絡(luò)，滿足我們各種出行需求的交通網(wǎng)絡(luò)。

在所有這些問題領(lǐng)域，我們都希望某些實體(電力、消費品、一個人或一輛車,一個消息)從一個點到另一個點盡可能需要少的費用以及獲取最大的效益。這就是網(wǎng)絡(luò)流問題的實質(zhì)。

﹏﹏

﹏

根據(jù)不同的研究目的網(wǎng)絡(luò)流問題可分為：最短路徑問題（shortest path problem）、最大流問題（maximum flow problem）、最小費用流問題（minimum cost flow problem）、最小費用最大流問題（minimum cost maximum flow problem）等等

作為網(wǎng)絡(luò)流問題的研究內(nèi)容之一，最短路問題主要解決在網(wǎng)絡(luò)中從一個節(jié)點到另一個節(jié)點成本最低的路徑是什么。
一種最通用的最短路問題可以如此描述：希望在網(wǎng)絡(luò)中找到一條從源節(jié)點（source node）到接收節(jié)點（target node）的最小成本路徑，這里的最小成本可定義為路徑長度、旅行時間、旅行費用等。?二、應(yīng)用領(lǐng)域

二十世紀六十年代，在最短路問題的研究上已經(jīng)頗有成效，該問題在計算機科學(xué)、運籌學(xué)等學(xué)科的研究中一直是一個熱點問題。

最短路問題在現(xiàn)實應(yīng)用中也相應(yīng)的代表了最低成本、最短時間問題等。該問題作為網(wǎng)絡(luò)流學(xué)科中的經(jīng)典問題，以其豐富的適用性，具有廣泛的應(yīng)用領(lǐng)域。

單就交通運輸而言，最短路問題就已經(jīng)有如下重要應(yīng)用

應(yīng)用領(lǐng)域	相關(guān)文獻
車輛路徑規(guī)劃	畢明華. 動態(tài)物流中多點多源最佳路徑算法研究與實現(xiàn)[D].浙江理工大學(xué),2019.
公共交通換乘方案及線路規(guī)劃	張妍. 隨機環(huán)境下的地鐵換乘問題兩階段優(yōu)化模型[D].北京交通大學(xué),2016.牛學(xué)勤,王煒.基于最短路搜索的多路徑公交客流分配模型研究[J].東南大學(xué)學(xué)報(自然科學(xué)版),2002.馬良河,劉信斌,廖大慶.城市公交線路網(wǎng)絡(luò)圖的最短路與乘車路線問題[J].數(shù)學(xué)的實踐與認識,2004.
航空調(diào)度	田倩南. 面向航空調(diào)度中機場任務(wù)指派與受擾航班恢復(fù)問題的研究[D].華中科技大學(xué),2018.
供應(yīng)鏈管理	鄭金忠,陳宏紀,李興濤,李友虎.基于供應(yīng)鏈的航材配送最短路算法[J].物流技術(shù),2004.
鐵路運輸調(diào)度指揮	苗義烽. 突發(fā)事件下的列車運行調(diào)度模型與算法研究[D].中國鐵道科學(xué)研究院,2015.Meng, L., & ?Zhou, X. Simultaneous train rerouting and rescheduling on an N-track network: ?A model reformulation with network-based cumulative flow variables[J].Transportation ?Research Part B: Methodological, 2014, 67: 208-234.
交通流量分配	Zhou X , Taylor J , Pratico F . DTALite: A queue-based mesoscopic ?traffic simulator for fast model evaluation and calibration[J]. Cogent ?Engineering, 2014.顏佑啟,歐陽建湘.最短路—最大流交通分配法[J].中國公路學(xué)報,2005.柳伍生,賀劍,李甜甜,諶蘭蘭.出行策略與行程時間不確定下的公交客流分配方法[J].交通運輸系統(tǒng)工程與信息,2018.
行人出行	Shatu F, ?Yigitcanlar T. Development and validity of a virtual street walkability audit ?tool for pedestrian route choice analysis—SWATCH[J]. Journal of transport ?geography, 2018.
物流運輸	Mahmoudi M , Zhou X . Finding optimal solutions for vehicle routing problem ?with pickup and delivery services with time windows: A dynamic programming ?approach based on state-space-time network representations[J]. 2015.張運河,林柏梁,梁棟,高紅艷.優(yōu)化多式聯(lián)運問題的一種廣義最短路方法研究[J].鐵道學(xué)報,2006.
隨機條件下路徑規(guī)劃	Yang, L., & Zhou, ?X. (2014). Constraint reformulation and a Lagrangian relaxation-based ?solution algorithm for a least expected time path problem[J]. Transportation ?Research Part B: Methodological.?2014..Xing T , Zhou X . ?Finding the most reliable path with and without link travel time correlation: ?A Lagrangian substitution based approach[J]. Transportation Research Part B: ?Methodological, 2011.

三、數(shù)學(xué)模型

這里給出通用單源最短路徑數(shù)學(xué)模型描述：

G 是由節(jié)點集合Ν（元素個數(shù)為n）和弧集合A（元素個數(shù)為m）組成的網(wǎng)絡(luò)

定義節(jié)點s?∈ N?為源節(jié)點（source），其他節(jié)點為非源節(jié)點（non-source），路徑長度為該路徑所包含弧的長度之和。求解單源最短路徑問題就是找出源節(jié)點s到每一個非源節(jié)點i的有向最短路徑。最短路徑問題的數(shù)學(xué)模型如下：

最短路徑數(shù)學(xué)模型

我們可以采用GAMS軟件實現(xiàn)上述最短路徑模型，并得到準確最優(yōu)解。這里給出一個GAMS求解Chicago network的簡單案例(https://github.com/xzhou99/learning-transportation/tree/master/GAMS_code%20-space-time-network/1%20shortest_path）

GAMS建模過程

variable z;  binary variables  x(a,i,j ) selection of agent a between i and j;
  equations  so_obj  comm_flow_on_node_origin(a,i) origin node flow of agent a on node i at time t  comm_flow_on_node_intermediate(a,i) intermediate node flow of agent a on node i at time t  comm_flow_on_node_destination(a,i) destination node flow of agent a on node i at time t;
  so_obj.. z =e= sum (a,sum((i,j)$(arcs(a,i,j)>0.1), x(a,i,j)*travel_cost(a,i,j)));
  Model SP /ALL/ ;  solve SP using MIP minimizing z;

（左右滑動查看更多）此外，本文所研究的最短路徑問題無特殊說明外，均具有以下假設(shè)：
●?所有弧長均為整數(shù)值●?網(wǎng)絡(luò)包含從節(jié)點s?到網(wǎng)絡(luò)中所有其他節(jié)點的有向路徑●?網(wǎng)絡(luò)不包含負循環(huán)●?網(wǎng)絡(luò)為有向圖

四、最短路算法

面對最短路徑問題我們可以通過求解整數(shù)或線性規(guī)劃模型（詳見：https://en.wikipedia.org/wiki/Unimodular_matrix ）的方法求解，然而這種做法并不高效，當網(wǎng)絡(luò)含有負環(huán)或者網(wǎng)絡(luò)規(guī)模較大時現(xiàn)有計算能力很難對其求解。因此需要更高效的算法來求解最短路徑問題。

由于最短路徑問題的特殊性，基于圖論開發(fā)出了許多有效的迭代算法，例如：Dijkstra算法、Floyd-Warshall算法、Bellman-Ford算法等等。表2-3羅列了常見的最短路算法，這些算法被分為兩類：Label Setting Algorithm和Label Correcting Algorithm。

表2-3 常見最短路算法分類
這兩類算法基本出發(fā)點是相同的：在每次迭代時為每個非源節(jié)點分配一個臨時距離標簽，作為源節(jié)點到節(jié)點,最短路徑的估計值。
不同的是它們如何更新臨時距離標簽：Label Setting Algorithm，在每次迭代時將當前臨時距離標簽最小的更新為永久距離標簽，直到所有的臨時距離標簽都更新為永久距離標簽；
而Label Correcting Algorithm在每次迭代時都有可能更新臨時距離標簽的值，直到最后一次迭代時所有的臨時距離標簽才成為永久距離標簽。

正因為其更新機制不同，他們所適用的最短路徑問題也是有所區(qū)別的（如下表）。

Label Setting Algorithms與Label Correcting Algorithms適用條件

接下來我們以Dijkstra algorithm為例，證明標準Label Setting Algorithm對于含有負環(huán)網(wǎng)絡(luò)的不適用。

Dijkstra algorithm

令為永久距離標簽對應(yīng)的節(jié)點集合，非永久距離標簽對應(yīng)的節(jié)點集合，為網(wǎng)絡(luò)節(jié)點集合，為網(wǎng)絡(luò)節(jié)點個數(shù)，表示源節(jié)點到非源節(jié)點的臨時距離標簽，表示非源節(jié)點的前向節(jié)點，表示從節(jié)點發(fā)出的所有弧的集合（適用于本文所有符號表示）。

Dijkstra algorithm偽代碼如下：

 begin2:      S:="?"; S ?:=N;3:      d(i):=∞ for each node i∈N;4:      d(s):=0 and pred(s):=0;5:      while |S| 6:      begin7:         let i ∈S ? be a node for which d(i)=min{d(j): j ∈S ?};8:         S:=S ∪ {i};9:         S ?:=S ?– {i};10:         for each arc (i,j)∈A(i) do11:           if d(j) >d(i)+c_ij then d(j):=d(i)+c_ij and pred(j):=i;12:     end;13:???end;

表2-5?Dijkstra Algorithm
根據(jù)表2-5，求解圖2-1中從節(jié)點1到其他節(jié)點最短路徑
求解過程

①令,,,,;② 從中選擇節(jié)點1（距離標簽最小）作為當前節(jié)點，并將其從移到中（此時節(jié)點1標記為永久節(jié)點），之后根據(jù)判別條件將節(jié)點2和3的臨時距離標簽更新為，前向節(jié)點為；③ 繼續(xù)從中選擇節(jié)點3（距離標簽最?。┳鳛楫斍肮?jié)點，并將其從移到中（此時節(jié)點3標記為永久節(jié)點），之后根據(jù)判別條件將節(jié)點5的臨時距離標簽更新為,前向節(jié)點為；④ 繼續(xù)從中選擇節(jié)點5（距離標簽最?。┳鳛楫斍肮?jié)點，并將其從移到中（此時節(jié)點5標記為永久節(jié)點），之后根據(jù)判別條件將節(jié)點4和6的臨時距離標簽更新為，前向節(jié)點為；⑤繼續(xù)從中選擇節(jié)點4作為當前節(jié)點，并將其從移到中（此時節(jié)點4標記為永久節(jié)點），此時沒有可更新的距離標簽；⑥?繼續(xù)從中選擇節(jié)點2作為當前節(jié)點，并將其從移到中（此時節(jié)點2標記為永久節(jié)點），此時沒有可更新的距離標簽；⑦ 繼續(xù)從中選擇節(jié)點6作為當前節(jié)點，并將其從移到中（此時節(jié)點6標記為永久節(jié)點），此時沒有可更新的距離標簽，且為空，算法結(jié)束。

圖2-1 ?含有負環(huán)的有向圖（負環(huán)用紅色標識）由此得到節(jié)點1到其他各節(jié)點的最短路徑及其長度：1-2（6），1-3（4）,1-3-5-4（4），1-3-5（6），1-3-5-6（9）。

但應(yīng)注意到節(jié)點3、4、5構(gòu)成一個負環(huán)（負環(huán)長度為-1），只要經(jīng)過一次路徑長度就減少1，因此可以無限減少節(jié)點1到節(jié)點3,4,5,6的距離。由此可見，Dijkstra無法正確求解含有負環(huán)的網(wǎng)絡(luò)最短路徑問題。其他標準Label Setting Algorithm的情況類似，可自行舉出反例進行驗證。以上我們通過反例驗證標準Label Setting Algorithm不適合處理含負環(huán)網(wǎng)絡(luò)的最短路徑問題，Label Correcting Algorithm能否處理這種情況我們將在后續(xù)章節(jié)進行詳細探討。END

周學(xué)松教授是亞利桑那州立大學(xué)(ASU)可持續(xù)工程與建筑環(huán)境學(xué)院教授，目前是Transportation Research Part C的副主編，城市軌道交通urbanrail transit 執(zhí)行主編，Transportation Research Part B的編委。主要研究大規(guī)模多模式交通系統(tǒng)優(yōu)化和仿真算法。

文案&編輯：崔贊揚、李崇楠（北京交通大學(xué)）

審稿人：鄧發(fā)珩、周航、向柯瑋（華中科技大學(xué)管理學(xué)院）

指導(dǎo)老師：周學(xué)松（Arizona State University）

如對文中內(nèi)容有疑問，歡迎交流。（PS：部分資料來自網(wǎng)絡(luò)）

如有需求，可以聯(lián)系：

崔贊揚（北京交通大學(xué)博士：[email protected]）

李崇楠（北京交通大學(xué)本科：[email protected]）

周學(xué)松（Arizona State University Professor：? [email protected]）

鄧發(fā)珩（華中科技大學(xué)本科三年級：? [email protected]、個人公眾號：程序猿聲）

周航（華中科技大學(xué)本科一年級：[email protected]）

向柯瑋（華中科技大學(xué)本科一年級：[email protected]）

推薦閱讀：