最短路算法專業譯文.doc

(10頁)

'最短路算法專業譯文.doc'
?專業譯文最短路的算法:以實際道路網絡作為評估班級:2010122 姓名:張菲菲 學號:20102322文章摘自:F. BENJAMIN ZHAN, CHARLES E. NOON.Department of Geography and Planning, Management Science Program, The University of Tennessee, Knoxville, Tennessee 37996摘要:尋找嚴短路徑網絡的經典問題多年來一右?是大家的研究目標。這些研究成果已經導致 了一些不同的算法和大量的實證研究結果與性能。但是,Z前的研究并沒有在選擇計算實際 網絡道路的最短路徑問題方面提供一個明確的方向。大多數最短路徑算法的計算測試是基于 沒有實際網絡道路特征的隨機生成的網絡。在木文屮,我們提供了一個利用各種齊樣現實道 路網絡的最短路徑算法的客觀評價。在評估的基礎上,一套為計算實際道路網絡而推薦的最 短路徑算法是正確的。這種評價應該是對研究人員和從業人員在運籌學,管理科學,交通運 輸,地理信息系統方面特別有用。關鍵詞:實際網絡道路;隨機生成的網絡;Bellman-Ford算法;Dijkstra算法1.介紹最短路徑的計算在很多網絡和交通運輸分析屮都是一個重要的任務c在發展 上而,計算測試和最短路徑算法的有效實現i直在相關科學方面保持著重耍的研 究課題,比如運籌學,管理科學,地理,交通運輸和計算機科學。(參見Dijkstra 算法,1959;表盤等,1979; Glover- Klingman算法和Philips, 1985; Ahuja, 1990; Goldberg和Radzik, 1993)。這些研究成果已經衍牛出許多最短路徑的算法,此 外,對于算法的計算性能也有大量的實證研究。(參見比如,Glover- Klingman 算法等,1985; Gallo和Pallottino, 1988; Mondou , Crainic, Nguyen, 1991 ; Cherkassky, Goldberg, Radzik, 1993) □在面對解決最短路問題的任務屮,選擇正確的算法是必須要決定的。根據不 同的應用,算法的運行吋間在決策過程總將是一個重要的決定。盡管一些計算評 估已經在文獻中被報道(例如,Hung和Divoky,1988; Gallo和PallottinoJ988; Cherkassky等等,1993),在實際道路網絡屮,哪一個算法或哪一套算法運行的 更快,一直都沒有一個明確的答復,這是從業者所而臨的網絡問題屮最常見的。 本文的主要H的是確定哪種算法在實際道路網絡屮運行速度最快。第二個H標是 更好的了解在輸入數據吋算法性能的靈每攵度。過去的計算評估主要是基于隨機牛成的網絡。隨機網絡牛成的方法有很人的 差別c由此產牛的隨機網絡范圍從均勻分布的電弧長度的完整網絡到高度結構化 的網格網絡。與實際道路網絡相比,隨機網絡往往由不同連接程度的弧表示節點 的比例。本文所研究的真實網絡的弧形節點比例,范圍從2.66到3.28o在文獻報 道屮,弧形節點比例高達10,這跟很多隨機牛成的網絡描述屮是不同的。另一?方 面,隨機網絡不同于實際網絡,隨機網絡實際上是源于隨機網絡的弧長通常是隨 機抽取的一個獨立的方式。這可能會導致網絡違規行為,其屮,“遠遠”分開的 兩個相鄰的節點屮的一個可能是“關閉”的。這樣的違規行為可以強烈支持某些 類型的算法和夬幅放緩其他類型。隨機網絡的發電機在文獻小有一?個特征,就是, 我們認為導致實際與隨機網絡有著顯著差異的即他們為建立連接或在均勻的網 絡方式屮產牛的弧長中請一個過程。實際的網絡拓撲結構往往包含被高子網郊區 包圍的密集的城市網絡區域,然后進一步包圍農村道路結構。隨機網絡產牛的某 些方法可以復制一個特定區域,例如在市區電網的發電機,但是在實際網絡屮色 含一個混合不同類型的道路網絡的拓撲結構,是幾乎不可能模擬的。我們己經利用實際網絡測試了以15個為一組的最短路徑的算法。用于測試的 網絡包括來美國屮西部和東南部的10個州的道路網絡,以及橫跨美國大陸的美 國國家高速公路規劃網(nhpn) o我們研究的算法的相對排序跟過去的研究有所 不同,像Gallo和Pallottino ( 1988)和Cherkassky等人(1993)。對于不同學科的研 究人員和從業者來說這個結論是有用的,如運籌學,管理學,交通運輸,地理信 息系統,它們在某些應用程序屮都依賴最短路徑的計算。我們的研究主要集屮在 各種算法的相對速度。程序的運行和存儲要求的問題是很重要的,然而,經過嚴 格測試的公共域代碼的可用性,使得從業人員更容易的為口己獲取和實現這樣一 個代碼。本文屮的計算結果是為了計算最短路徑而使用公共領域的C源代碼集, 這是由Cherkassky等人(1993)經過輕微修改后提岀的。它們的實現被證明在計 算吋間上是快速的,在存儲要求上是有效的。本文的其余部分安排如下:第一部分提供了-?些以前的學習背景也總結了在 我們學習屮的一些算法測試。第二部分是了解計算研究的一些細節。第三部分, 文中得出了一套關于算法選擇的建議。2.背景文獻屮報道的一個最近由Cherkassky發起的有關最短路徑算法的學習是最 綜合的也是最新的。Cherkassky最近報道了一個有17種最短路徑算法的評價。在 他們的實驗屮,Cherkassky試驗了這17種有不同特征的隨機牛成的網絡的算法。 從他們的研究屮得到了一個重要的現象,就是沒有一個單一的算法能一直超越其 他各種類型的模擬網絡°在他們的結論,他們認為,用Dijkstra算法實現了雙桶 結構(dikbd)是計算網絡與非負弧長最好的算法,而Goldberg-Radzik算法在遠 程更新拓撲排序上(gorl)是一個很好的選擇。我們將用一個類似于Cherkassky算法的測試環境作為我們研究的出發點。我 們的評價不同于他們的評價,因為我們使用實際的道路網絡,而不是隨機產牛的 網絡。這17種算法在Cherkassky等人的評價中,只有15種是在我們的研究屮的。 因為我們不考慮無環網絡,所以Cherkassky等人測試所專用無環網絡的算法被排 除在我們的研究屮。同時,經過一些初步的測試后,我們發現,利用堆棧標記節 點來處理程序執行的方法比其他的算法更慢,因此,它是不被認可的。在繼續測試之前,讓我們正式介紹一些符號并定義最短路徑問題。網絡是一 個圖G = (N,A)由一-組節點的索引W , n = \N\和一個牛成的有向弧A , m = \A\ 組成。每個弧表示為節點的有序對的形式,從節點,到丿?節點,記為(/, j) o每個 弧匕丿)都有一個相關的數值5,表示距離或成本通過電弧發牛。在本文小,我 們假設一對節點,和丿是由兩個不同的有向弧代表之間的雙向傳送(門)和(川)。 給定一個有向網絡G = (N,A)與己知的弧長J,每個弧(z,j)g A,最短路徑問題 是要找到最短的距離(最低成本)從一個源節點到所有其他節點的節點集。表I l -h:種算法研究綜述縮寫算法的實現描述復雜度參考文獻。省略部分。KR)是將兩個數據集聚集在一起。 對數據集1,他們表現不佳的相對運行時間比例從5.12到8.24。在數據集2中, 分別提高了 dikh和DIKR的札I對性能比例為2.15和2.70。DIKF滯后于其他堆 實現的相對比例。他們分別是數據集的1屮的&24和數據集的2屮的4.31c相比,表現最好的算法,Dijkstra算法的單純實現(dikq)大約比數據集1 慢?五倍也比數據集2慢24倍。拓撲排序算法(GOR和gorl)在數據?集1的比率 為2.49和8.58。在數據集2, gorl保持相對緩慢,比例超過10,而關閉的性能 差距的比例為1.62o Bellman-Ford-Moore算法的實現(BFP和BF)在2到3倍 的吋間上比數據集1快,然后表現得菲常差的數據集2與約14和31的相對吋間 比率。最后,表III提供了一個衡量算法的可預測性。對算法和網絡的每個組合, 根據個人的時間進行了計算最短路徑樹牛成100個源節點和最大平均的平均吋 間比的計算。最后,給出了每一組網絡屮的最大平均的平均比率。高的平均比率 意味著算法采取了將每個節點的平均時間與較長時間的一些源節點作比較。 Bellman-Ford-Moore實現了數據集的最高平均比率。在Dijkstra算法的單純實現 屮數據集1的效率有點低,而數據集2的效率較高。大多數其他算法對數據集都 有相對較低的比例,這表明不論是不是源節點,他們都保持一致的速度性能。網絡名稱(縮寫)數據集1:9個狀態網節點數目絡與3個層;弧的數 目次的道路弧序點的比 例弧長在一個地理坐標系統屮電弧的長度是?I ?進制的。 這些值代表一個算法/網絡組合的CPU時間比效率嚴好的算法時間還要短。給定的CPU時間 是以毫秒為單位的。明顯的列里面:算法被命令通過增加整體的相對速度來提高算法的運行速度。平均數StdDev 函數內布拉斯加州52316463.140.8747640.2155510.142461(NE1)阿拉巴馬州(AL1)84225062.980.6503050.1288700.114031明尼蘇達州95129323.080.9724360.1751730.132083(MN1)愛荷華州(IA1)100326842.680.5737680.1199000」13719密西西比州(MSI)115632402.800.4988100.0954430.100703弗羅里達州(FL1)215563702.960.9230880.0752470.076590密蘇里州(MO1)239172083.060.4947300.0909770.064761路易斯安娜州243768762.821.0215260.0606620.067557(LA1)美國佐治亞州287884282.920.4785790.0683330.005668(GA1)數據集2:9個狀態網絡與4個層次的道路和美國國家高速公路規劃網路易斯安娜州(LA2)35793988802.760.3606780.0138740.015297密西西比州(MS2)399861205823.020.2320620.0154120.014000弗羅里達州(FL2)501091331342.660.4162120.0112070.015264愛荷華州(IA2)634072081343.280.2698230.0157330.009220明尼蘇達州654912093403.200.4109250.0172020.014107(MN2)亞拉巴馬(AL2)660821859862.820.2982320.0113830.012410密蘇里州(MO2)678992041443.000.2124700.0155420.013266美國nhpn (US2)754172059982.741.5003610.0660840.094758美國佐治亞州927922643922.840.1742450.0105110.000107(GA2)網絡的相對性能 整體性能算法NE1AL1MN1MSISCIFL1GAI總時間比率PAPE1.001.001.001.001.001.001.0015.121.00TWO-Q1.081.081.081.091.081.071.0616.221.07THRESH1.871.581.521.491.441.511.3322.261.47BFP1.431.571.592.361.951.992.5131.962」1DIKBA4.332.862.912.342.152.311.9535.412.34DIKB4.332.872.922.352」62.331.9735.612.36GOR2.472.472.492.592.502.422.4737.612.49DIKBM4.633.203.142.662.422.532.3139.982.64DIKED3.753.483.292.952.902.962.6745.252.99BF1.742.092.213.102.653.344.0548.353.20DIKQ3.244.394.074.175.123.935.8875.094.97DIKH4.615.374.714.875.264.685.3177.475」2DIKR6.376.085.825.205.205.244.7880.695.34DIKF7.598.257.827.578.427.738.23124.638.24GORI6.907.707.267.598.518.838.86129.708.58最小的CPU時間0.460.730.901.091.632.082.8715.12
關 鍵 詞:
算法 譯文 短路 專業
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:最短路算法專業譯文.doc
鏈接地址: http://www.476824.live/p-49949002.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 白小姐精选四肖必中一肖 股票在线配资 杨方配资开户 北京快3开奖和值 山东十一选五牛走势 海南环岛旅游线路 快乐双彩开奖牛彩 江西十一选五全天计划 黑龙江十一选五预测打 配资炒股手法上上盈下载 江西快三下载