組合算法

組合算法(combinatorial algorithm)是組合學的一個研究分支，一些組合問題需用電子計算機解決，當研究如何進行計算時，就需要研究算法，組合算法是一類不同於代數計算的方法，為使這種算法能夠有效地進行，對於每種組合算法，必須研究其組合結構和在此基礎上討論其時間的複雜性和空間的複雜性問題，即對算法所需的時間和存儲單元與輸入數據量的關係作出估計。

基本介紹

• 中文名：組合算法
• 外文名：combinatorial algorithm
• 所屬學科：數學（組合學）
• 簡介：組合學的一個研究分支

基本介紹

組合算法指計算對象是離散的、有限的數學結構的組合學問題的算法。組合算法的用途十分廣泛。從方法學的角度，組合算法包括算法設計和算法分析兩個方面，關於算法設計，已經總結出若干帶有普遍意義的方法和技術，包括動態規劃、回溯法、分枝限界法、分治法、貪心法等。儘管如此，組合算法的設計仍然是一門藝術需要高度的技巧和靈感。算法分析的任務是分析算法的優劣，主要是討論算法的時間複雜性和空間複雜性。它的理論基礎是組合分析，包括計數和枚舉。計算複雜性理論，特別是NP完全性理論，與組合算法是緊密相關的。NP完全性概念的提出，正是為了刻畫包括旅行商問題、圖著色問題、整數規劃等在內的一大批組合問題的計算難度。計算複雜性理論研究算法在時間和空間限制下的能力以及問題的難度，使組合算法的研究有了更加清晰的框架，將組合算法的研究提高到一個新水平。

相關算法介紹

單純形法

單純形法是G.B.Dantzig在1947年提出的一種線性規划算法，他本人以及其他學者後來又提出多種形式的變形和改進。實踐表明，單純形法及其變形和改進是非常行之有效的，在市場上已經形成許多可以有效解央大型線性規劃問題的軟體包。線性規劃研究線性目標函式在一組線性等式與線性不等式約束下的極值問題。這本來是連續問題，Dantzig發現線性規劃問題的可行解集(即滿足約束條件的點的全體)是一個超多面體。 如果它的最優解存在，那么最優解一定可以在這個超多面體的某個頂點取到。由於超多面體的頂點只有有限個，從而使線性規劃成為一個組合最佳化問題。單純形法是按照一定的規劃，從可行解集的一個頂點轉移到另一個頂點，使得目標函式的值不斷地得到改進，最後達到最優。儘管單純形法一直使用得很好，但在最壞情況下它需要指數運行時間，從而使線性規劃問題是否屬於P類一度成為人們關心的問題。1979年前一位蘇聯數學家提出一個多項式時間的線性規划算法——橢球算法， 從而解決了這個問題。1984年印度數學家N.Karmarkar又提出一個新的更好的多項式時間算法——投影算法。

排序和檢索

將給定的元素序列按照某種順序關係重新排列成有序序列稱作排序。例如將n個數組成的序列按照從小到大的順序重新排列；將n個英語單詞組成的序列按照字典順序重新排列。在給定的集合中查找某個特定的元素稱作檢索。例如從給定的n個數中找到最大的數。排序和檢索算法已經成為數據結構中不可缺少的部分，是計算機科學技術中最基本、使用最頻繁的算法。正因為如此，它們也是研究得最細緻的一類組合算法(參見排序算法)。

圖與網路最佳化算法

圖與網路最佳化算法是組合算法中內容最豐富的部分。圖論中的計算問題包括圖的搜尋路徑問題、連通性問題可平面性檢驗、著色問題、網路最佳化等。圖論中的著名算法有求最小生成樹的Kruskal算法、求最短路的Dijkstra算法和Floyd算法、求二部圖最大匹配(指派問題)的匈牙利算法、求一般圖最大匹配的Edmonds"花”算法、求網路最大流和最小割的標號法等。

貪心法與擬陣

貪心法是求解關於獨立系統組合最佳化問題的一種簡單算法，求最小生成樹的Kruskal算法就是一種貪心法。但是，貪心法並不總能找到最優獨立集，貪心法能求得最優獨立集的充分必要條件是L為一個擬陣。事實上，求最大生成樹是關於擬陣的組合最佳化問題，而二部圖的所有匹配構成的獨立系統U不是擬陣。

窮舉搜尋

組合算法要解決的問題只有有限種可能，在沒有更好辦法時總可以用窮舉搜尋的辦法來解決，即逐個檢查所有可能的情況。當情況較多時這樣做是很費時的。實際上，並不需要機械地檢查每一種情況，常常有可能提前判斷出某些情況不可能取到最優解，從而可以提前捨棄這些情況。這樣使“隱含地”檢查了所有情況，既減少了搜尋量，又保證不漏掉最優解。參見回溯法。

分支限界法

分支限界法是一種用於求解組合最佳化問題的排除非解的搜尋方法。它的基本思想是：把問題分成若干個子問題，估計子問題的目標函式值的上界或下界。對於最大值問題，子問題的下界也是原問題的下界。 當子問題的上界小於原問題的下界時，不可能在這個子問題中取得原問題的最優解，捨去這個子問題。否則將這個子問題再劃分成若干更小的子問題，重複上述過程，直到沒有需要檢查的子問題為止。

其他組合算法還有動態規劃，快速傳里葉變換等。