前言：中文期刊網精心挑選了運籌學最短路徑范文供你參考和學習，希望我們的參考范文能激發你的文章創作靈感，歡迎閱讀。
運籌學最短路徑范文1
關鍵詞： 高職院校 Dijkstra算法 標號法 表格
Dijkstra算法是典型的最短路算法，用于計算一個頂點到其他所有頂點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由于它遍歷計算的頂點很多，因此效率低。但Dijkstra算法是很有代表性的最短路算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構、圖論、運籌學等。
給定一個帶權有向圖，其中每條邊的權是一個非負實數。另外給定圖中的一個頂點，稱為源。現在我們要計算從源到所有其他各頂點的最短路徑長度。這里的長度指路上各邊權之和。這個問題通常稱為單源最短路徑問題。Dijkstra算法（標號法）是按各頂點與源點間的路徑長度的遞增次序，生成源點到各頂點的最短路徑的算法，即先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從源點到其他各頂點的最短路徑全部求出為止。
關于最短路問題Dijkstra算法的教學，看上去不難，但老師講授起來很費勁，學生學起來更加感覺困難。對此，不尋找恰當的教學方法，一味地啃書本是難以達到良好的教學效果的。往往還會致使學生厭學，從而對相關課程的學習失去興趣。高職學生相對于其他普通本科院校的學生，在數學學習方面能力要弱一些，因此，高職院校的數學教師更應該注意尋找適合的教學方法來提高學生的學習興趣，從而提高課堂教學效率。教師應改變過去“填鴨式”、“灌輸式”的教學方法，充分發揮學生的主體作用，靈活運用啟發式教學方法，激發學生思維和質疑，培養學生的創新精神和獨立探討問題的能力。要引導學生對問題多思考，多問幾個“為什么”，抓住內容相關和相反的部分，對知識進行橫向和縱向的比較，并掌握它們之間的內在聯系和規律，培養學生系統而全面的思維方式。教師應鼓勵學生主動發表自己的見解，互相探討、啟迪，培養學生勇于探索，敢于創新的精神，引導學生自主學習。此外，教學中還應注意確保學生有充分思考的時間，切實加強學生對問題的認識程度，讓高職學生真正感受到對數學的學習并不是那么困難的事情，不斷增強學習數學的成功感，增強學習信心，從而優化課堂教學效果。
。
各行的數據是怎么計算出來的呢？
例：用Dijkstra算法求下圖從頂點到其余頂點的最短路。
參考文獻：
［1］王信峰.計算機數學基礎［M］.高等教育出版社，2009.
運籌學最短路徑范文2
【關鍵詞】配電網；動態規劃技術；恢復供電
當前，智能電網的發展在一定程度上帶動了電網技術的發展，并且成為了電網技術發展的重要方向。實際上，智能電網的重要組成部分在于智能配電網，智能配電網的主要特征為擁有完備的自愈能力，同時還能夠最大程度的減少電網故障給用戶帶來的影響。而配電網故障的恢復是智能配電網自愈功能實現的重要過程，配電網故障恢復問題主要指配電網發生故障以后，在故障定位與故障隔離的基礎之上，應用一定的故障恢復策略對其進行操作，從而確保供電的平穩與正常。
一、對最佳路徑的分析
配電網故障區域恢復供電的最佳路徑事實上是在故障情況下的配電網絡重構。主要的目的在于，能夠快速的將非故障區域供電恢復，與此同時，還能夠有效的滿足線路負載容量的要求以及線損最小等各個方面的條件?，F階段，在配網自動化領域中研究最多的在于怎樣能夠快速的實現故障隔離以及快速的恢復費故障區域的供電技術方法，因此，在恢復路徑的最優化選擇方面出現了較多的研究。
一般而言，配電網故障區域恢復供電的路徑為多目標最佳路徑問題，現階段在最佳路徑問題的研究上較多的便是城市交通網絡中的最短路徑問題的研究。由于問題解決的思路存在著極大的不同點，因此最短路徑問題能夠被分為單元最短路徑算法與基于啟發式搜索最短路徑算法[1]。這與鄧群，孫才新，周駁仍凇恫捎枚態規劃技術實現配電網恢復供電》一文中的觀點極為相似。其中，單元最短路徑算法主要體現在幾個方面，即：
第一，在GIS空間查詢語言方面的最短路徑。該職工路徑的研究方法在當前還停留在理論研究方面，例如在MAX中定義了一套空間查詢語言，該套語言對其完備性給予了相關證明，同時通過舉證的方式，對范圍查詢與時態查詢等進行了應用分析。
雖然，對于GIS空間發展研究GeoSQL為一種有效的處理最短路徑的手段，但是GIS受到數據庫技術發展的制約與影響，導致實際的應用領域和背景的不同，使其和商用之間還有很長的一段距離。
第二，在功能模塊思想路徑方面，需要按照不同的分類方法實施，而單元最短路徑問題的算法能夠被分為很多種，例如神經網絡法與基于人工智能的啟發式搜索算法等，對于不同的背景應用需求和具體軟件應用的環境，各種算法在空間的復雜程度與時間的復雜程度等都有明顯的體現[2]，這與李振坤，周偉杰，錢嘯等在《有源配電網孤島恢復供電及黑啟動策略研究》一文中有著相似的觀點。并且各種算法在故障恢復方法中各具特色。
另外，啟發式搜索最短路徑算法也是一種有效的手段?；趩l式方向策略最短路徑算法，其中包括空間有效方向的可控參數法，該方法能夠有效的調節相關系數，在有效方向上路徑無效的時候，能夠確保得到有效的路徑。
二、最佳路徑的選擇方法分析
事實上，配電網故障區域恢復供電的最佳路徑并不是簡單的路徑問題，而是多目標最佳路徑問題。為此，在研究配電網非故障區域恢復供電的最佳路徑過程中，需要對其展開綜合的分析。
首先，在多目標分析方面，通常在選擇配電網非故障區域恢復供電最佳路徑的時候，最為重視的目標為：
第一，在恢復供電路徑的過程中，饋線負荷不能過載，同時，還需要確?；謴蛥^域的電壓質量能夠與實際規定的標準要求相吻合。當供電質量可靠性最高的時候，那么恢復的時間將會很短[3]；這與鄧昆英，汪鳳嬌，饒杰等在《智能配電網有功自治互動建模研究》一文中的觀點極為相似。另外，供電過程中，線損最低，證明開關拉合的次數最少，同時現場的操作點也會最少。
第二，在動態規劃技術恢復供電的最短路徑方面需要明確，動態規劃主要是運籌學的一個分支，它是求解決策過程的最優的數學方式。早在很久以前，就已經有研究人員對多階段過程轉化問題轉化為一系列的單階段問題，并且逐一進行求解，這標志著解決這類過程優化問題的新方法的創立，即動態規劃技術。
本文主要將一典型的復雜配電網絡作為研究例子，該連通系包括10個電源點，8個分支點，同時聯絡開關有16個。將其加入到配網潮流方向和典型的運動方式中，將聯絡開關和電源點作為定點，那么可以將其分為26個定點。盡管從數量上頂點比較多，但是由于存在著較為復雜的網絡關系，使得該問題成為一個極為簡單的最短路徑問題[4]。這與楊建在《配電網無功補償系統的關鍵技術研究》一文中的觀點有著相似之處。加之恢復路徑主要指費故障區域相關的聯絡開關與相應路由，為此我們可以將其理解為從不同電源點出發到各個聯絡開關的最短路徑問題，這樣一來，故障恢復工作的實施便簡單的多。
總結
本文主要從兩個方面左手，共同分析了采用動態規劃技術實現配電網恢復供電的方法與效果，一方面著手于最佳路徑的分析，另一方面著手于最佳路徑的選擇方法。從這兩個方面可以看出，利用動態規劃技術去實現配電網恢復供電是一種可行的方法。但是，受到歷史原因的影響，我國城市配電網絡還缺少標準的規范要求，導致配電網常常出現一些事故。因此，恢復配電網供電已經成為當務之急。隨著科技的發展，智能配電網已經被廣泛的應用在供電方面，這為平穩供電提供了一定的保障，同時也為恢復配電網故障供電創建了良好的環境與條件等。
參考文獻
[1]鄧群，孫才新，周駁.采用動態規劃技術實現配電網恢復供電[J].重慶大學學報（自然科學版），2006，29（3）：40-44.
[2]李振坤，周偉杰，錢嘯等.有源配電網孤島恢復供電及黑啟動策略研究[J].電工技術學報，2015，30（21）：67-75.
[3]鄧昆英，汪鳳嬌，饒杰等.智能配電網有功自治互動建模研究[J].機電工程技術，2014，（2）：4-7.
[4]楊建.配電網無功補償系統的關鍵技術研究[D].中南大學，2002，（12）：56-78.
運籌學最短路徑范文3
關鍵詞：LINGO；動態規劃； 最短路問題； 生產批量計劃問題
中圖分類號：G642 文獻標識碼：A 文章編號：1009-3044（2014）04-0743-04
在交通專業課程如《交通運籌學》、《交通系統分析方法》等的教學過程中，大量涉及到可劃分為多階段的優化問題求解，這些問題的求解一般使用動態規劃（dynamic programming）方法。動態規劃將決策問題的全過程劃分為若干個相互聯系的子過程（每個子過程為一個階段），然后按照一定的次序來求解。當劃分的階段個數較多時，手工求解動態規劃問題相當麻煩。由于在實際的交通工程規劃實踐中，涉及到的動態規劃優化問題規模往往較大，指導學生掌握相應的優化軟件求解動態規劃問題一方面能增進學生對動態規劃法的理解掌握，另一方面能鍛煉學生的編程能力，是一項十分有意義的教學工作。
美國LINDO系統公司開發的LINGO由其求解問題的高效性和穩定性，成為目前廣泛使用的優化軟件。LINGO是一套專門用于求解最優化問題的軟件包，其內置了一種建立最優化模型的的語言，可以簡便表達出問題，同時利用LINGO高效的求解器可快速求解并分析結果。LINGO在處理含有大量變量和約束條件的優化問題時，一般使用數組和矩陣的輸入方法：LINGO程序首先定義集合段，確定需要的集合及其屬性，然后定義數據段，用于輸入已知原始數據，最后使用函數對集合進行操作。在通常介紹LINGO使用的文獻中[1][2]，一般著重于敘述其如何求解線性規劃和非線性規劃等具有明確目標函數的優化問題，很少關注如何用LINGO求解復雜的動態規劃問題，該文通過分析交通運輸中常見的最短路問題和生產批量計劃問題，給出用動態規劃方法求解的LINGO代碼，指出LINGO可以在不需要目標函數的情況同樣很好地求解多階段優化問題。
1 動態規劃法求解實例
實例1 最短路問題
在縱橫交錯的公路網中（圖1所示），貨車司機希望找到一條從一個城市到另一個城市的最短路。圖中節點1—8代表貨車可以停靠的城市，弧旁的數字表示兩個城市之間的距離（百公里）。若貨車要從城市1出發到達城市8，問如何選擇行駛路線使所經過的路程最短。
問題分析：該最短路問題滿足動態規劃的最優性原理，即“從節點1到節點8的最短路的子路徑仍然是相應節點間的最短路”，用[D（i，j）]表示從節點[i]和[j]有弧相連時相應的距離，[L（i）]表示從節點1到節點i的最短路程數。則不難得到以下的動態規劃由前向后遞推方程：
根據式（1），再進一步定義當節點[i]在從節點1到節點[j]的最短路徑上時，[P（i，j）=1]，否則[P（i，j）=0]，編寫如下LINGO求解代碼：
運行LINGO得到如圖1所示的最優解報告。
從報告中可以看到，最短路徑找到，由[L（8）]的值可以得出，從城市1到城市8的最短路程數為14，由各個[P（i，j）]的值分析可知，從城市1到城市8的最短路線為[1258]。
實例2（生產批量計劃問題）
某企業生產某種產品用以滿足市場需求。通過統計，該產品今后[T]4周的外部需求（訂貨量）分別是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要開工生產，則第[t]周開工所需的生產準備費為[st]千元（與生產的數量無關），每件產品的生產費為[ct]千元。如果在滿足需求后周末有產品剩余，每千件產品的存儲費為[ht]千元。設第[t]周末的庫存量為[It]，假設開始沒有庫存，記為[I0=0]且不考慮生產能力限制，問工廠應如何安排生產，在按時滿足需求的條件下，使總費用最?。?/p>
問題分析：對于生產批量計劃問題，分析可知有如下兩條性質成立：
由于以上兩個性質，只有當上一時段庫存[It-1=0]時，本時段才考慮進行生產，且一旦生產，其生產量一定為某些后續時段需求量的總和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。這樣如用[ft]表示當[t]時段初始庫存為0時，從[t]時段到[T]時段的子問題的最優費用值，可以建立如下的遞推關系：
運行LINGO得到如下最優解報告：
從報告可以看到，[F（1）=561]，即從第1周到第4周末的最優費用為561（千元），分析其它[F]值得到，最優的生產批量計劃為第1周生產2（千件），第2周生產5（千件），第3周不生產，第4周生產4（千件）。
2 結束語
本文針對用動態規劃方法手工求解多階段優化決策問題十分繁瑣的特點，利用LINGO軟件將各個動態規劃遞推方程簡潔明確地編程實現，幫助學生更好的理解了各階段決策變量之間相互遞進的關系，同時更重要的是交通專業學生熟練地掌握了軟件的使用，才能解決實際工程規劃中的大規模復雜優化問題，LINGO軟件的教學實踐促進了《交通運籌學》、《交通系統分析方法》與《交通規劃》等課程的融合。
參考文獻：
[1] 李曉川，朱曉敏，趙乃東. 基于Lingo的運輸優化系統設計與開發[J]. 物流技術，2010（Z1）.
運籌學最短路徑范文4
關鍵詞 物流管理；運籌學；資源配置；最優化
中圖分類號 F252
文獻標識碼 A
文章編號 （2014）13-0112-01
物流業是指物品從發出地實體流動向接受地的過程。當貨物數量不斷增加，運送方式日趨多樣化時，如何配置運送物品時的資源成為較少物流企業成本，使企業利益最大化的關鍵。這其中就要運用到運籌學的思想，在既定的條件下，尋找能使目標函數最大化的組合。
一、運籌學與物流管理之間的關系
運籌學課概括為“依照給定條件和目標，從眾多方案中選擇最佳方案”，即在實行操作管理的各個領域，運用數學方法和包括概率論、數理分析、線性代數等在內的工具，對需要進行管理的問題統籌規劃人、財、物的組織、調度等，作出決策使系統運行最優解而必須使用的的一門應用科學。
在科學技術快速發展的社會，企業間的競爭變得異常激烈。減少開支，節約成本成為了企業管理中首要的問題。因此，隨著科學管理被越來越多的企業所重視，運籌學作為管理學的核心與基礎，自然有著極其重要的作用。作為管理工具，運籌學在企業產品定價問題，生產庫存問題，運輸問題等等一系列方面可以提供最優化模型。而物流系統的主要功能是將物品用最小的成本在兩地之間進行運輸，其追求的是一種及時快速，能夠最大程度節約人力物力的物流服務。從這一點上講，是與運籌學解決資源最優配置的目的不謀而合的。
物流管理較運籌學的起步較晚，但現代社會運籌學在物流企業中的作用不斷擴大。將兩者結合在一起，才能更好的實現達到企業節約成本的目的。
二、運籌學在物流系統中的運用
運籌學的主要理論包括規劃論、圖論、排隊論、博弈論等。在物流運輸這一龐大的系統中，每個環節都可以與運籌學中的理論相對應。規劃論中的線性規劃可以用來求解物資配送、人員分配等問題；整數規劃可以用來求解工作人員及機器數目、廠房選址等問題，動態規劃可以解決最優路徑生產調度、設備更新等問題。圖論可以直觀的將構建的模型反映出來，運用最短路徑和最大流等理論知識，可以求解運輸費用最小化、運輸路徑最短等重要問題。排隊論可以使物流運輸時最大程度得利用場地資源，解決運輸機或貨車應從哪個入口進入、如何離開等問題，提高物流系統的運作效率。
因此，物流系統中幾個關鍵的環節，包括運輸、儲存、裝卸、搬運、流通加工、配送等，都可以用運籌學中與之對應的方法。
三、運用運籌學節約物流成本
（一）基于線性規劃的運輸成本最優化問題
Z表示的是運輸所需的總費用，利用上述所給模型進行求解，即能得到一個使運輸費用最小的調配方案。
（二）基于圖論的物流網絡優化問題
設某種物資從m個倉庫發出，稱之為出發點，需要運輸至n個目的地，成為收貨點，在制定運輸方案時，首先需要畫一個示意圖，表明收發點的大致所在位置、貨物的收發量、運輸路途的長度。在示意圖上出發點用“”表示，收貨點用“”表示，將收貨量標記在其中。收發點之間的運費及其線路的長度標記在路途示意線的旁邊。然后做運輸物資的流向圖，物資運輸的方向用“”來表示，把調運物資的量記在“”的右邊并加括號表示和運輸線路長度的區別，這樣就構成了如下所示的物資調運流量圖。
在物流調運中，將物資從發點調運到收點的運輸方案有很多，但我們優化物流網絡的目的是使用運輸力量最小的方案。
（三）基于排隊論的倉庫人員配置問題
設某倉庫中，需要s個具有相同能力的工作人員為運貨車輛裝載，平均每人每小時可裝載μ輛貨車，平均每小時有λ輛貨車需要裝載，設貨車到來服從泊松分布，服務時間服從負指數分布。
根據排隊論的基本理論，我們可以輕易地看出在這里運貨車輛是顧客，工作人員是服務設施。我根據排隊論中關于標準的M/M/C的算法
多個服務站下 ， 表示系統中沒有運貨車輛的概率， 表示系統中有n個顧客的概率。因此平均隊長為 。平均等待時間為 。為了使系統中的運貨車輛不會排成無限的隊列，s必須滿足條件： 。
四、結語
物流業的發展離不開科學技術的支持，其中尤以運籌學為主。運籌學通過將物流系統中各個環節的變量和所要優化的目標抽象成模型，通過模型來理論的配置資源，使資源得到最合理的利用，從而達到節約成本、提高利潤的目的。
參考文獻：
[1]熊義杰.運籌學教程[M].北京：國防工業出版社，2004.
[2]宋偉剛.物流工程及應用[M].北京：機械工業出版社，2003.
運籌學最短路徑范文5
關鍵詞:最短路;迪杰斯特拉;數據結構;標準模板庫;優化算法
中圖分類號:TP312 文獻標識碼: A文章編號:1009-3044(2009)13-3439-04
1 引言
最短路問題是一個經典問題,過程涉及算法設計、數據結構、運籌學、圖論等多方面的知識,有很深遠的理論研究意義,并在許多學科中有重要應用。在實際生活以及工程實際應用中,最短路問題的求解算法也尤為重要,例如交通路線的選擇、公用設施的地點布局、管道線路的安排、智能機器人的路線選擇、最短時間規劃等等。
實際問題中又以單源最短路問題居多,解決單源最短路問題有比較優秀的迪杰斯特拉算法,著名的E.W.Dijkstra在1959年提出該算法,是圖論中求解最短路問題的一個經典算法。由單源最短路問題可以引申出更多類似的問題,比如時間規劃問題、成本預算問題、收益最大化問題等,這些與最短路同構的問題,往往可以應用Dijkstra算法得到滿意的結果。
隨著計算機技術的發展,絕大多數算法問題已經轉變為在計算機平臺上實現,其中又以使用計算機程序處理為主。在計算機編程實現的過程中,程序往往不夠優化,達不到令人滿意的結果,效率瓶頸突出。本文通過分析Dijkstra算法的本質,透徹分析計算機語言的特點,加之合理的數據結構,并使用C++語言實現優化的Dijkstra算法,達到了一般意義下的時間復雜度和空間復雜度的下限。
2迪杰斯特拉算法
2.1 迪杰斯特拉算法基本思想
單源最短路問題是指在一個有權的圖中求出源點到其他所有點的最短路徑,而Dijkstra算法是解決單源最短路問題的有效算法,在圖中不存在負環(即一條從源點到源點不經過重復的邊并且權值之和為負的路徑)的情況下,可以得到正確的結果。其基本思想是算法中的貪心思想:每次找到一條最短的未知路徑,然后用該路徑更新其他未知路徑的最短距離,直到不存在未知路徑為止。
2.2 迪杰斯特拉算法數學描述
步驟如下:
圖G=(V,E),其中V為點的集合,E為邊的集合,源點為src,已經求得最短路的目的點集設為S, 源點到點i的距離d[i]
1)?坌(src,i)∈E,置d[i] = V(src, i)
2)?坌(src,i)?埸E,置d[i] =∞
3)d[src] = 0;
4)?堝j∈V,j?埸S,使得d[j]=min{d[x]},x∈V,x?埸S
5)S=S+{j}
6)?坌i∈V,i?埸S,置d[i]=min{d[i],d[j]+weight(j,i)}
7)若|S|≠|V|,轉至2)
8)結束
2.3 迪杰斯特拉算法復雜度分析
分析2.2的數學描述,算法的時間消耗主要在循環上,而每次循環耗費時間的就是步驟4),即找未探索點中的最近點。設n=|V|,即n表示圖中頂點的個數;m = |E|,即m表示圖中邊的條數。則最多循環n次,因為每次循環將使得S中的點數增加一個;同時,每次循環中找最近點的過程需要找n次,因為總共有n個點。綜合考慮后,傳統迪杰斯特拉算法的時間復雜度為O(n2)。空間消耗主要在圖的存儲上,如果采用鄰接矩陣表示圖,則空間復雜度為O(n2)。
3 算法優化探究
3.1 使用鏈表優化
從上面的分析可以得到空間復雜度為O(n2)的算法,似乎空間復雜度不是很高,然而對于頂點很多,而邊卻很少的稀疏圖,用鄰接矩陣表示的圖在空間利用率上會相當低。因此,我們考慮到了使用基于鏈表的鄰接表來表示圖,從而將空間復雜度從O(n2)轉變為O(m),對于處理稀疏圖,有很大優勢。
在訪問圖中的邊時,若采用鄰接表,則訪問的次數也會有所降低,這是因為用鄰接矩陣表示圖的時候,對于邊的訪問,必須從一個頂點循環枚舉到所有頂點的邊,然而由于圖的稀疏性,一個點所連接的邊可能很少,甚至出度為0,此時用鄰接表就要明顯優于鄰接矩陣表示的圖。
3.2 使用靜態內存的鏈表優化
鏈表具有靈活和高效的特點,然而的實際應用過程中往往不那么容易。一方面是因為早期的C語言不具有鏈表數據結構,必須自己手動編寫鏈表結構,程序很容易出錯。對于參加程序設計大賽的選手來說,手寫代碼量較大的數據結構,除非在萬不得已時,一般是不會手寫數據結構代碼的,因為容易出錯,對于程序的正確性難以保證。在最短路問題中,若用鄰接表來表示圖,只需要編寫創建鏈表和訪問鏈表的函數,所以程序量在該算法中不是很大。
經常寫程序的話,就會體會到使用動態內存的數據結構,不但容易出錯,在效率上更是會明顯地降低。以約瑟夫問題舉例來說,使用鏈表數據結構按照理論應該是比數組直接簡單模擬的算法要快,然而在實際過程中就會發現兩者無太大差別,在數據量比較大的時候,數組反而比鏈表快得多。實際上這是鏈表使用了動態內存的原因,申請動態內存將會占據大量的時間。這就留給我們一個問題,在使用鏈表的過程中,是否可以使用靜態內存?對于程序設計很熟悉的人員,馬上可以想到,先申請一個很大的數組,然后將該數組作為動態數據申請的數據段,就可以實現靜態內存的鏈表。這樣優化之后,可以在很大程序上減少程序的運行時間,同時也可以減少系統管理動態內存出錯導致的問題。該優化措施的有效性可以在后面的實驗中得到驗證。
設有權有向圖G=(V,E),V是頂點的集合,|V|=n;E是邊的集合,|E|=m。下面給出使用靜態內存鏈表的定義過程,申請內存過程,以及創建鄰接表的過程,使用C++代碼表示如下:
//程序頭部
#include
#include
#include
using namespace std;
const int N = 31000, M = 2500000, INF = 1000000000;
//鏈表定義
struct data
{
int id, w; //指向頂點,權值
data *next; //鏈表后繼
}mem[M];
int mem_size, size, n, m;
//申請內存過程
node new_node(int id, int w)
{
mem[mem_size++] = (data){id,w,0};
return mem+mem_size-1;
}
//讀入邊的信息
for(i = 0; i < m; i++)
{
scanf("%d%d%d",&j,&id,&w);
tmp = g[j]->next;
g[j]->next = new_node(id,w);
g[j]->next->next = tmp;
}
3.3 使用高級數據結構進行優化
上面兩個步驟的優化都是行之有效的方法,然而在使用了靜態內存鏈表的數據結構后,我們仍不能降低該問題的理論時間復雜度上限O(n2)。再來透徹地分析一下原始的迪杰斯特拉算法,我們發現對于每次循環查找最近點的過程,最壞情況下循環上限是n次,查找問題是算法中一個典型的問題,我們通常會想到使用哈希表來查找,這樣可以將查找的的復雜度降低至O(1)的復雜度,然而哈希技術一般是針對數字方面的查找,對于從給定集合中查找最小值的問題,似乎束手無策,那么還有什么好的技術可以使用呢?
二杈搜索樹BST(Binary Search Tree)的查找過程和插入過程以及其他一些常用操作都只需要O(log n)的時間復雜度,常用的二杈搜索樹有AVL、Treap、Splay、紅黑樹等等,這些高級數據結構都有著很高執行效率,在解決算法問題的過程中得到了廣泛的應用,在數據庫技術中也有很多應用,是數據處理技術的理論基礎。然而要想自己寫出這些高級數據結構的全部操作,對于一般的程序設計者來說,還是有相當大的困難,雖然可以花費長時間來寫出模板,然后在以后應用過程中直接調用即可,但是在程序設計比賽等一些特殊場合來說,程序的精簡性尤為重要。
說到程序的精簡性,我們一定會想到STL(Standard Template Library),即標準模板庫。STL中包含了很多種數據結構的通用模板,使用起來尤為方便,程序簡潔,且不容易出錯。例如上面提到的BST,在C++ STL中使用了紅黑樹來實現,雖然不能實現BST的所有操作,但是對于處理最短路問題,使用C++ STL中的BST數據結構set,可以滿足要求。set具有插入,查找,刪除等操作,完全可以勝任最短路問題中的查找要求。
回頭再來思考Dijkstra算法,過程中主要的操作就是查找最小值,以及刪除最小值。只是對最小值處理的話,其實我們有更簡單的數據結構來處理,這就是被稱作“堆”的數據結構,堆支持查找最小值,刪除最小值,插入某個數值等操作,在最短路算法過程中使用堆的數據結構,不僅程序編寫量小,更重要的是查找效率比BST高得多,查找的時間復雜度可以降低至O(1)?？梢?如果使用的堆來查找,可以極大的降低時間復雜度,查找的時間復雜度為O(1),刪除最小值的時間復雜度為O(log n),總共循環n次,可見時間復雜度已經降低至O(n*log n),相比于原先的O(n2),有了很大的提高。
5 使用優先隊列全面優化程序
一個好的程序,不僅要求效率高,還要求容易實現,容易編寫,這也是為什么即使計算機的運算速度達到無限快時,我們還要繼續研究算法的原因。堆的數據結構實現起來并不困難,但是對于不熟悉的人來說還是有一定難度。其實這里我們可以繼續使用STL來簡化程序,簡化后的程序程序量小,簡潔易懂,應用價值很高。
STL中擁有heap的數據結構,也就是堆,但是STL中的heap并沒有封裝成類,在通用性和安全性上還存在問題,使用起來也不是很方便。STL同時提供優先隊列priority_queue,實際上就是把heap進行類的封裝,以方便使用。需要注意的是priority_queue默認為大根堆,而我們需要的是小根堆,所以需要自行編寫比較函數,以使用小根堆,具體的C++代碼如下:
typedef data * node;
node g[N];
bool mark[N];
int dist[N];
//定義堆內數據類型
struct heap
{
int id, dist;
};
//自定義比較函數以使用小根堆
bool operator < (const heap& x, const heap& y)
{
return x.dist > y.dist;
}
priority_queue a;
//最短路核心求解過程
int dijkstra(int s, int t)
{
int i, j, k, u, v, tmp;
node p;
dist[s] = 0;
a.push((heap){s,0});
for(i = 1; i
if(i!=s)
{
dist[i] = INF;
}
while(!mark[t] && !a.empty())
{
u = a.top().id;
a.pop();
if(mark[u])continue;
mark[u] = true;
for(p = g[u]->next; p; p = p->next)
{
j = dist[u] + p->w;
v = p->id;
if(j < dist[v])
{
dist[v] = j;
a.push((heap){v,dist[v]});
}
}
}
return dist[t];
}
6 算法效率評價
6.1 理論復雜度分析
再來分析一下上述算法的空間復雜度和時間復雜度。由于采用鏈表存儲,因此實際使用的內存不會超過2×m×sizeof(data),空間復雜度為O(m)。算法需要循環查找n次,而每次查找過程需要O(1)時間,刪除最小值需要O(log n)時間,整體時間復雜度為O(n*log n)。
6.2 實際效率分析
程序的效率最終體現在是否能在最短時間內得到正確結果,實際效率受到的影響因素較多,同一程序,同一時間,在同一臺機器上運行同樣的程序,其執行時間可能有不小差別,但是實際的運行時間體現了一般意義下的實際效率,值得研究。
編寫一般的Dijkstra最短路算法,和我們上面所寫的程序進行對比,在Visual Studio 2005中運行,得到如圖1結果。
可見,在圖的頂點數比較多的情況下,優化后的算法優勢明顯,原始的算法已經很難接受了。
7 結論
單源最短路問題是一個經典問題,在交通運輸、生產規劃、人工智能等方面有廣泛的應用。通過該文章的分析以及總結,我們對單源最短路問題已經得到了令人滿意的解答。將時間復雜度從O(n2)降低至O(n*log n),極大的減少了運行時間,在實際應用中可以得到更好的應用,即使在一些實時系統,我們也可以運用文章描述的優化算法,算法的實際運行時間基本上在毫秒級別,保證了時間上的高效。通過STL標準模板庫,使得算法的編寫也變得很容易,即使在一些特殊環境中,也能得到應用。
對問題的優化探究,往往來自于對問題的深刻認識,對工具的靈活運用,以及多學科之間的綜合分析,這是我們在科學研究中應該時刻銘記的。
參考文獻:
[1] Leiserson C E,Rivest R L,Stein C.算法導論(影印版)[M].2版.北京:高等教育出版社,2002:580-619.
[2] Sahni S.數據結構、算法與應用――C++語言描述[M].北京:機械工業出版社,2000:408-408.
[3] 魏寶剛,陳越,王申康.數據結構與算法分析[M].浙江:浙江大學出版社,2004:224-227.
[4] 陳媛,何波,涂曉紅,等.算法與數據結構[M].北京:清華大學出版社,2005:165-168.
[5] 朱承學,李錫輝.數據結構(C/C++描述)[M].北京:中國電力出版社,2004:131-135.
[6] 陳明.數據結構實用教程[M].北京: 清華大學出版社,2004:143-144.
[7] Bondy J A,Murty U S R.圖論以及應用[M].北京:科學出版社,1984.
運籌學最短路徑范文6
【關鍵詞】圖論；單目標優化；旅游線路；lingo
【基金項目】2015年安徽省大學生創新訓練項目：基于圖論的自駕游路線的設計與實踐（201510380025）.
隨著經濟的發展，家庭汽車的普及，人們不滿足于傳統的旅游方式，自駕游出行成為人們出游的重要方式.隨之人們需要一個更加符合自身要求的旅游路線.因此，以人本主義為出發點，將旅游線路設計的普適性與個性化結合，設計出一種更加符合自駕游者自身條件的旅游路線，有著極大的市場需求，并且會促進整個旅游業的健康發展.
通過我們的網絡調查問卷，對收集到的問卷進行分析，結果表明自駕游愛好者主要是大學生及上班的工作人員，自駕游出行時間主要集中在假期，影響自駕游出行路線的主要因素有時間（自駕游車程所耗費的時間）、費用（自駕游車程所耗費的費用）、路程、到達目的地所轉折的道路節點數等.現選取6個旅游景點作為自駕游的目的地進行相關的線路優化設計.
一、模型假設
1.在自駕過程中汽車平均以60 km/h的速度行駛，行程中無其他意外突發事件，以最短路徑作為行車路線.
2.每天的自駕時間和旅游時間為10小時，然后就找住宿的地方休息.
3.汽車在自駕過程中耗油為0.5元/km.（包括過橋、過路費用）.
4.旅游外出時間主要是自駕時間和旅游景點游玩時間，其他時間不計入.
5.每個景點的游玩費用固定不變，景點每天都按時間正常開放.
6.自駕游愛好者在景點的食宿費用為每個景點所在地一戶人家一天的平均消費費用.
二、模型的建立與求解
把游客要游覽的每個景點看作圖中的一個節點，各景點之間的距離、時間、費用看作圖中對應邊上的權，各景點的線路網就轉化成一個加權無向圖G.自駕游愛好者從某一節點出發，游遍圖中的每一個節點有且H有一次，最終回到出發點使得總時間、總費用或總路程最優的自駕游路線，即旅行售貨員問題，旅行售貨員問題是一個完全NP問題[1].對于單目標優化問題，問題可行解的優劣可以通過比較解的大小來判斷優劣，從而得出問題的最優解[2].我們將以蕪湖為出發地，其他地點作為自駕游的目的地.其中，將游覽景點的節點分別記為vi（i=1表示在出發地蕪湖，i=2，3，…，6分別代表游覽景點黃山、杭州、舟山、揚州、南京），通過經緯度換算等方式計算給出以下相關的數據，分別建立了以路程最短和費用最少為目標函數的路線模型.
