路徑搜索方法和系統(tǒng)

基本信息

申請?zhí)?/td> CN200910158931.3 申請日 -
公開（公告）號 CN101944095B 公開（公告）日 2012-09-12
申請公布號 CN101944095B 申請公布日 2012-09-12
分類號 G06F17/30(2006.01)I;G01C21/34(2006.01)I 分類 計算；推算；計數(shù);
發(fā)明人 柳宗偉 申請（專利權(quán)）人 廣東融訊信息科技有限公司
代理機(jī)構(gòu) 北京康信知識產(chǎn)權(quán)代理有限責(zé)任公司 代理人 余剛
地址 528305 廣東省佛山市順德高新區(qū)(容桂)建業(yè)中路7號
法律狀態(tài) -

摘要

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