最大密度路徑與最大子陣列問題之演算法設計與分析

Algorithms for finding the maximum-density path and maximum subarray problems

林容任(Rung-Ren Lin)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00343

摘要

在本論文中，我們提出一些演算法來解決兩個問題。第一個問題是在樹中找尋有長度限制且密度最大的路徑。給定一個具有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.

並列關鍵字

path ； tree ； subarray ； maximum-density

參考文獻

[1] A. Arslan, O. Egecioglu, and P. Pevzner, A new approach to sequence comparison: normalized sequence alignment, Bioinformatics, 17:327-337, 2001.

[2] J. Bentley, Programming Pearls - Algorithm Design Techniques, CACM, 865-871, 1984.

[3] K.-M. Chao, On computing all suboptimal alignments, Information Sciences, 105:189-207, 1998.

[4] K.-M. Chao, R.C. Hardison and W. Miller, Recent developments in linear-space alignment methods: a survey, Journal of Computational Biology, 1:271-291, 1994.

[5] K. M. Chung and H.-I. Lu., An Optimal Algorithm for the Maximum-Density Segment Problem, Proceedings of the 11th Annual European Symposium on Algorithms, 136-147, 2003.