查詢結果分析
相關文獻
- 軸式多維度指派問題演算法之研究
- Generalized Gray Codes with Applications
- Distributed Broadcasting Algorithms in Rotator Graphs
- Fractal Image Coding Using Projection-Based Classification and Variable Shape Matching
- 以類神經網絡模式分析颱風降雨與半分布並聯式水庫概念模式模擬颱洪歷線之串聯應用
- 線性軸幅路網接駁系統最適整合區位、路線與排班模式之研究
- 都市計畫草圖替選方案分析模式之實例研究
- MUSCL Type Algorithm for Acoustic Wave Equations in Heterogeneous Media
- 運用類神經網路於股價指數之套利--以日經225指數為例
- Genetic Algorithm Approach for Designing Fir Hilbert Transformers and Differentiators
頁籤選單縮合
題名 | 軸式多維度指派問題演算法之研究=An Algorithm for the Axial Multi-Dimensional Assignment Problem |
---|---|
作者 | 林吉仁; | 書刊名 | 技術學刊 |
卷期 | 13:3 1998.09[民87.09] |
頁次 | 頁471-478 |
分類號 | 319.16 |
關鍵詞 | 多維度指派問題; 演算法; 分枝界限法; 懲罰值; Multi-dimensional assignment problem; Algorithm; Branch-and-bound; Penalty; |
語文 | 中文(Chinese) |
中文摘要 | 傳統的二維指派問題可擴充為多維度軸式或面式指派問題,而兩者仍可視為0-1整 數規劃問題。然而,求解二維指派問題最有效率的匈牙利法,在三維以上的指派問題並不適 用。而軸式問題由於各切平面的元素有所重疊,所以比面式問題較不易處理。本研究應用分 枝界限法的觀念,提出一套求解軸式多維指派問題的懲罰值法;其分枝法則指標──懲罰值 的求法,亦可應用於面式指派問題。懲罰值法並與另一同可應用於四維以上問題的演算法比 較,發現隨著問題變數的增加,懲罰值法相對平均效率愈佳,但變異亦大。 |
英文摘要 | Traditional two-dimensional assignment problems can be extended to axial or planar multi- dimensional assignment problems. Both still belong to the 0-1 integer programming models. But the Hungarian method, which is the most efficient algorithm for two dimensional assignment problems, is no more feasible for multi-dimensional types, and because the entries of each facet on axial problem are not independent, it is more complex than the planar one. In this paper, we present an algorithm for the axial multi-dimensional assignment problem. The algorithm is based on the branch-and-bound technique with maximum penalty rule. The procedure for computing the penalty of this algorithm can also be applied to planar multi-dimensional assignment problems. The algorithm is compared with another algorithm on 3 and 4 dimensional problems. We find that the more the variables, the relatively faster the new algorithm, but it also exhibits larger variance. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。