查詢結果分析
來源資料
相關文獻
- The Shortest Path of a Sparse Graph--Nearest Service Searching of Vehicle Navigation System
- 農產品最適運輸路線之規劃--以臺中到新竹之路段為例
- Solving the Steiner Minimum Tree (SMT) Problem Using a Fast and Efficient 2-Step Heuristic Algorithm
- Path-Planning Information System of Autonomous Vehicle
- 最短路徑演算法理論複雜度與電腦執行時間之比較分析
- 三維電子地圖上機動車輛最佳路徑規劃與GPS之整合應用
- 利用改良式A*演算法於無人船的避碰路徑之規劃
- Together社群經營企劃案
- 水電維修網之系統建置與行銷策略擬定
- 航路3D自動規劃功能之研究
頁籤選單縮合
題名 | The Shortest Path of a Sparse Graph--Nearest Service Searching of Vehicle Navigation System=圖形最短路徑之快速演算法--汽車駕駛輔助資訊系統之最近服務搜尋 |
---|---|
作 者 | 莊益瑞; 洪集輝; | 書刊名 | 景文技術學院學報 |
卷期 | 10:1 1999.09[民88.09] |
頁次 | 頁77-85 |
分類號 | 557.82 |
關鍵詞 | 最短路徑; 基數堆積; 費氏堆積; 演算法; 依序傳播演算法; Shortest path; Radix heap; Fibonacci heap; Distance trasformation; The ordered propagation algorithm; |
語文 | 英文(English) |
中文摘要 | 在汽車駕駛輔助資訊系統中,常牽涉到最近服務站的動態搜尋問題,這些服務站 可能是加油站、停車場、醫院等, 過去最常被用來解決這個問題的方法是著名的 Dijkstra 演算法,不過這種方法應用在稀疏圖形時效率並不理想。在影像分析 (Image Analysis) 領 域有一種常被使用的工具稱為距離轉換 (Distance Transformation), 依序傳播演算法 ( Ordered Propagation Algorithm) 是計算距離轉換的快速演算法, 這種方法可經由適當的 改良來提昇計算最少成本問題的效率。 本篇論文將會比較我們的方法與常見的 Dijkstra's Algorithm、Radix Heap 和 Fibonacci Heap 等方法在效率上的差別。實驗結果證實我們的 方法之時間複雜度接近於線性時間 (Linear Time),較過去的方法有效率。 |
英文摘要 | The ordered propagation is an algorithm in Pattern Recognition categories for computing a distance transformation in rectangular domain. The main principle of this algorithm is that by using a job queue to place the unprocessed vertices in by two directions. The cost of found shortest path will be replaced when the new one is found. This will amend the overhead of the queue of propagated distance transformation, so that the algorithm is more efficient for searching the shortest paths. In this paper, we applied this concept for the shortest path problem on graph, and found the time complexity is linear which is better then the well known algorithm of Dijkstra and its improved versions using by Radix Heap and Fibonacci Heap. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。