組合算法概論(A Brief IntrodUCtion to Combinatorial Algorithm)
    組合算法是算法分析學(xué)當(dāng)中非常重要的一個(gè)分支，關(guān)于它在計(jì)算機(jī)科學(xué)的地位我就不敖述了，下面為大家整理了整個(gè)材料，算法是我收集的，只是分門別類簡(jiǎn)單介紹一下，然后把我的材料做了個(gè)整理，大家收藏吧，感覺挺有用的，費(fèi)了我好長(zhǎng)時(shí)間和精力呀，我現(xiàn)在預(yù)備考研了，沒有太多時(shí)間發(fā)很多經(jīng)典文章了，這片算是大部頭了。
    關(guān)于組合學(xué)問題的算法，計(jì)算對(duì)象是離散的、有限的數(shù)學(xué)結(jié)構(gòu)。從方法學(xué)的角度，組合算法包括算法設(shè)計(jì)和算法分析兩個(gè)方面。關(guān)于算法設(shè)計(jì)，歷史上已經(jīng)總結(jié)出了若干帶有普遍意義的方法和技術(shù)，包括動(dòng)態(tài)規(guī)劃、回溯法、分支限界法、分治法、貪心法等。下面我們著重談?wù)剮讉€(gè)有代表性的組合算法：
單純形法：
    這是一種線性規(guī)劃算法，由G.B.Dantzig在1947年提出，后來由他和其他的學(xué)者又提出了單純形法的變形和改進(jìn)。這些被實(shí)踐證實(shí)都是行之有效的，線性規(guī)劃研究線性目標(biāo)函數(shù)在一組線性等式與線性不等式約束下的極值問題。這本來是連續(xù)問題，Dantzig發(fā)現(xiàn)線性規(guī)劃問題的可行解集（即滿足約束條件的點(diǎn)的全體）是一個(gè)超多面體。假如它的最優(yōu)解存在，那么這個(gè)最優(yōu)解一定可以在超多面體的一個(gè)頂點(diǎn)取到。由于超多面體的頂點(diǎn)只有有限個(gè)，從而使線性規(guī)劃成為一個(gè)組和優(yōu)化問題。單純形法是按照一定的規(guī)則，從可行解集的一個(gè)頂點(diǎn)轉(zhuǎn)移到另一個(gè)頂點(diǎn)，使得目標(biāo)函數(shù)的值不斷地得到改進(jìn)，最后達(dá)到最優(yōu)。盡管單純形法一直使用得很好，但是在最壞情況下它需要指數(shù)運(yùn)行時(shí)間，從而使線性規(guī)劃問題是否屬于P類一度成為人們關(guān)心的問題。后來的橢球算法和投影算法都很好的解決了這個(gè)問題。
排序和檢索：
    這兩部分應(yīng)當(dāng)是大家比較熟悉的，所謂排序，就是將給定的元素序列按照某種順序關(guān)系重新排列成有序序列。例如將n個(gè)數(shù)組成的序列按照從小到大的順序重新排列；將n個(gè)英語單詞組成的的序列按照字典順序重新排列。所謂檢索，就是在給定的集合中查找某個(gè)特定的元素或是元素組。排序和檢索已經(jīng)成為計(jì)算機(jī)科學(xué)技術(shù)中最基本、使用最頻繁的算法。下面我們專門談?wù)勁判蛩惴ǎ╯orting algorithm）。
    在討論此種算法時(shí)，數(shù)據(jù)通常是指由若干記錄組成的文件，每個(gè)記錄包含一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)，其中能夠標(biāo)志該記錄的數(shù)據(jù)項(xiàng)稱為鍵碼。給定一文件的n個(gè)記錄{R1,R2,…,Rn}及其相應(yīng)的鍵碼的集合{K1,K2,…,Kn}。所謂排序算法就是在數(shù)據(jù)處理中將文件中的記錄按鍵碼的一定次序要求排列起來的算法。若待排序的文件能夠同時(shí)裝入計(jì)算機(jī)的主存中，整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，有一部分必須放在外存上，則稱此類排序問題為外部排序。當(dāng)待排序的文件中包含有一些相同鍵碼的記錄時(shí)，假如經(jīng)過排序后這些相同的鍵碼的記錄的相對(duì)次序仍然保持不變，則相應(yīng)的排序算法是穩(wěn)定的，否則為不穩(wěn)定的。假如排序算法設(shè)計(jì)成單處理機(jī)完成的，則此排序算法稱為串行（或順序）排序算法；假如排序算法時(shí)設(shè)計(jì)成多處理機(jī)實(shí)現(xiàn)的，則稱為并行排序算法。
    首先談?wù)?STRONG>內(nèi)部排序：內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過程。在排序的過程中，參與排序的記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無序區(qū)。
使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為一趟排序。
    逐步擴(kuò)大記錄有序序列長(zhǎng)度的方法大致有下列幾類：
一．插入排序
    假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：
則一趟直接插入排序的基本思想為：將記錄R
插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]。
    顯然，完成這個(gè)“插入”需分三步進(jìn)行：
1．查找R的插入位置j+1；
2．將R[j+1..i-1]中的記錄后移一個(gè)位置；
3．將R復(fù)制到R[j+1]的位置上。
[I]直接插入排序
    利用順序查找實(shí)現(xiàn)“在R[1..i-1]中查找R的插入位置”的插入排序。
    注重直接插入排序算法的三個(gè)要點(diǎn)：
1．從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；
  R[0] = R;    // 設(shè)置“哨兵”
  for (j=i-1; R[0].key<R[j].key; --j); // 從后往前找
  return j+1;     // 返回R的插入位置為j+1
2．對(duì)于在查找過程中找到的那些要害字不小于R.key的記錄，可以在查找的同時(shí)實(shí)現(xiàn)向后移動(dòng)；
  for (j=i-1; R[0].key<R[j].key; --j);  
  R[j+1] = R[j]
3．i = 2，3，…, n, 實(shí)現(xiàn)整個(gè)序列的排序。
  template<class Elem>
  void InsertionSort ( Elem R[],  int n)
  {
      // 對(duì)記錄序列R[1..n]作直接插入排序。
      for ( i=2; i<=n; ++i )
      {
          R[0] = R;            // 復(fù)制為監(jiān)視哨