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

本發(fā)明涉及交通技術(shù)領(lǐng)域，特別涉及一種路徑規(guī)劃方法和裝置。

背景技術(shù)

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

目前，根據(jù)迪杰斯特拉算法做路徑規(guī)劃的過(guò)程中，采用從路徑規(guī)劃的起點(diǎn)向終點(diǎn)進(jìn)行發(fā)散的規(guī)劃原則，從起點(diǎn)發(fā)散到終點(diǎn)即告結(jié)束，從而確定出兩個(gè)城市之間的最短路徑。

由于從路徑規(guī)劃的起點(diǎn)向終點(diǎn)進(jìn)行發(fā)散，需要對(duì)每一個(gè)節(jié)點(diǎn)(實(shí)際中為路口)進(jìn)行計(jì)算，并且對(duì)于從終點(diǎn)到起點(diǎn)返回時(shí)，需要以終點(diǎn)為起點(diǎn)、以起點(diǎn)為終點(diǎn)，再次進(jìn)行發(fā)散。因此路徑規(guī)劃需要花費(fèi)大量的時(shí)間，從而路徑規(guī)劃的效率較低。

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

本發(fā)明實(shí)施例提供了一種路徑規(guī)劃方法和裝置，能夠有效地提高路徑規(guī)劃的效率。

第一方面，本發(fā)明實(shí)施例提供了一種路徑規(guī)劃方法，該方法包括：

A1：確定待規(guī)劃路徑的起點(diǎn)和終點(diǎn)；

A2：從所述起點(diǎn)到所述終點(diǎn)及從所述終點(diǎn)到所述起點(diǎn)同時(shí)進(jìn)行發(fā)散；

A3：當(dāng)檢測(cè)到存在滿足終止條件的終止節(jié)點(diǎn)時(shí)，終止發(fā)散并執(zhí)行A4；

A4：確定所述起點(diǎn)到所述終止節(jié)點(diǎn)的第一最短路徑以及所述終點(diǎn)到所述終止節(jié)點(diǎn)的第二最短路徑；

A5：將所述第一最短路徑和所述第二最短路徑組合，獲得所述待規(guī)劃路徑。

優(yōu)選地，所述從所述起點(diǎn)到所述終點(diǎn)及從所述終點(diǎn)到所述起點(diǎn)同時(shí)進(jìn)行發(fā)散，包括：

從所述起點(diǎn)到所述終點(diǎn)及從所述終點(diǎn)到所述起點(diǎn)分別執(zhí)行：

S0：將待處理節(jié)點(diǎn)作為當(dāng)前中間節(jié)點(diǎn)；

其中，從所述起點(diǎn)到所述終點(diǎn)的發(fā)散過(guò)程中，所述待處理節(jié)點(diǎn)為所述起點(diǎn)，從所述終點(diǎn)到所述起點(diǎn)的發(fā)散過(guò)程中，所述待處理節(jié)點(diǎn)為所述終點(diǎn)；

S1：確定與所述當(dāng)前中間節(jié)點(diǎn)可達(dá)的目標(biāo)節(jié)點(diǎn)；

S2：確定從出發(fā)點(diǎn)到每個(gè)所述目標(biāo)節(jié)點(diǎn)的最短路徑；

其中，從所述起點(diǎn)到所述終點(diǎn)的發(fā)散過(guò)程中，所述出發(fā)點(diǎn)為所述起點(diǎn)，從所述終點(diǎn)到所述起點(diǎn)的發(fā)散過(guò)程中，所述出發(fā)點(diǎn)為所述終點(diǎn)；

S3：確定每個(gè)所述目標(biāo)節(jié)點(diǎn)的最短路徑的距離，將距離最小的最短路徑對(duì)應(yīng)的最短目標(biāo)節(jié)點(diǎn)作為所述當(dāng)前中間節(jié)點(diǎn)，執(zhí)行S1。

優(yōu)選地，所述當(dāng)檢測(cè)到存在滿足終止條件的終止節(jié)點(diǎn)時(shí)，終止發(fā)散并執(zhí)行A4，包括：

實(shí)時(shí)判斷是否存在從所述起點(diǎn)到所述終點(diǎn)進(jìn)行發(fā)散的過(guò)程中以及從所述終點(diǎn)到所述起點(diǎn)進(jìn)行發(fā)散的過(guò)程中均經(jīng)過(guò)的節(jié)點(diǎn)，若是，則停止發(fā)散并執(zhí)行A4。

優(yōu)選地，在所述從所述起點(diǎn)到所述終點(diǎn)及從所述終點(diǎn)到所述起點(diǎn)同時(shí)進(jìn)行發(fā)散之前，進(jìn)一步包括：

確定所述待規(guī)劃路徑的所述起點(diǎn)和所述終點(diǎn)之間的至少一個(gè)節(jié)點(diǎn)；

對(duì)于從所述起點(diǎn)到所述終點(diǎn)，將所述起點(diǎn)添加到第一集合中，將所述終點(diǎn)和所述至少一個(gè)節(jié)點(diǎn)添加到第二集合中；

對(duì)于從所述終點(diǎn)到所述起點(diǎn)，將所述終點(diǎn)添加到第三集合中，將所述起點(diǎn)和所述至少一個(gè)節(jié)點(diǎn)添加到第四集合中；

所述S1，包括：

從第一待處理集合中，確定所述當(dāng)前中間節(jié)點(diǎn)可達(dá)的目標(biāo)節(jié)點(diǎn)；

其中，從所述起點(diǎn)到所述終點(diǎn)的發(fā)散過(guò)程中，所述第一待處理集合為所述第二集合，從所述終點(diǎn)到所述起點(diǎn)的發(fā)散過(guò)程中，所述第一待處理集合為所述第四集合；

在所述將距離最小的最短路徑對(duì)應(yīng)的最短目標(biāo)節(jié)點(diǎn)作為所述當(dāng)前中間節(jié)點(diǎn)之后，在所述執(zhí)行S1之前，進(jìn)一步包括：

將所述最短目標(biāo)節(jié)點(diǎn)從所述第一待處理集合中刪除，將所述最短目標(biāo)節(jié)點(diǎn)加入到第二待處理集合中；

其中，從所述起點(diǎn)到所述終點(diǎn)的發(fā)散過(guò)程中，所述第二待處理集合為所述第一集合，從所述終點(diǎn)到所述起點(diǎn)的發(fā)散過(guò)程中，所述第二待處理集合為所述第三集合。

優(yōu)選地，所述檢測(cè)到存在滿足終止條件的終止節(jié)點(diǎn)，包括：

實(shí)時(shí)判斷所述第一集合和所述第三集合中是否存在相同的共同節(jié)點(diǎn)，如果是，則將所述共同節(jié)點(diǎn)作為所述終止節(jié)點(diǎn)。

第二方面，本發(fā)明實(shí)施例提供了一種路徑規(guī)劃裝置，該裝置包括：地點(diǎn)確定單元、發(fā)散單元、判斷單元、路徑確定單元和組合單元，其中，

所述地點(diǎn)確定單元，用于確定待規(guī)劃路徑的起點(diǎn)和終點(diǎn)；

所述發(fā)散單元，用于從所述起點(diǎn)到所述終點(diǎn)及從所述終點(diǎn)到所述起點(diǎn)同時(shí)進(jìn)行發(fā)散；