[發(fā)明專利]一種多條最短路徑的快速尋找方法在審
| 申請?zhí)枺?/td> | 201711045402.3 | 申請日： | 2017-10-31 |
| 公開（公告）號： | CN107860393A | 公開（公告）日： | 2018-03-30 |
| 發(fā)明（設計）人： | 劉靖宇 | 申請（專利權(quán)）人： | 劉靖宇 |
| 主分類號： | G01C21/34 | 分類號： | G01C21/34 |
| 代理公司： | 成都弘毅天承知識產(chǎn)權(quán)代理有限公司51230 | 代理人： | 徐金瓊,劉東 |
| 地址： | 610051 四川省成都市成華*** | 國省代碼： | 四川;51 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 多條最短 路徑 快速 尋找 方法 | ||
技術(shù)領(lǐng)域
一種多條最短路徑的快速尋找方法，可用于物流調(diào)度、GPS導航等實際中，屬于計算機網(wǎng)絡領(lǐng)域。
背景技術(shù)
隨著電子商務的飛速發(fā)展，物流網(wǎng)絡迅速膨脹，如何快速配送用戶購買商品，提高用戶體驗，成為物流業(yè)進一步發(fā)展的關(guān)鍵；其中快件配送中的路徑規(guī)劃問題是提高派送速度，改善用戶體驗的核心問題。實際快件配送往往是一個物流匯集中心到多個派送點，需要分別求出到各個派送點的最短路徑，同時現(xiàn)實中也需要備用多條最短路徑以供選擇，從而產(chǎn)生了單源多目的地的K最短路徑問題。當然，單源多目的地的路徑規(guī)劃問題不僅局限于物流行業(yè)，在其他領(lǐng)域比如GPS導航等應用也非常廣泛。
路徑搜索問題一般可以通過圖論中的最短路徑方法解決。常用的最短路方法有Dijkstra、A*算法等經(jīng)典方法。然而這些方法原本只是尋找出圖中給定點到任意點間的最短路徑，要計算單源到多目的結(jié)點的K條最短路徑，就需要多次迭代，復雜度高而且實現(xiàn)復雜。而實際應用中，更多的需要得到多條不帶回路的最短路徑。例如，在物流配送中，往往涉及到單個出發(fā)點到多個配送點的最短路徑規(guī)劃問題，即除了尋找最短路徑外，可能還需要尋找第二短、第三短、第四短等多條路徑備用。另外如果這些路徑中存在回路，在實際應用中沒有任何意義，即按規(guī)劃路徑實際通行，不可能經(jīng)過重復的結(jié)點。本發(fā)明中的路徑尋找方法在一次運行結(jié)束后就可以找到源結(jié)點到各個目標結(jié)點的K條最短路徑，并且不帶回路。
與單源最短路徑問題相比，單源多目的地的K最短路徑問題在方法設計上更為復雜，目前尚沒有一種K最短路徑方法如單源最短路徑方法中的Dijkstra方法一樣得到業(yè)界共識并且達到大規(guī)模實用化程度。
常用的K最短路徑搜索方法有Dijkstra、A*算法等。但是這些方法并不能一次運行就將源結(jié)點到各個目的地的K條最短路徑求出來，而且實現(xiàn)也較為復雜。本發(fā)明中的尋找方法可以有效解決這些問題。
發(fā)明內(nèi)容
本發(fā)明的目的在于：解決現(xiàn)有技術(shù)中采用Dijkstra、A*算法等經(jīng)典方法進行源結(jié)點到每個其他結(jié)點的多條(假定為K)最短路徑計算時，由于需要多次迭代，造成計算復雜；同時，所計算路徑不能有效避免回路，造成實際利用價值低的問題。
本發(fā)明采用的技術(shù)方案如下：
一種多條最短路徑的快速尋找方法，其特征在于，包括以下步驟：
(1)導入地圖，用戶確定源結(jié)點和各目的結(jié)點，以及所需尋找的最短路徑數(shù)目K，即源結(jié)點到每一個目的結(jié)點都要求出最短的K條路徑；
(2)定義水流數(shù)據(jù)結(jié)構(gòu)W(NodeList，reachTime)，WList和P，其中W表示一股水流，NodeList是一個鏈表，保存水流已經(jīng)經(jīng)過的目的結(jié)點以及即將流入的目的結(jié)點，reachTime表示水流到達NodeList中各目的結(jié)點的時間，WList中存儲的是當前網(wǎng)路中流動的水流，并按到達時間升序排列，P中存儲了源結(jié)點到每個目的結(jié)點的最短的K條路徑；
(3)初始化數(shù)據(jù)結(jié)構(gòu)，從源結(jié)點沿可走路徑引出恒速水流W1,…,WJ，J為源結(jié)點可走路徑的數(shù)目；將W1,…,WJ按到達時間升序排列插入WList中；
(4)從WList中取出第一條水流信息Wc，并將WList中的Wc刪除，取出Wc中目的結(jié)點Nt，在P中查看Nt是否已經(jīng)找到了K條路徑，若是，終止該目的結(jié)點Nt水流分流，轉(zhuǎn)到步驟(6)，否則，轉(zhuǎn)到步驟(5)；
(5)將Wc中NodeList分量保存到P中，接著分流目的結(jié)點Nt之前，判斷目的結(jié)點Nt分流到達的目的結(jié)點是否在P的NodeList分量中，若沒有,將目的結(jié)點Nt分流后到達的目的結(jié)點按水流到達時間的升序插入到WList中,否則放棄該可走路徑；
(6)判斷WList是否為空，若是，結(jié)束程序返回P，否則轉(zhuǎn)到步驟(4)。
進一步，所述步驟(3)中，源結(jié)點沿可走路徑引出的恒速水流的公式如下：
NodeListW|W＝Wj＝(n0,nj),reachTimeW|W＝Wj＝vj；
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于劉靖宇，未經(jīng)劉靖宇許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201711045402.3/2.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
