，即與節(jié)點(diǎn)p鄰接的前驅(qū)節(jié)點(diǎn)具有兩個(gè)節(jié)點(diǎn)q與節(jié)點(diǎn)j且節(jié)點(diǎn)p的后向節(jié)點(diǎn)為j，故有向弧上加權(quán)\n有兩個(gè)時(shí)間花費(fèi)權(quán)值：車(chē)輛從q方向行駛經(jīng)過(guò)p到達(dá)i的時(shí)間花費(fèi)權(quán)值為tqpi，從j方向行\(zhòng)n駛經(jīng)過(guò)p到達(dá)i的時(shí)間花費(fèi)權(quán)值為tjpi。 \n[0045] 根據(jù)本發(fā)明的一個(gè)實(shí)施例，圖1中所示小型交通路網(wǎng)加權(quán)時(shí)間花費(fèi)權(quán)值后的示意圖如圖4所示。以四元組的形式來(lái)描述該交通路網(wǎng)為：V={p,q,x,i,j} （節(jié)點(diǎn)集合）； \n[0046] E={,,,,,,,,,,}（有向弧集合）；\n[0047] T={ tjpq,tqpq,tqpi,tjpi,tjpj,tqpj,tpqp,tiqp,tiqi,tpqi,,tpqx,tiqx,tqxi,tqiq,tjiq,tpiq,txiq,tpij,tqij,tjij,tpji,tiji,tijp,tpjp }（時(shí)間花費(fèi)集合）；\n[0048] D={d,d,d,d,d,d,d,d,d,d,d}（路段長(zhǎng)度集合）。\n[0049] 綜上所述，本模型中如果車(chē)輛可以從與某個(gè)交叉口節(jié)點(diǎn)鄰接的多個(gè)前驅(qū)節(jié)點(diǎn)方向駛來(lái)，并且可以通過(guò)該節(jié)點(diǎn)到達(dá)其鄰接的后向節(jié)點(diǎn)，則該節(jié)點(diǎn)至其后向節(jié)點(diǎn)的有向弧上加權(quán)的時(shí)間花費(fèi)權(quán)值的數(shù)量等于其起始節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的數(shù)目。例如，圖4中節(jié)點(diǎn)p具有兩\n個(gè)前驅(qū)節(jié)點(diǎn)j和q并且具有后向節(jié)點(diǎn)i，故節(jié)點(diǎn)p至i之間的有向弧上加權(quán)有兩個(gè)\n時(shí)間花費(fèi)權(quán)值tqpj和tjpi。 \n[0050] 另外，在交通路網(wǎng)中出現(xiàn)禁止轉(zhuǎn)彎的情況時(shí)，也就是說(shuō)，從某節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)駛來(lái)的車(chē)輛不允許經(jīng)過(guò)該節(jié)點(diǎn)到達(dá)對(duì)應(yīng)的后向節(jié)點(diǎn)，則可以省略對(duì)應(yīng)的時(shí)間花費(fèi)權(quán)值。如圖4所示，由于禁止從節(jié)點(diǎn)x方向駛來(lái)的車(chē)輛經(jīng)過(guò)節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j，故有向弧上只加權(quán)有三個(gè)時(shí)間花費(fèi)權(quán)值(其中省略了txij)。應(yīng)注意的是，在加權(quán)過(guò)程中也可以將txij設(shè)置為無(wú)窮大。 \n[0051] 在圖5所示的車(chē)輛繞過(guò)環(huán)道情況，從i、j、k、m方向駛來(lái)的車(chē)輛向n方向行駛，由于各個(gè)方向繞過(guò)環(huán)道的路徑不一樣，理論上來(lái)說(shuō)，i方向繞過(guò)環(huán)道的時(shí)間是最長(zhǎng)的，j、k、m方向繞過(guò)環(huán)道所花費(fèi)的時(shí)間依次遞減。由此可見(jiàn)，從此等四個(gè)方向駛來(lái)的車(chē)輛繞過(guò)環(huán)道向n方向行駛到達(dá)其后向節(jié)點(diǎn)所花費(fèi)的時(shí)間是不相同的。因此，在數(shù)據(jù)采集過(guò)程中，不是采集交叉口處紅綠燈的延時(shí)、堵塞、排隊(duì)等參數(shù)，而是只需要實(shí)時(shí)采集車(chē)輛從進(jìn)入節(jié)點(diǎn)的初始時(shí)間以及到達(dá)其后向節(jié)點(diǎn)的終止時(shí)間，初始時(shí)間與終止時(shí)間的時(shí)間差值即為加權(quán)至兩節(jié)點(diǎn)之間的有向弧上的時(shí)間花費(fèi)權(quán)值。數(shù)據(jù)的采集通過(guò)外部的GPS設(shè)備來(lái)實(shí)現(xiàn)。 \n[0052] 數(shù)據(jù)庫(kù)中每一有向弧上各時(shí)間花費(fèi)權(quán)值都以圖6所示的單鏈表結(jié)構(gòu)來(lái)存儲(chǔ)，而此等單鏈表的首指針則統(tǒng)一存儲(chǔ)于圖7所示的鄰接表(其為一維數(shù)組)結(jié)構(gòu)中。應(yīng)注意的\n是，圖8中鄰接矩陣中各單元存儲(chǔ)的并非是表示節(jié)點(diǎn)間有向弧連接關(guān)系1或0，而是相關(guān)有向弧的單鏈表在鄰接表中對(duì)應(yīng)的表頭節(jié)點(diǎn)的索引。 \n[0053] 圖6中單鏈表的表頭節(jié)點(diǎn)由RID、SID、EID和next指針構(gòu)成，其中RID表示道路\n(有向弧)的編號(hào)，SID 表示該條道路的起始結(jié)點(diǎn)的編號(hào)，EID 表示該條道路的終點(diǎn)結(jié)點(diǎn)的編號(hào)，next指針指向帶有三個(gè)域(preID ,weight和next)的中間結(jié)點(diǎn)。preID是道路起始\n結(jié)點(diǎn)SID的一個(gè)鄰接前驅(qū)結(jié)點(diǎn)的編號(hào)， weight是從preID方向駛來(lái)的車(chē)輛通過(guò)SID的時(shí)間\n與行駛至EID的時(shí)間之和，next為指向下一個(gè)此類(lèi)型的中間結(jié)點(diǎn)的指針。以下是單鏈表的表頭節(jié)點(diǎn)、中間節(jié)點(diǎn)以及鄰接表的定義： \n[0054] 單鏈表的表頭節(jié)點(diǎn)定義：\n[0055] struct RoadInfo \n[0056] Long RID； \n[0057] Long SID; \n[0058] Long EID; \n[0059] PreNodeInfo * next; \n[0060] }\n[0061] 單鏈表的中間節(jié)點(diǎn)定義：\n[0062] struct PreNodeInfo\n[0063] {\n[0064] Long preID;\n[0065] Double weight;\n[0066] PreNodeInfo * next;\n[0067] }\n[0068] 鄰接表的定義：\n[0069] RoadInfo Road[N]; // N 是圖中有向弧的數(shù)目。\n[0070] 一般地，采用以下步驟來(lái)訪(fǎng)問(wèn)所述數(shù)據(jù)庫(kù)模塊中的數(shù)據(jù)： \n[0071] S1：訪(fǎng)問(wèn)鄰接矩陣，找到鄰接表中與有向弧對(duì)應(yīng)的單鏈表的表頭節(jié)點(diǎn)；\n[0072] S2：根據(jù)表頭節(jié)點(diǎn)，找到鄰接表中對(duì)應(yīng)的單鏈表；\n[0073] S3：遍歷單鏈表得到有向弧的各個(gè)時(shí)間花費(fèi)權(quán)值以及時(shí)間花費(fèi)權(quán)值是車(chē)輛從哪個(gè)方向駛來(lái)的時(shí)間花費(fèi)權(quán)值。\n[0074] 傳統(tǒng)的靜態(tài)路徑算法是以行駛路徑最短為目標(biāo)，而本導(dǎo)航方法是以行駛時(shí)間最短為目標(biāo)來(lái)優(yōu)化行駛路線(xiàn)，供車(chē)輛導(dǎo)航使用。因此，本導(dǎo)航方法中采用的靜態(tài)路徑算法在傳統(tǒng)Dijstra算法的基礎(chǔ)上做出了改進(jìn)，因?yàn)榕c傳統(tǒng)算法不同本模型中每條有向弧可能存在多個(gè)時(shí)間花費(fèi)權(quán)值，故在此引入了時(shí)間花費(fèi)權(quán)值cost（i，j，pre）函數(shù)，用來(lái)求得一條有向弧上加權(quán)的多個(gè)時(shí)間花費(fèi)權(quán)值中與當(dāng)前路段的前驅(qū)節(jié)點(diǎn)(行駛方向)對(duì)應(yīng)的時(shí)間花\n費(fèi)權(quán)值。 \n[0075] 在該導(dǎo)航方法的實(shí)施過(guò)程中，設(shè)定S集合表示已求得花費(fèi)時(shí)間最短路徑的節(jié)點(diǎn)的集合，V集合表示交通路網(wǎng)中所有節(jié)點(diǎn)的集合，節(jié)點(diǎn)vi∈V-S表示V集合中未加入S集合的\n節(jié)點(diǎn)，并且引入了信息變量s(vi)，d(vi)，p(vi)，其中s(vi)是布爾型變量用來(lái)表示節(jié)點(diǎn)vi是否已求得花費(fèi)時(shí)間最短路徑(當(dāng)節(jié)點(diǎn)vi求得花費(fèi)時(shí)間最短路徑，則s(vi)=true；當(dāng)節(jié)點(diǎn)vi未求得花費(fèi)時(shí)間最短路徑，則s(vi)=false)，d(vi)表示從初始起點(diǎn)v0到節(jié)點(diǎn)vi的最短時(shí)間花費(fèi)權(quán)值上限，p(vi)表示節(jié)點(diǎn)vi的后向指針。應(yīng)注意的是：上述對(duì)節(jié)點(diǎn)i是對(duì)節(jié)點(diǎn)vi的簡(jiǎn)化描述。 \n[0076] 具體地，在電子地圖中查找初始節(jié)點(diǎn)v0與終止節(jié)點(diǎn)vt之間的花費(fèi)時(shí)間最短的路徑包含以下步驟： \n[0077] 步驟一：通過(guò)設(shè)置在車(chē)輛中的GPS裝置采集獲得表示時(shí)間花費(fèi)權(quán)值的數(shù)據(jù)，以形成數(shù)據(jù)庫(kù)，其他步驟流程圖如圖9所示：\n[0078] 步驟二：選定初始節(jié)點(diǎn)v0和終止節(jié)點(diǎn)vt，分別初始化信息變量s(vi)，d(vi)，p(vi)，并且將初始節(jié)點(diǎn)v0標(biāo)記為已求得花費(fèi)時(shí)間最短路徑的節(jié)點(diǎn)，其到自身的最小時(shí)間花費(fèi)權(quán)值上限為0，使得s(vi) = false，d(vi)= cost(0,i,-1)，p(vi)=-1以及s(v0) = true，d(v0)=0，p(v0)=-1，節(jié)點(diǎn)v0無(wú)確定前驅(qū)節(jié)點(diǎn)，其中cost(0,i,-1)表示從節(jié)點(diǎn)v0到節(jié)點(diǎn)vi的多個(gè)時(shí)間花費(fèi)權(quán)值中的最小時(shí)間花費(fèi)權(quán)值并且如果節(jié)點(diǎn)v0與節(jié)點(diǎn)vi不相鄰，則取無(wú)窮大；\n[0079] 步驟三：考察未加入至S集合的所有節(jié)點(diǎn)，選擇與初始節(jié)點(diǎn)v0具有最小時(shí)間花\n費(fèi)權(quán)值上限的節(jié)點(diǎn)vj，將節(jié)點(diǎn)vj添加至S集合，使得d(vj) = min{d(vi)|s(vi) = false, vi∈V-S}并令s(vj) = true，由于在初始化過(guò)程中在節(jié)點(diǎn)v0與節(jié)點(diǎn)vi不相鄰時(shí)會(huì)取無(wú)窮\n大，所以節(jié)點(diǎn)vj一定與初始節(jié)點(diǎn)v0相鄰接；\n[0080] 步驟四：修改與節(jié)點(diǎn)vj鄰接且未加入S集合中的節(jié)點(diǎn)vk，如果d(vk)>d(vj)+ \ncost(j,k,p(vj))，則修改初始節(jié)點(diǎn)v0至節(jié)點(diǎn)vk的時(shí)間花費(fèi)權(quán)值上限使得d(vk)=d(vj)+ \ncost(j,k,p(vj))且修改節(jié)點(diǎn)vk的前向指針使得p(vk)=vj；\n[0081] 步驟五：判定終止節(jié)點(diǎn)vt是否加入S集合：如果終止節(jié)點(diǎn)vt已加入所述S集合，\n則從終止節(jié)點(diǎn)vt開(kāi)始遍歷其前向指針p所指向的節(jié)點(diǎn)，直至指針指向所述起始節(jié)點(diǎn)v0，從而獲得兩節(jié)點(diǎn)之間的花費(fèi)時(shí)間最短路徑；\n[0082] 步驟六：將步驟四中獲得的花費(fèi)時(shí)間最短路徑繪制在電子地圖上并且通過(guò)顯示模塊顯示出來(lái)。\n[0083] 其中，在步驟四中如果終止節(jié)點(diǎn)vt未加入所述S集合，則重復(fù)所述步驟三和步驟四，直至終止節(jié)點(diǎn)vt加入S集合。 \n[0084] 本發(fā)明并不局限于前述的具體實(shí)施方式。本發(fā)明擴(kuò)展到任何在本說(shuō)明書(shū)中披露的新特征或任何新的組合，以及披露的任一新的方法或過(guò)程的步驟或任何新的組合。
航.png/origine/0f6a94b4-6a53-4b94-aaeb-4bb81abe869d)
心標(biāo)簽1.png/origine/193a42c9-f5af-4d7e-a646-2a98eedabcb2)
1.png/origine/97cb1070-51e1-47b0-938b-4dd7d50acaa3)
心標(biāo)簽1.png/origine/a5a18e95-7c7d-491e-a093-713cda0b0ad7)
1.png/origine/d298c2c6-2c20-4903-a326-b23058822982)
分類(lèi).png/origine/757193e8-b4c3-4914-b1cc-be6edea0462a)
報(bào)告.png/origine/1498c825-49a3-4330-88fc-1905b67e541e)
起名.png/origine/3175514b-02e3-4aa6-89d0-80416df17e61)
公告.png/origine/381a92b0-52bf-4e0f-9661-362d60c740bd)
人報(bào)告.png/origine/580433d4-0746-43a0-b34c-de7b30623383)
監(jiān)測(cè).png/origine/a9485c85-19ac-4c1e-92b1-326e08a43366)
進(jìn)度查詢(xún)APP-二維碼.png/origine/04defa58-e927-4dd0-9bcc-7dde68c6a7ee)
產(chǎn)權(quán).png/origine/23a83bad-6c4d-44d0-8d0e-d3820225913f)
.png/origine/d15fc3a7-f08d-4b6b-80c3-81bd3705902e)
icon.png/origine/4967397a-2c85-42b9-a9d2-3c150b91098f)
間.png/origine/498975d4-944d-498a-875c-28ad22f2bb86)
