gps在及物流方面的應(yīng)用-文庫(kù)吧
2025-06-07 15:54 本頁(yè)面
【正文】 由Ford提出了Ford算法,它能有效地解決含有負(fù)權(quán)的最短路問(wèn)題。Floyd算法適用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行V次SPFA算法。簡(jiǎn)單介紹一下Floyd算法。1，從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無(wú)窮大。2，對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。把圖用鄰接矩陣G表示出來(lái)，如果從Vi到Vj有路可達(dá)，則G[i,j]=d，d表示該路的長(zhǎng)度；否則G[i,j]=無(wú)窮大。定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息，D[i,j]表示從Vi到Vj需要經(jīng)過(guò)的點(diǎn)，初始化D[i,j]=j。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說(shuō)明從V5到V1經(jīng)過(guò)V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說(shuō)明V5與V3直接相連，如果D(3,1)=1，說(shuō)明V3與V1直接相連。（2） 單點(diǎn)動(dòng)態(tài)定位單點(diǎn)動(dòng)態(tài)定位的基本方程為ρj=[(XjXu)2+YjYu2+ZjZu2]12+d （1）試中，Xu，Yu，Zu為動(dòng)態(tài)用戶在tk時(shí)刻的瞬時(shí)位置；(Xj，Yj，Zj是第j顆GPS衛(wèi)星在其運(yùn)行軌道上的瞬時(shí)位置，它可根據(jù)廣播星歷計(jì)算；ρj為碼接收機(jī)所測(cè)得GPS信號(hào)接收天線和第j顆GPS微型之間的距離，即站星距離；d事由于接收機(jī)時(shí)鐘誤差等因素引起的站星距離偏差。利用（1）式解算用戶位置時(shí)，不是直接求它的三維坐標(biāo)，而是求各個(gè)坐標(biāo)分量的修正量，即給定用戶三維坐標(biāo)的初始值（Xu0,Yu0,Zu0）,而求解三維坐標(biāo)的改正值（?Xu,?Yu,?
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1