趙坤茂臺灣大學：資訊工程學研究所林容任Lin, Rung-RenRung-RenLin2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/54008在本論文中，我們提出一些演算法來解決兩個問題。第一個問題是在樹中找尋有長度限制且密度最大的路徑。給定一個具有n個邊的樹，我們提出了兩個O(nL)的演算法找出長度至少為L的最大密度路徑。其中一個演算法甚至可以在O(n)的時間找出完整m元樹的解。另一個問題是在二維陣列中找尋具有最大和的子陣列。給定m乘n的陣列，我們提出兩個啟發式的演算法來計算最大子陣列，其時間複雜度為O(nm+km^2)，在此k為一給定的參數值。根據實驗數據顯示，它們有相當的可能性可找到二維陣列裡的最大子陣列。We propose some algorithms to solve two problems in this thesis. The first problem is to find a length-constrained maximum-density path in a tree. Given a tree with n edges, we present two efficient algorithm for finding a maximum-density path of length at least L in O(nL) time. One of them is further modified to solve full m-ary trees in O(n) time. The other problem is to find the maximum subarray in a two-dimensional array. Given an m×n array of numbers, we develop two heuristic algorithms for computing the maximum subarray in O(nm + km^2), where k is a given parameter. Preliminary experiments show that these approaches are very promising for locating the maximum subarray in a given two-dimensional array.Chapter 1 Introduction.....1 1.1 Motivation.....1 1.2 Organization.....2 Chapter 2 Finding a Length-Constrained Maximum-Density Path in a Tree.....3 2.1 Introduction of the Maximum-Density Path Problem.....3 2.2 Finding a Maximum-Density Path from its End Node.....4 2.3 Finding a Maximum-Density Path from its LCA Node.....7 2.4 A Special Case.....14 Chapter 3 Efficient Heuristic Algorithms for the Maximum Subarray Problem.....16 3.1 Introduction of the Maximum Subarray Problem.....16 3.2 Preliminaries.....17 3.3 Heuristic Methods.....18 Chapter 4 Conclusion and Future Work.....24 4.1 Conclusion.....24 4.2 Future Work.....24 Bibliography.....25278348 bytesapplication/pdfen-US路徑樹子陣列最大密度pathtreesubarraymaximum-densitythesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54008/1/ntu-93-R91922054-1.pdf