臺灣博碩士論文加值系統

本文介紹一種解決最短路徑問題的數值演算法，首先藉由流向表之觀念將網路結構轉換為二維式數據結構，以利數值儲存與處理。接著透過梯式數值運算，可以轉換得出最小擴張樹，以及迴路鏈集之架構，最後藉著虛構路徑之助即可求出最短路徑解答。
本文所提出之演繹法以MATLAB軟體處理做實例之解釋，對於網路拓撲複雜之最短路徑搜索問題上，可由此演算法加以解決。本演算法在於節省最短路徑問題之運算處理過程，並可運用於作業研究、運輸問題，及電腦網路之連線維護作業上。

This paper presents an innovative numerical method of the shortest path problem for a network. Firstly, the topological structure of a network is converted into a two-dimensional data structure via Flow-table so that data storage and numerical processing can easily be made. Secondly, by the Echelon form processing, Minimum Span Tree and Tie-set links of the network under studied can be identified. Finally, by taking advantages of a hypothetical path, the shortest path of the network can then be obtained.
The proposed method in this paper is also illustrated by a numerical example via MATLAB software. The shortest path for a large network with complex topology can be solved by the proposed method with easy-processing features. The method is applicable to the fields of operations research, transportation management, and computer networking.

目錄
圖目錄………………………………………………………………………………...Ⅵ
表目錄………………………………………………………………………………...Ⅶ
第一章 緒論…………………………….……………………………….………….1
1.1 研究動機與目的……………………………………………..……….……..1
1.2 本文特點………………..……………………………………..…..…….......2
1.3 研究範圍………………..…………………………………….…..………....2
1.4 研究方法及論文架構…..………………………………….………..……....3
第二章 最小擴張樹與最短路徑之問題及文獻回顧…………………........4
2.1 最小擴張樹問題…………..……………………….…………………..…....4
2.2 最小擴張樹問題的一些基本概念……………………………....………….5
2.3 最小擴張樹之最佳化……………………………….……....………………7
2.4 最小擴張樹演算法之文獻回顧……………………………….……....……9
2.5 最短路徑…………………………………….……....……………………..10
2.6 最短路徑演算法之文獻回顧…………………..………………………….13
2.7 最短路徑之演算法探討……………………..……………………….……16
第三章 最小擴張樹問題之數值方法……………….………….…………....18
3.1 流向表架構………………..……………………….……………………....18
3.2 入映矩陣………….………………………………………………………..18
3.3 先標處理…………………………………………………………………...19
3.4 梯式流向表………………………………………………………………...20
3.5 後標處理…………………………………………………………………...21
3.6 最小擴張樹型態…………………………………………………………...21
3.7 最小擴張樹之演繹步驟………………………………………………...…23
3.8 不考慮分支方向性之最小擴張樹求法……………………….…………..28
3.9 小結………………………………………………………………………...32
第四章 最短路徑問題之數值方法………………………….………….…….33
4.1 迴路鏈集矩陣………………..…………………………………………….33
4.2 最短路徑解答…..………………………………………………………….33
4.3 路徑判斷原則……………………..……………………………………….34
4.4 最短路徑之演算法………..……………………………………………….34
4.5 釋例……………..………………………………………………………….35
4.6 小結……………..………………………………………………………….43
第五章 多目標限制情況下之最短路徑解法……………….…………..….44
5.1 簡介……………………..………………………………………………….44
5.2 本文方法……..…………………………………………………………….44
5.3 釋例……………………..………………………………………………….46
5.4 小結…………………………………..…………………………………….53
第六章 結論與建議………………………………………….…………...……...54
6.1 結論……………………..………………………………………………….54
6.2 建議……………………..………………………………………………….55
參考文獻 ………………………………………………….......…………………….56
圖目錄
圖2-1 擴張樹之說明……….…………………………………………………………6
圖2-2 擴張樹特質說明…….…………………………………………………………7
圖2-3 切集與路徑最佳化狀況….……………………………………………………8
圖2-4 網路圖脈例子…………....………………………………………………...….11
圖2-5 網路方向性之說明………….…………………………………………….….12
圖2-6 網路圖A…………….……………………………………………………...…13
圖3-1 網路圖B……………….…………………………………………………...…18
圖3-2 網路圖C……..……………………………………………………...………...24
圖3-3 具有方向性之網路圖C.…………………………………………………...…24
圖3-4 加入虛構路徑之網路圖C.………………………………………………...…26
圖3-5 具方向性之網路圖C的最小擴張樹架構……………………………………27
圖3-6 加入虛構路徑之網路圖C……………………………………………...…….29圖4-1 網路圖D…………....……………………………………………….……...…36
圖4-2 加入虛構路徑之網路圖D.………………………………………………...…38
圖4-3 網路圖D之最小擴張樹架構.………………………………………………...40
圖5-1 網路圖E………………….…………....………………………………...…....46
圖5-2 加入虛構路徑之網路圖E.………………………………………………...…47
表目錄
表3-1 圖3-1的入映矩陣A……………………………………………………..……19
表3-2 流向表Q………………..…………………………………………………..…19
表3-3 梯式流向表 …………………………………………………………………20
表3-4 梯式流向表S………………………………………………………….………21
表3-5 標準切集矩陣型態…………………………………………………………...22
表3-6 圖3-3之入映矩陣A……………………………………………………..……25
表3-7 加入虛構路徑之入映矩陣 ………………………………………………..25
表3-8 圖3-4之流向表Q…...………………………………………………………..26
表3-9 圖3-4之梯式流向表 ….…………………………………………………….27
表3-10 網路圖C之入映矩陣A.…………………………………………………….28
表3-11 圖3-6之入映矩陣 ………………………………………………………..29
表3-12 圖3-6之流向表Q……………………………………………………………30
表3-13 圖3-6之梯式流向表 ..……………………………………………………..30
表3-14 圖3-6之梯式流向表S………………………………………………………31
表4-1 倉庫間的運送計畫表………………………………………………………...36
表4-2 網路圖D之入映矩陣A……………………….……………………………...37
表4-3 圖4-2之入映矩陣 ……….………………………………………………...37
表4-4 圖4-2之流向表Q…..………………………………………………………....38
表4-5 圖4-2之梯式流向表 ……...………………………………………………...39
表4-6 圖4-2之梯式流向表S……...………………………………………………...39
表4-7 圖4-2之矩陣T……...………………………………………………………...40
表4-8 圖4-2之流向表P……………...……………………………………………...41
表4-9 線性相加後所形成的路徑……...…………………………….……………...41
表5-1 運輸時間限制下之入映矩陣 ……...…………………………….………..48
表5-2 運輸時間限制下之最小擴張樹型態……...……………………………..…..48
表5-3 運輸時間限制參數下所形成的路徑……...………………………………....49
表5-4 運送時間限制下所形成的路徑說明與其運送時間……...…………………49
表5-5 運輸成本限制參數下的入映矩陣A……...………………………………....50
表5-6 運輸成本限制參數下所形成的路徑……...………………………………....51
表5-7 運送成本限制下所形成的路徑說明與其運送成本……...………………....51
表5-8 符合運送時間限制的路徑在成本與距離之說明……...…………………....52
表5-9 符合運送成本限制的路徑在時間與距離之說明……...…………………....52

參考文獻
[1] Bellman R., “On a routing problem,” Quarterly of Applied Mathematics, Vol. 16, pp. 87-90, 1958.
[2] Berge C., and A. Ghouila-Houri, Programming and Transportation Networks, N.Y. : Wiley, 1962.
[3] Chua L. C., and P. M. Lin, Computer Aided Analysis of Electronic Circuit, Prentice Hall, 1975.
[4] Dial R., “Shortest path forest with topological ordering,” Communication of ACM, Vol. 12, pp. 632-633, 1969.
[5] Dial R., F. Glover, D. Karney, and D. Klingman, “A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees,” Networks, Vol. 9, pp. 215-248, 1979.
[6] Dijkstra E., “A note on two problems in connection with graphs,” Numeriche Mathematics, Vol. 1, pp. 269-271, 1959.
[7] Divoky J. J. and M. S. Hung, “Performance of shortest path algorithms in network flow problems,” Management Science, Vol. 36, pp. 661-673, 1990.
[8] Ford L. R., and D. R. Fulkerson, “Solving the transportation problem,” Management Science, Vol. 3, pp. 24-32, 1956.
[9] Gallo G., and S. Pallottino, Shortest path methods in transportation planning models, In Transportation Planning Models, 1984.
[10] Gallo G., and S. Pallottino, In Fortran Codes for Network Optimization, “Shortest path algorithms,” Annals of Operations Research, Vol. 13, pp. 3-79, 1988.
[11] Hung M. S. and J. J. Divoky, “A computational study of efficient shortest path algorithms,” Computers and Operations Research, Vol. 15, pp. 567-576, 1988.
[12] Juang J. Y., “Identifying Topological Structure of a Large Scale Dynamic Network System,” Proc. International Conference on Advanced Automation, pp. 398-402, 1983.
[13] Juang J. Y., “Identifying Minimum Span of a Network by Flow Table,” Proc. International Conference on Advanced Automation, pp. 1130-1134, 1984.
[14] Katta G. Murty, Network Programming, Englewood Cliffs, N. J. : Prentice Hall, 1992.
[15] Kruskal J. B., “On the shortest spanning tree of graph and the traveling salesman problem ,” Proc. of the American Mathematical Society, Vol. 7, pp. 48-50, 1956.
[16] Prim R. C., “Shortest connection networks and some generalization,” Bell System Technical Journal, Vol. 36, pp. 1389-1401, 1957.
[17] 賴嘉旭，“多重限制條件下最短路徑問題之研究”，私立淡江大學管理科學研究所碩士論文，中華民國八十一年。
[18] 陳慧琪，“時間相依最短路徑問題演算方法之研究”，國立交通大學運輸工程與管理系碩士論文，中華民國八十八年。