趙坤茂臺灣大學:資訊工程學研究所劉效飛Liu, Hsiao-FeiHsiao-FeiLiu2010-06-022018-07-052010-06-022018-07-052008U0001-1706200812460900http://ntur.lib.ntu.edu.tw//handle/246246/184834在這份論文中，我們將探討一系列有關序列分析的計算問題。這些問題依據其性質，可分為以下四類：最佳化、列舉、挑選、排序。其中最佳化、列舉、挑選這三類問題性質較為接近，所以又統稱為搜尋問題。在最佳化問題中，我們的目標是找出最佳解；在列舉問題中，我們希望能將前 k 好的解都列舉出來；在挑選問題中，我們希望能挑選出第 k 好的解；在排序問題中，我們必須重新排序一個序列，使得這個序列滿足給定的限制。本論文中所討論的問題都已知能在多項式時間內解決，所以我們的目標將鎖定在設計能更快找出精確解的演算法。In this dissertation, we study a series of problems on sequences. These problems are broadlyategorized into four types: Optimization, enumeration, selection, and ordering. Problems ofhe first three types are generally called the searching problems. In the optimization problem,e seek for the best feasible solution. In the enumeration problem, we have to enumerate the kest feasible solutions. In the selection problem, we pick out the kth best feasible solution. Inhe ordering problem, we are required to reorder a sequence subject to some constraints. Allroblems considered in this dissertation are already known to be polynomial-time solvable, soe aim at giving efficient exact algorithms for them.1 Introduction 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problem Formulation and Contribution . . . . . . . . . . . . . . . . . . . . . . . 2.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Optimization Problems 9 Disjoint Segments with Maximum Sum of Densities 10.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 The DMDS Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.4 The Main Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.5 The Complete Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Length-Constrained Max-Eccentricity Segments 25.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25.2 Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Sum-Constrained Max-Density Intervals 33.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.2 Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Density Finding 43.1 Reduction to the Slope Finding Problem . . . . . . . . . . . . . . . . . . . . 43.2 The Algorithm for the Slope Finding Problem . . . . . . . . . . . . . . . . . 44I Enumeration Problems 47 Length-Constrained k Max-Sum Segments 48.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48.2 An O(n + k)-Time Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.1 Finding k Length-Constrained Maximum-Density Segments Satisfying aensity Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.2 Finding the Area-Constrained k Max-Sum Subarrays . . . . . . . . . . . 53 Weight-Constrained k Longest Paths 54.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54.2 An O(jV j log jV j + k)-Time Algorithm . . . . . . . . . . . . . . . . . . . . . . . 59.3 An ­(jV j log jV j + k) Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 An Application of Finding the Sum-Constrained k Longest Segments . . . . . . 63II Selection Problems 64 Length-Constrained Sum Selection 65.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65.2 Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66.3 An O(n log(U ¡ L + 1))-Time Algorithm . . . . . . . . . . . . . . . . . . . . . . 67.4 An Lower Bound for Sum Selection . . . . . . . . . . . . . . . . . . . . . . . . . 69V Ordering Problems 71 A Tight Analysis of the Katriel-Bodlaender Algorithm 72.1 The Katriel-Bodlaender Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 An O(m3=2 + mn1=2 log n) Upper Bound . . . . . . . . . . . . . . . . . . . . . . 76.3 An ­(m3=2 + mn1=2 log n) Lower Bound . . . . . . . . . . . . . . . . . . . . . . . 790 An ˜O(n2:5)-Time Algorithm for Online Topological Ordering 820.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840.2.1 Main Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840.2.2 Auxiliary Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . 840.2.3 Instructions for Data Structures . . . . . . . . . . . . . . . . . . . . . . . 850.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860.4 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900.4.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900.4.2 Running Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000.5 Further Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1010.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Ending 1041 Conclusions 1051.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1051.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106application/pdf845620 bytesapplication/pdfen-US序列最佳化列舉挑選排序sequenceoptimizationenumerationselectionorderingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184834/1/ntu-97-F92922019-1.pdf