路徑規(guī)劃方法和系統(tǒng)

基本信息

申請?zhí)?/td> CN200910158931.3 申請日 -
公開（公告）號 CN101944095A 公開（公告）日 2011-01-12
申請公布號 CN101944095A 申請公布日 2011-01-12
分類號 G06F17/30(2006.01)I;G01C21/34(2006.01)I 分類 計算；推算；計數(shù);
發(fā)明人 柳宗偉 申請（專利權(quán)）人 廣東融訊信息科技有限公司
代理機構(gòu) 北京康信知識產(chǎn)權(quán)代理有限責任公司 代理人 廣東融訊信息科技有限公司;廣東瑞圖萬方科技股份有限公司
地址 510656 廣東省廣州市天河區(qū)黃埔大道西平云路163號6樓自編1房
法律狀態(tài) -

摘要

摘要 本發(fā)明提供了一種路徑規(guī)劃方法和系統(tǒng)，其中，方法包括以下步驟：將道路映射成交通網(wǎng)絡(luò)拓撲圖中的結(jié)點，將道路的端點映射成交通網(wǎng)絡(luò)拓撲圖中的弧段；從原結(jié)點和目標結(jié)點雙向搜索得到多個當前結(jié)點；依次計算多個當前結(jié)點到原結(jié)點和目標結(jié)點的代價，得到從原結(jié)點到目標結(jié)點的代價最小的當前結(jié)點；根據(jù)代價最小的當前結(jié)點和原結(jié)點以及目標結(jié)點，得到從原結(jié)點到目標結(jié)點的路線方案。本發(fā)明克服了現(xiàn)有技術(shù)中采用鄰接矩陣的Dijkstra方法來存儲交通網(wǎng)絡(luò)拓撲數(shù)據(jù)，雖然可以在O(1)時間內(nèi)完成(i；j)是否是一條網(wǎng)絡(luò)邊的查詢，但對最短路徑規(guī)劃最關(guān)鍵的關(guān)聯(lián)結(jié)點的查詢，其復雜度均為O(n)，導致查詢的復雜度較高的問題。