[發(fā)明專利]導(dǎo)航設(shè)備中實(shí)現(xiàn)路徑規(guī)劃的方法

有效

• 申請?zhí)枺?/td>: 201110360440.4
• 申請日: 2011-11-15
• 公開（公告）號: CN102506886A
• 公開（公告）日: 2012-06-20
• 發(fā)明（設(shè)計(jì)）人: 張維軍
• 申請（專利權(quán)）人: 深圳市路暢科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 深圳市智科友專利商標(biāo)事務(wù)所 44241
• 代理人: 陳潤生

技術(shù)領(lǐng)域

本發(fā)明涉及交通領(lǐng)域中的路徑規(guī)劃，特別是路徑規(guī)劃的算法。

背景技術(shù)

迪杰斯特拉算法（Dijkstra）是由荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·迪杰斯特拉（Edsger?Wybe?Dijkstra）發(fā)明的。算法解決的是有向圖中單個(gè)源點(diǎn)到其他頂點(diǎn)的最短路徑問題。如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示城市間的距離，該算法可以用來找到兩個(gè)城市之間的最短路徑。

該算法的輸入包含了一個(gè)有權(quán)重的有向圖?G，我們以V表示G中所有頂點(diǎn)的集合。圖中的邊，是兩個(gè)頂點(diǎn)所形成的有序元素對(Vi,?Vj)，表示從頂點(diǎn)Vi到Vj有路徑相連。我們以E表示所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:?E→[0,?∞]定義，權(quán)重可以表示距離。因此，w(Vi,?Vj)就是從頂點(diǎn)Vi到頂點(diǎn)Vj的距離。圖中任兩點(diǎn)間路徑的距離，就是該路徑上所有邊的距離總和。已知圖中V有頂點(diǎn)V0，迪杰斯特拉算法可以找到V0到所有其他頂點(diǎn)的最短路徑。

在計(jì)算V0到其他頂點(diǎn)的最短路徑時(shí)，按下述步驟執(zhí)行：

1.?首先，設(shè)置兩個(gè)頂點(diǎn)集合S和T，S={V0},T={其余頂點(diǎn)}，T中頂點(diǎn)對應(yīng)的距離值為d(V0,Vi),如果V0與Vi之間有邊連接，則d(V0,Vi)=w(V0,?Vj)，否則，d(V0,Vi)為∞，

2.?從T中選取頂點(diǎn)W，條件是W與V0的距離值最小，將W從集合T中移入集合S，

3.?對T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值。

重復(fù)上述步驟2、3，直到S中包含所有頂點(diǎn)，即S=T為止。

該算法因其算法的效率而在導(dǎo)航軟件中被大量采用。

導(dǎo)航軟件中用于路徑規(guī)劃的地圖來自于現(xiàn)實(shí)中的道路交通網(wǎng)絡(luò)，因此該圖為典型的有向圖，而且根據(jù)該圖使用迪杰斯特拉算法做路徑規(guī)劃的過程中，還必須考慮到圖中各個(gè)頂點(diǎn)（實(shí)際中為路口）上包含的交通規(guī)則。公知的導(dǎo)航軟件路徑規(guī)劃，一般采用從路徑規(guī)劃的起點(diǎn)向終點(diǎn)進(jìn)行發(fā)散的規(guī)劃原則。同時(shí)為了縮短路徑規(guī)劃的時(shí)間，提高路徑規(guī)劃的效率，往往采用從起點(diǎn)發(fā)散到終點(diǎn)即告結(jié)束的原則，而事實(shí)上，這樣的規(guī)劃原則往往是以犧牲路徑規(guī)劃的合理性來縮短路徑規(guī)劃的時(shí)間提高路徑規(guī)劃的效率。

由于道路網(wǎng)絡(luò)為有向圖，同時(shí)在道路網(wǎng)絡(luò)上的路口常常存在交通規(guī)則，考慮到迪杰斯特拉路徑規(guī)劃算法的特性：已確定最短路徑的頂點(diǎn)不能被再次翻開，這樣常常會導(dǎo)致從起點(diǎn)到終點(diǎn)的路徑規(guī)劃失敗，其原因是：如果兩個(gè)位置點(diǎn)都連通到一個(gè)公共點(diǎn)，則從公共點(diǎn)過來的路徑規(guī)劃過程中，該兩點(diǎn)之間的道路不會被算法找到。如圖1中，位置點(diǎn)B和C通過S4和S5連通到公共點(diǎn)D，則從D向B、C方向的路徑規(guī)劃過程中，B和C之間的道路S3不會被找到。

如圖1所示，Start為起點(diǎn)，End為終點(diǎn)，交通規(guī)則規(guī)定：從道路S4經(jīng)B點(diǎn)不能到達(dá)道路S2，我們根據(jù)迪杰斯特拉路徑規(guī)劃原理，從Start點(diǎn)出發(fā)，當(dāng)G點(diǎn)、D點(diǎn)被依次翻開時(shí)，?Start、G和D點(diǎn)為有最短路徑的頂點(diǎn)的集合，

S={Start，G，D},

而End、A、B、C為尚未確定最短路徑的頂點(diǎn)集合，

T={End、A、B、C}。

根據(jù)D點(diǎn)的拓?fù)潢P(guān)系，從D點(diǎn)再次向外發(fā)散可以翻開C點(diǎn)和B點(diǎn)，當(dāng)C點(diǎn)和B點(diǎn)被翻開時(shí)，

S={Start，G，D，C，B}，

T={End、A}。

假設(shè)C點(diǎn)到Start點(diǎn)的距離小于B點(diǎn)到Start點(diǎn)的距離,因此應(yīng)該先發(fā)散C點(diǎn)，但我們發(fā)現(xiàn)和C點(diǎn)相連的B點(diǎn)和D點(diǎn)均為有最短路徑的頂點(diǎn)，從C點(diǎn)發(fā)散，已無頂點(diǎn)能再次被翻開，經(jīng)由C點(diǎn)地路徑規(guī)劃到C點(diǎn)結(jié)束；排除C點(diǎn)后，我們會發(fā)現(xiàn)另一個(gè)有最短路徑的頂點(diǎn)為B，根據(jù)B點(diǎn)的拓?fù)潢P(guān)系，從B點(diǎn)再次向外發(fā)散可以翻開的點(diǎn)只有A點(diǎn)，但分析B點(diǎn)地交通規(guī)劃，從S4經(jīng)B點(diǎn)不能到達(dá)S2，那么可以確定自S4到達(dá)B點(diǎn)地路徑不能翻開A點(diǎn)，而B點(diǎn)也不存在其它可以翻開的點(diǎn)，因此可以確定，經(jīng)由S4到達(dá)B點(diǎn)地路徑規(guī)劃在B點(diǎn)結(jié)束，自此，根據(jù)迪杰斯特拉路徑規(guī)劃原理結(jié)合實(shí)際的交通規(guī)則進(jìn)行的路徑規(guī)劃全部結(jié)束，但從Start點(diǎn)發(fā)散到的節(jié)點(diǎn)只有B、C、G、D點(diǎn)，而A點(diǎn)和End點(diǎn)均未被發(fā)散到，也就是說從Start點(diǎn)到End點(diǎn)不存在最短路徑。而實(shí)際上我們觀察圖形會發(fā)現(xiàn)：從Start點(diǎn)到End點(diǎn)的路徑時(shí)存在的，既：

如何解決上述問題，是導(dǎo)航軟件路徑規(guī)劃算法中普遍存在的技術(shù)難題。

發(fā)明內(nèi)容