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