A Multiple Purpose Path Routing Algorithm

Abstract

路徑長度和轉彎次數一直是交通工具的主 要運輸成本因素，路徑越長則所花時間越久；而 每次轉彎必須減速也增加時間成本的支出。 然而，一條最快的路徑不應該只考慮距離長 短和轉彎次數，實際上，每段路徑可以行進的速 度也是一項重要的因素，但是同時考慮多項參數 的路徑搜尋演算法為NP-complete 的課題，故本 文使用的方式為將多組參數整合成一個參數；以 Kirby 提出的構想及Ahuja 等人改良之Dijkstra 演算法為核心發展成多功能最佳路徑演算法，在 一個n × n 的網格圖中，其運算時間複雜度為 O(n logC )，並可藉由調整相關變數來得到最短 路徑、最少轉彎數路徑和最快路徑等多種不同的 輸出結果路徑。