臺灣博碩士論文加值系統

本文探討一個組合最佳化問題：瓶頸選擇內部節點最小問題（Bottleneck Selected-Internal Minimum Spanning Tree Problem，BSIMSTP）。給定一個無向完全圖G=(V,E)，一個非負數的權重函數在邊上及一個節點的集合RV，選擇內部節點生成樹為一棵生成樹連通V內的所有節點，但是在R內的節點不能是樹葉（|V\R|2）。瓶頸選擇內部節點最小生成樹問題定義為找出一棵選擇內部節點最小生成樹使得樹上最大邊的權重要最小。此問題可應用在通訊網路設計、交通運輸網。本研究證明瓶頸選擇內部節點最小問題為NP-Complete，同時設計一個基因演算法與一個啟發式演算法來解決問題並比較此兩個演算法的時間效能分析及找出的解與最佳解間的關係。

摘要 i
Abstract ii
目次 iii
圖目次 iv
表目次 v
1.緒論 1
1.1研究背景與動機 1
1.2問題描述 4
1.3研究目的與應用 7
1.4論文架構 8
2.文獻探討 9
2.1旅行推銷員問題 9
2.2瓶頸旅行推銷員問題 11
2.3最小生成樹問題 13
2.4選擇內部節點最小生成樹問題 15
2.5基因演算法 17
3.研究方法與步驟 20
3.1 NP-Complete證明 20
3.2研究方法 24
3.3演算法步驟與流程圖 31
4.實驗結果與分析 36
4.1節點數為6和7的比較 37
4.2節點數為30的比較 41
4.3 TSP資料庫輸入比較 42
5.結論與未來研究方向 44
參考文獻 45

[1] M. Charikar, J. Naor, and B. Schieber, Resource optimization in QoS multicast routing of real-time multimedia, IEEE/ACM Transactions Networking, Vol. 12, pp. 340–348, 2004.
[2] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
[3] X. Cheng and D.Z. Du, Steiner Tree in Industry, Kluwer Academic Publishers, Dordrecht, Netherlands, 2001.
[4] C. Chiang, M. Sarrafzadeh, and C.K. Wong, Global router based on Steiner min-max trees, IEEE Transaction on Computer-Aided Design, Vol. 9, pp. 1318–1325, 1990.
[5] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithm, 2nd edition, MIT Press, Cambridge, 2001.
[6] M.S. Daskin, Network and Discrete Location: Models Algorithms and Applications, Wiley, New York, 1995.
[7] D.Z. Du, J.M. Smith and J.H. Rubinstein, Advances in Steiner tree, Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.
[8] D.Z. Du and X. Hu, Steiner Tree Problems in Computer Communication Networks, World Scientific Publishing Company, 2008.
[9] C.W. Duin and A. Volgenant, The partial sum criterion for Steiner trees in graphs and shortest paths, European Journal of Operations Research, Vol. 97, pp. 172–182, 1997.
[10] M.R. Garey, R.L. Graham, and D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM Journal of Applied Mathematics, Vol. 32, pp. 835–859, 1997.
[11] R.S. Garfinkel and K.C. Gilbert, The bottleneck travelling salesman problem Algorithms and probabilistic analysis, Journal of the ACM, Vol. 25, pp. 435–448, 1978.
[12] S.L. Hakimi, Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, Vol. 12, pp. 450–459, 1964.
[13] S.L. Hakimi, Steiner’s problem in graphs and its implications, Networks, Vol. 1, pp. 113-133, 1971.
[14] D.S. Hochbaum and D.B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM, Vol. 33, pp. 533–550, 1986.
[15] D.S. Hochbaum and A. Pathria, Generalized p-center problems: complexity results and approximation algorithms, European Journal of Operational Research, Vol. 100, pp. 594–607, 1997.
[16] J.H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, The University of Michigan Press, 1975.
[17] S.Y. Hsieh and S.C. Yang, Approximating the selected-internal Steiner tree, Theoretical Computer Science, Vol. 381, pp. 288–291, 2007.
[18] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem, Annuals of Discrete Mathematics, Vol. 53, Elsevier Science Publishers, Amsterdam, 1992.
[19] X. Li, F. Zou, Y. Huang, D. Kim and W. Wu, A better constant-factor approximation for selected-internal Steiner minimum tree, Algorithmica, Vol. 56, pp. 333–341, 2010.
[20] C.S. Liu, Y.T. Kuo and C.W. Ma, A heuristic algorithm for the selected-internal minimum spanning tree problem. The 29th Workshop on Combinatorial Mathematics and Computational Theory, pp. 267–271, 2012.
[21] R.G. Parker and R.L. Rardin, Guaranteed performance heuristics for the bottleneck traveling salesman problem. Operations Research Letters, Vol. 2, pp. 269–272, 1984.
[22] C.S. ReVelle and H.A. Eiselt, Location analysis: A synthesis and survey, European Journal of Operational Research, Vol. 165, pp. 1–19, 2005.
[23] A. Tamir, Improved complexity bounds for center location problems on networks by using dynamic data structures, SIAM Journal of Discrete Mathematics, Vol. 1, 377–396, 1988.
[24] TSPLIB -A library of sample instances for the TSP. University of Heidelberg: Office Research Group Discrete Optimization, from http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/index.html