查詢結果分析
來源資料
相關文獻
- Comparison of Heuristic Algorithms for Linear Fractional Shortest Path Problem on Cyclic Networks
- Modified Hamming Neural Network and Its Character Recognition System
- 多層級交換式區域網路
- 跨越官僚的專業線:網路力量與救災行動
- 具自我調適功能之線上課程問題自動回覆系統
- 散裝飼料車電腦化派車系統之建置
- 網際網路與無線通訊整合 (HiAir) 之服務
- BEX-VCS訊務管理之設計
- 中華電信與民營行動通信業者網路互連信號測試規劃
- IEC Station:一個Java Based的嵌入式系統
頁籤選單縮合
題 名 | Comparison of Heuristic Algorithms for Linear Fractional Shortest Path Problem on Cyclic Networks=循環網路中線性分式最短路徑問題之啟發式解法的比較 |
---|---|
作 者 | 阮金祥; | 書刊名 | 東吳經濟商學學報 |
卷 期 | 22 1998.09[民87.09] |
頁 次 | 頁1-18 |
分類號 | 448.6 |
關鍵詞 | 網路; 收斂迴路; 啟發式解法; Networks; Convergent cycle; NP-hard; Heuristic algorithm; |
語 文 | 英文(English) |
中文摘要 | 最短路徑問題是網路相關問題中最重要的幾種之一。本文探討的是每一弧線擁 有兩個參數 (如成本和時間 ) 之延伸性最短徑問題, 其目標是去找尋兩特定節點間單位時 間成本最小的路徑。這樣的目標式是將兩個線性函數的分式小最小化,所以此問題被稱為線 性分式最短路徑問題 (LFSP)。眾所周知,具負迴路 (negative cycles) 之最短路徑問題是 一種 NP-Hard 的問題同樣地, 其收斂迴路 (convergent cycles ) 之線分式最短路徑問題 也是一種 NP-Hard 的問題,其中所謂收斂迴路是指一迴路被重複繞行後, 將使成本對時間 的比值收斂。本文針對具迴路之線性分式最短路徑問題提出兩個啟發式解法,這些方法之實 證表現亦被同時提出、比較。 |
英文摘要 | The shortest path problem is one of the most important issues among network problems In this paper, and extension of this problem is considered wherein each arc possesses two parameters (such as cost and time). The object in this problem is to find path between two specified nodes that minimizes cost per unit time. Since such an objective involves minimizing the fraction of two linear objectives. it is called a linear fractional shortest path problem(LFSP). As it is well known, finding a shortest path in a cyclic network containing negative cycles is NP-Hard. While solving (LFSP) on a cyclic network containing convergent cyclles is also NP-Hard, where convergent cycle is a cycle which if traversed again and again results in smaller and smaller csot-to-time ratio values. Two heuristic algorithms are developed for LFSP on cyclic networks. Computational results on the performance of thses algorityms are presented and compared. |
本系統中英文摘要資訊取自各篇刊載內容。