條件限制下的序列搜尋與排序

Abstract

在這份論文中，我們將探討一系列有關序列分析的計算問題。這些問題依據其性質，可分為以下四類：最佳化、列舉、挑選、排序。其中最佳化、列舉、挑選這三類問題性質較為接近，所以又統稱為搜尋問題。在最佳化問題中，我們的目標是找出最佳解；在列舉問題中，我們希望能將前 k 好的解都列舉出來；在挑選問題中，我們希望能挑選出第 k 好的解；在排序問題中，我們必須重新排序一個序列，使得這個序列滿足給定的限制。本論文中所討論的問題都已知能在多項式時間內解決，所以我們的目標將鎖定在設計能更快找出精確解的演算法。

In this dissertation, we study a series of problems on sequences. These problems are broadly categorized into four types: Optimization, enumeration, selection, and ordering. Problems of the first three types are generally called the searching problems. In the optimization problem, we seek for the best feasible solution. In the enumeration problem, we have to enumerate the k best feasible solutions. In the selection problem, we pick out the kth best feasible solution. In the ordering problem, we are required to reorder a sequence subject to some constraints. All problems considered in this dissertation are already known to be polynomial-time solvable, so we aim at giving efficient exact algorithms for them.