|
組合算法概論(A Brief Introduction to Combinatorial Algorithm) 組合算法是算法分析學(xué)當(dāng)中非常重要的一個(gè)分支，關(guān)于它在計(jì)算機(jī)科學(xué)的地位我就不敖述了，下面為大家整理了整個(gè)材料，算法是我收集的，只是分門別類簡單介紹一下，然后把我的材料做了個(gè)整理，大家收藏吧，感覺挺有用的，費(fèi)了我好長時(shí)間和精力呀，我現(xiàn)在準(zhǔn)備考研了，沒有太多時(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í)踐證明都是行之有效的，線性規(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ù)剝?nèi)部排序：內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。在排序的過程中，參與排序的記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無序區(qū)。 使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為一趟排序。 逐步擴(kuò)大記錄有序序列長度的方法大致有下列幾類： 一．插入排序 假設(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ì)于在查找過程中找到的那些關(guān)鍵字不小于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)視哨 for ( j=i-1; R[0].key < R[j].key; --j ) R[j+1] = R[j]; // 記錄后移 R[j+1] = R[0]; // 插入到正確位置 } } // InsertSort 時(shí)間分析： 實(shí)現(xiàn)排序的基本操作有兩個(gè)： （1）“比較”序列中兩個(gè)關(guān)鍵字的大??； （2）“移動(dòng)”記錄。 對(duì)于直接插入排序： [II]折半插入排序 因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉Ｆ渌惴ㄈ缦拢?nbsp; template<class Elem> void BiInsertionSort (Elem R[]， int n) { // 對(duì)記錄序列R[1..n]作折半插入排序。 for ( i=2; i<=L.length; ++i ) { R[0] = R; // 將R暫存到R[0] low = 1; high = i-1; while (low<=high) { //在R[low..high]中折半查找插入的位置 m = (low+high)/2; // 折半 if (R[0].key < R[m].key)) high = m-1; // 插入點(diǎn)在低半?yún)^(qū) else low = m+1; // 插入點(diǎn)在高半?yún)^(qū) } for ( j=i-1; j>=high+1; --j ) R[j+1] = R[j]; // 記錄后移 R[high+1] = R[0]; // 插入 } } // BInsertSort 折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動(dòng)”的次數(shù)不變。 [III]表插入排序 為了減少在排序過程中進(jìn)行的“移動(dòng)”記錄的操作，必須改變排序過程中采用的存儲(chǔ)結(jié)構(gòu)。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。 算法描述如下： template<class Elem> void LInsertionSort (Elem SL[]， int n) { // 對(duì)記錄序列SL[1..n]作表插入排序。 SL[0].key = MAXINT ; SL[0].next = 1; SL[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL[0].next; SL[k].key <= SL.key ; j = k, k = SL[k].next ) { SL[j].next = i; SL.next = k; } // 結(jié)點(diǎn)i插入在結(jié)點(diǎn)j和結(jié)點(diǎn)k之間 }// LinsertionSort 關(guān)于如在排序之后調(diào)整記錄序列： 算法中使用了三個(gè)指針: 其中：p指示第i個(gè)記錄的當(dāng)前位置； i指示第i個(gè)記錄應(yīng)在的位置； q指示第i+1個(gè)記錄的當(dāng)前位置 template<class Elem> void Arrange ( SLinkListType SL[ ], int n ) { // 根據(jù)靜態(tài)鏈表SL中各結(jié)點(diǎn)的指針值調(diào)整 // 記錄位置，使得SL中記錄按關(guān)鍵字非遞減 // 有序順序排列 p = SL[0].next;// p指示第一個(gè)記錄的當(dāng)前位置 for ( i=1; i<n; ++i ) { // SL[1..i-1]中記錄已按關(guān)鍵字有序排列， // 第i個(gè)記錄在SL中的當(dāng)前位置應(yīng)不小于i while (p<i) p = SL[p].next; // 找到第i個(gè)記錄，并用p指示 // 其在SL中當(dāng)前位置 q = SL[p].next; // q指示尚未調(diào)整的表尾 if ( p!= i ) { SL[p]←→SL; // 交換記錄，使第i個(gè) // 記錄到位 SL.next = p; // 指向被移走的記錄， // 使得以后可由while循環(huán)找回 } p = q; // p指示尚未調(diào)整的表尾， // 為找第i+1個(gè)記錄作準(zhǔn)備 } } // Arrange 二． 交換排序 通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度; [I]起泡排序 假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：n-i+1 則第i趟起泡插入排序的基本思想為：借助對(duì)無序序列中的記錄進(jìn)行“交換”的操作，將無序序列中關(guān)鍵字最大的記錄“交換”到R[n-i+1]的位置上。 算法描述： template <class Elem> void BubbleSort(Elem R[], int n) { // i 指示無序序列中最后一個(gè)記錄的位置 i = n; while (i > 1) { lastExchangeIndex = 1; for (j = 1; j < i; j++) { if (A[j+1] < A[j]) { Swap(A[j],A[j+1]); lastExchangeIndex = j; } //if } // for i = lastExchangeIndex; } // while } // BubbleSort 起泡排序的結(jié)束條件為：最后一趟沒有進(jìn)行“交換”。 從起泡排序的過程可見，起泡排序是一個(gè)增加有序序列長度的過程，也是一個(gè)縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。我們可以設(shè)想，若能在經(jīng)過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 20:07:19 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊(cè)：2003-8-28 第 2 樓 [II]一趟快速排序 目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t],且R[j].key≤ R.key ≤ R[j].key (s≤j≤i-1) 樞軸 (i+1≤j≤t) 例如:關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 其中(52)為樞軸，在調(diào)整過程中，需設(shè)立兩個(gè)指針:low和high，它們的初值分別為:s和t, 之后逐漸減小high，增加low，并保證R[high].key≥52，而R[low].key≤52,否則進(jìn)行記錄的“交換”。 算法描述如下: template<class Elem> int Partition (Elem R[], int low, int high) { // 交換記錄子序列R[low..high]中的記錄，使 // 樞軸記錄到位，并返回其所在位置，此時(shí)， // 在它之前（后）的記錄均不大（?。┯谒?nbsp; pivotkey = R[low].key; // 用子表的第一個(gè)記錄作樞軸記錄 while (low<high) { // 從表的兩端交替地向中間掃描 while (low<high && R[high].key>=pivotkey) --high; R[low]←→R[high]; // 將比樞軸記錄小的記錄交換到低端 while (low<high && R[low].key<=pivotkey) ++low; R[low]←→R[high]; // 將比樞軸記錄大的記錄交換到高端 } return low; // 返回樞軸所在位置 } // Partition 容易看出，調(diào)整過程中的樞軸位置并不重要，因此，為了減少記錄的移動(dòng)次數(shù)，應(yīng)先將樞軸記錄“移出”，待求得樞軸記錄應(yīng)在的位置之后(此時(shí)low=high),再將樞軸記錄到位。 將上述“一次劃分”的算法改寫如下： template<class Elem> int Partition (Elem R[], int low, int high) { // 交換記錄子序列R[low..high]中的記錄，使 //樞軸記錄到位，并返回其所在位置，此時(shí)， // 在它之前（后）的記錄均不大（小）于它 R[0] = R[low]; // 用子表的第一個(gè)記錄作樞軸記錄 pivotkey = R[low].key; // 樞軸記錄關(guān)鍵字 while (low < high) { // 從表的兩端交替地向中間掃描 while(low=pivotkey) --high; R[low] = R[high]; // 將比樞軸記錄小的記錄移到低端 while (low<high && R[low].key<=pivotkey) ++low; R[high] = R[low]; // 將比樞軸記錄大的記錄移到高端 } R[low] = R[0]; // 樞軸記錄到位 return low; // 返回樞軸位置 } // Partition [III]快速排序 在對(duì)無序序列中記錄進(jìn)行了一次分割之后，分別對(duì)分割所得兩個(gè)子序列進(jìn)行快速排序，依次類推，直至每個(gè)子序列中只含一個(gè)記錄為止。 快速排序的算法描述如下: template<class Elem> void QSort (Elem R[], int low, int high) { // 對(duì)記錄序列R[low..high]進(jìn)行快速排序 if (low < high-1) { // 長度大于1 pivotloc = Partition(L, low, high); // 將L.r[low..high]一分為二 QSort(L, low, pivotloc-1); // 對(duì)低子表遞歸排序，pivotloc是樞軸位置 QSort(L, pivotloc+1, high); // 對(duì)高子表遞歸排序 } } // QSort template<class Elem> void QuickSort(Elem R[], int n) { // 對(duì)記錄序列進(jìn)行快速排序 QSort(R, 1, n); } // QuickSort 快速排序的時(shí)間分析 假設(shè)一次劃分所得樞軸位置i=k，則對(duì)n個(gè)記錄進(jìn)行快排所需時(shí)間 T(n) = Tpass(n)+T(k-1)+T(n-k) 其中 Tpass(n)為對(duì)n個(gè)記錄進(jìn)行一次劃分所需時(shí)間，若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則k取1至n中任意一值的可能性相同，由此可得快速排序所需時(shí)間的平均值為： 設(shè) Tavg(1)≤b 則可得結(jié)果 通常，快速排序被認(rèn)為是在所有同數(shù)量級(jí)O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，需在進(jìn)行快排之前，進(jìn)行“予處理”，即：比較 R(s).key, R(t).key和R[(s+t)/2.key，然后取關(guān)鍵字為“三者之中”的記錄為樞軸記錄。 三． 選擇排序 從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度; [I]簡單選擇排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為： 并且有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字，則第i趟簡單選擇排序是，從無序序列R[i..n]的n-i+1記錄中選出關(guān)鍵字最小的記錄加入有序序列。 簡單選擇排序的算法描述如下： template void SelectSort (Elem R[], int n ) { // 對(duì)記錄序列R[1..n]作簡單選擇排序。 for (i=1; i // 選擇第i小的記錄，并交換到位 j = SelectMinKey(R, i); // 在R[i..n]中選擇key最小的記錄 if (i!=j) R←→R[j]; // 與第i個(gè)記錄交換 } } // SelectSort 時(shí)間性能分析 對(duì)n個(gè)記錄進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)總計(jì)為 移動(dòng)記錄的次數(shù)，最小值為0, 最大值為3(n-1) [II]堆排序 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 20:07:36 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊(cè)：2003-8-28 第 3 樓 堆排序也是選擇排序的一種，其特點(diǎn)是，在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果。 堆的定義: 堆是滿足下列性質(zhì)的數(shù)列{r1, r2, …，rn}： 或 若將此數(shù)列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當(dāng)左/右子樹不空時(shí)，根結(jié)點(diǎn)的值小于(或大于)左/右子樹根結(jié)點(diǎn)的值。 由此，若上述數(shù)列是堆，則r1必是數(shù)列中的最小值或最大值，分別稱作小頂堆或大頂堆。 堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。具體作法是：先建一個(gè)“大頂堆”，即先選得一個(gè)關(guān)鍵字為最大的記錄，然后與序列中最后一個(gè)記錄交換，之后繼續(xù)對(duì)序列中前n-1記錄進(jìn)行“篩選”，重新將它調(diào)整為一個(gè)“大頂堆”，再將堆頂記錄和第n-1個(gè)記錄交換，如此反復(fù)直至排序結(jié)束。 所謂“篩選”指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹為堆。 堆排序的算法如下所示： template void HeapSort ( Elem R[], int n ) { // 對(duì)記錄序列R[1..n]進(jìn)行堆排序。 for ( i=n/2; i>0; --i ) // 把R[1..n]建成大頂堆 HeapAdjust ( R, i, n ); for ( i=n; i>1; --i ) { R[1]←→R; // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 // R[1..i]中最后一個(gè)記錄相互交換 HeapAdjust(R, 1, i-1); // 將R[1..i-1] 重新調(diào)整為大頂堆 } } // HeapSort 其中篩選的算法如下所示。為將R[s..m]調(diào)整為“大頂堆”，算法中“篩選”應(yīng)沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下進(jìn)行。 Template void HeapAdjust (Elem R[], int s, int m) { // 已知R[s..m]中記錄的關(guān)鍵字除R[s].key之 // 外均滿足堆的定義，本函數(shù)調(diào)整R[s] 的關(guān) // 鍵字，使R[s..m]成為一個(gè)大頂堆（對(duì)其中 // 記錄的關(guān)鍵字而言） rc = R[s]; for ( j=2*s; j<=m; j*=2 ) {// 沿key較大的孩子結(jié)點(diǎn)向下篩選 if ( j if ( rc.key >= R[j].key ) break; // rc應(yīng)插入在位置s上 R[s] = R[j]; s = j; } R[s] = rc; // 插入 } // HeapAdjust 堆排序的時(shí)間復(fù)雜度分析： 1. 對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1); 2．對(duì)n個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為4n; 3. 調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過 2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n) 因此，堆排序的時(shí)間復(fù)雜度為O(nlogn) 四．歸并排序：是通過“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長度;歸并排序的基本思想是：將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。 在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的有序子序列 歸并為一個(gè)有序序列。 “歸并”算法描述如下： template void Merge (Elem SR[], Elem TR[], int i, int m, int n) { // 將有序的SR[i..m]和SR[m+1..n]歸并為 // 有序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { // 將SR中記錄由小到大地并入TR if (SR.key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i<=m) TR[k..n] = SR[i..m]; // 將剩余的SR[i..m]復(fù)制到TR if (j<=n) TR[k..n] = SR[j..n]; // 將剩余的SR[j..n]復(fù)制到TR } // Merge 歸并排序的算法可以有兩種形式：遞歸的和遞推的，它是由兩種不同的程序設(shè)計(jì)思想得出的。在此，只討論遞歸形式的算法。 這是一種自頂向下的分析方法： 如果記錄無序序列R[s..t]的兩部分R[s..(s+t)/2]和R[(s+t)/2+1..t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列，由此，應(yīng)該先分別對(duì)這兩部分進(jìn)行2-路歸并排序。 template void Msort ( Elem SR[], Elem TR1[], int s, int t ) { // 將SR[s..t]進(jìn)行2-路歸并排序?yàn)門R1[s..t]。 if (s==t) TR1[s] = SR[s]; else { m = (s+t)/2; // 將SR[s..t]平分為SR[s..m]和SR[m+1..t] Msort (SR, TR2, s, m); // 遞歸地將SR[s..m]歸并為有序的TR2[s..m] Msort (SR, TR2, m+1, t); //遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t] Merge (TR2, TR1, s, m, t); // 將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t] } } // MSort template void MergeSort (Elem R[]) { // 對(duì)記錄序列R[1..n]作2-路歸并排序。 MSort(R, R, 1, n); } // MergeSort 容易看出，對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需進(jìn)行l(wèi)ogn趟。 五．基數(shù)排序：借助“多關(guān)鍵字排序”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序”的算法。 [I]多關(guān)鍵字的排序 假設(shè)有n個(gè)記錄……的序列 { R1, R2, …，Rn} 每個(gè)記錄Ri中含有d個(gè)關(guān)鍵字(Ki0, Ki1, …,Kid-1),則稱上述記錄序列對(duì)關(guān)鍵字(Ki0, Ki1, …,Kid-1)有序是指：對(duì)于序列中任意兩個(gè)記錄Ri和Rj(1≤i (Ki0, Ki1, …,Kid-1)< (Kj0, Kj1, …,Kjd-1) 其中K0被稱為“最主”位關(guān)鍵字，Kd-1被稱為 “最次”位關(guān)鍵字。 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法: 最高位優(yōu)先MSD法：先對(duì)K0進(jìn)行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對(duì)K1進(jìn)行排序，…，依次類推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。 最低位優(yōu)先LSD法：先對(duì)Kd-1進(jìn)行排序，然后對(duì)Kd-2進(jìn)行排序，依次類推，直至對(duì)最主位關(guān)鍵字K0排序完成為止。排序過程中不需要根據(jù)“前一個(gè)”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(gè)(“前一個(gè)”關(guān)鍵字不同的)子序列。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 20:07:55 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊(cè)：2003-8-28 第 4 樓 例如:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。LSD的排序過程如下: [II]鏈?zhǔn)交鶖?shù)排序 假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。 對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。 例如：對(duì)下列這組關(guān)鍵字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其“個(gè)位數(shù)”取值分別為0, 1, …，9“分配”成10組，之后按從0至9的順序?qū)⑺鼈?#8220;收集”在一起;然后按其“十位數(shù)” 取值分別為0, 1, …，9“分配”成10組，之后再按從0至9的順序?qū)⑺鼈?#8220;收集”在一起;最后按其“百位數(shù)”重復(fù)一遍上述操作，便可得到這組關(guān)鍵字的有序序列。 在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： １． 待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表； ２．“分配”時(shí)，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊(duì)列”中，每個(gè)隊(duì)列中記錄的“關(guān)鍵字位”相同； ３．“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表; ４．對(duì)每個(gè)關(guān)鍵字位均重復(fù)2)和3)兩步。 例如： p→369→367→167→239→237→138→230→139 第一次分配得到 f[0]→230←r[0] f[7]→367→167→237←r[7] f[8]→138←r[8] f[9]→369→239→139←r[9] 第一次收集得到 p→230→367→167→237→138→368→239→139 第二次分配得到 f[3]→230→237→138→239→139←r[3] f[6]→367→167→368←r[6] 第二次收集得到 p→230→237→138→239→139→367→167→368 第三次分配得到 f[1]→138→139→167←r[1] f[2]→230→237→239←r[2] f[3]→367→368←r[3] 第三次收集之后便得到記錄的有序序列 p→138→139→167→230→237→239→367→368 我們?cè)诩夹g(shù)排序中需要注意的是： １．“分配”和“收集”的實(shí)際操作僅為修改鏈表中的指針和設(shè)置隊(duì)列的頭、尾指針； ２．為查找使用，該鏈表尚需應(yīng)用算法Arrange將它調(diào)整為有序表。 基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))。 其中，分配為O(n);收集為O(rd)(rd為“基”),d為“分配-收集”的趟數(shù)。 下面我們比較一下上面談到的各種內(nèi)部排序方法 首先，從時(shí)間性能上說： 1. 按平均的時(shí)間性能來分，有三類排序方法： 時(shí)間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈茫?nbsp; 時(shí)間復(fù)雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對(duì)那些對(duì)關(guān)鍵字近似有序的記錄序列尤為如此； 時(shí)間復(fù)雜度為O(n)的排序方法只有，基數(shù)排序。 2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度;而對(duì)于快速排序而言，這是最不好的情況，此時(shí)的時(shí)間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。 3. 簡單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。 其次，從空間性能上說： 指的是排序過程中所需的輔助空間大小。 1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復(fù)雜度為O(1)； 2. 快速排序?yàn)镺(logn)，為棧所需的輔助空間; 3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n); 4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。 再次，從排序方法的穩(wěn)定性能上說： 穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過排序之后，沒有改變。當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。我們需要指出的是：快速排序和堆排序是不穩(wěn)定的排序方法。 我們?cè)僬務(wù)勱P(guān)于“排序方法的時(shí)間復(fù)雜度的下限” 這里討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進(jìn)行排序的排序方法，可以證明，這類排序法可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法,所以它不受這個(gè)限制)。可以用一棵判定樹來描述這類基于“比較關(guān)鍵字”進(jìn)行排序的排序方法。 例如，對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹如下： K1 K1 K2< K3 K2 K3 描述排序的判定樹有兩個(gè)特點(diǎn)： １．樹上的每一次“比較”都是必要的; ２． 樹上的葉子結(jié)點(diǎn)包含所有可能情況。 則由上圖所示“判定樹的深度為4”可以推出“至多進(jìn)行三次比較”即可完成對(duì)三個(gè)關(guān)鍵字的排序。反過來說，由此判定樹可見，考慮最壞情況，“至少要進(jìn)行三次比較”才能完成對(duì)三個(gè)關(guān)鍵字的排序。對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹深度是唯一的。即無論按什么先后順序去進(jìn)行比較，所得判定樹的深度都是3。當(dāng)關(guān)鍵字的個(gè)數(shù)超過3之后，不同的排序方法其判定樹的深度不同。例如，對(duì)4個(gè)關(guān)鍵字進(jìn)行排序時(shí)，直接插入的判定樹的深度為6, 而折半插入的判定樹的深度為5。 可以證明，對(duì)4個(gè)關(guān)鍵字進(jìn)行排序，至少需進(jìn)行5次比較。因?yàn)椋?個(gè)關(guān)鍵字排序的結(jié)果有4!=24種可能，即排序的判定樹上必須有24個(gè)葉子結(jié)點(diǎn)，其深度的最小值為6。 一般情況下，對(duì)n個(gè)關(guān)鍵字進(jìn)行排序，可能得到的結(jié)果有n! 種，由于含n! 個(gè)葉子結(jié)點(diǎn)的二叉樹的深度不小于log2(n!) +1, 則對(duì)n個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至少是log2(n!) 。利用斯蒂林近似公式log2(n!) nlog2n 所以，基于“比較關(guān)鍵字”進(jìn)行排序的排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。 下面我們?cè)賮碚務(wù)勍獠颗判颍?nbsp; 常見的外部排序有： 磁盤排序和磁帶排序，之所以這么分是因?yàn)橥馀判虿坏c排序的算法有關(guān)，還與外存設(shè)備的特征有關(guān)。結(jié)合外存設(shè)備特征，大體上可分為順序存?。ㄈ绱艓В┖椭苯哟嫒。ㄈ绱疟P）兩大類。磁帶排序時(shí)間主要取決于對(duì)帶的讀寫。（這里只是交代一下，實(shí)際上正如大家知道的，基本上現(xiàn)在已經(jīng)淘汰了磁帶存儲(chǔ)的方式）需要指出的是外部排序的這兩種方式的工作過程是一致的，外部排序的基本過程由相對(duì)獨(dú)立的兩個(gè)步驟組成： １．按可用內(nèi)存大小，利用內(nèi)部排序的方法，構(gòu)造若干(記錄的)有序子序列，通常稱外存中這些記錄有序子序列為“歸并段”; ２．通過“歸并”，逐步擴(kuò)大(記錄的)有序子序列的長度，直至外存中整個(gè)記錄序列按關(guān)鍵字有序?yàn)橹埂?nbsp; 例如：假設(shè)有一個(gè)含10,000個(gè)記錄的磁盤文件，而當(dāng)前所用的計(jì)算機(jī)一次只能對(duì)1,000個(gè)記錄進(jìn)行內(nèi)部排序，則首先利用內(nèi)部排序的方法得到10個(gè)初始?xì)w并段，然后進(jìn)行逐趟歸并。 假設(shè)進(jìn)行2路歸并(即兩兩歸并)，則 第一趟由10個(gè)歸并段得到5個(gè)歸并段; 第二趟由 5 個(gè)歸并段得到3個(gè)歸并段; 第三趟由 3 個(gè)歸并段得到2個(gè)歸并段; 最后一趟歸并得到整個(gè)記錄的有序序列。 我們來分析上述外排過程中訪問外存(對(duì)外存進(jìn)行讀/寫)的次數(shù)：假設(shè)“數(shù)據(jù)塊”的大小為200，即每一次訪問外存可以讀/寫200個(gè)記錄。則對(duì)于10,000個(gè)記錄，處理一遍需訪問外存100次(讀和寫各50次)。 由此，對(duì)上述例子而言， 1) 求得10個(gè)初始?xì)w并段需訪問外存100次; 2) 每進(jìn)行一趟歸并需訪問外存100次; 3) 總計(jì)訪問外存 100 + 4 100 = 500次。 外排總的時(shí)間還應(yīng)包括內(nèi)部排序所需時(shí)間和逐趟歸并時(shí)進(jìn)行內(nèi)部歸并的時(shí)間，顯然，除去內(nèi)部排序的因素外，外部排序的時(shí)間取決于逐趟歸并所需進(jìn)行的“趟數(shù)”。 例如，若對(duì)上述例子采用5路歸并，則只需進(jìn)行2趟歸并，總的訪問外存的次數(shù)將壓縮到 100 + 2 100 = 300 次 一般情況下，假設(shè)待排記錄序列含m個(gè)初始?xì)w并段，外排時(shí)采用k路歸并，則歸并趟數(shù)為 logkm，顯然，隨之k的增大歸并的趟數(shù)將減少，因此對(duì)外排而言，通常采用多路歸并。k的大小可選，但需綜合考慮各種因素。 上面談的都是假設(shè)在單處理機(jī)上完成的工作，下面將談?wù)劜⑿信判颍?nbsp; 并行排序：是指利用多臺(tái)處理機(jī)（并行機(jī)）進(jìn)行的排序，其目的主要是為了提高速度。并行排序算法雖然和前面談到的單處理機(jī)上的串行排序算法有不少相似之處，但不能認(rèn)為它只是它是串行算法的簡單推廣和擴(kuò)充。它的最大特點(diǎn)之一就是他和并行計(jì)算機(jī)的體系結(jié)構(gòu)密切相關(guān)，不同體系結(jié)構(gòu)導(dǎo)致不同加速和不同設(shè)計(jì)風(fēng)格的并行排序算法。 圖與網(wǎng)絡(luò)優(yōu)化算法： 組合算法中內(nèi)容最豐富的部分就是圖與網(wǎng)絡(luò)優(yōu)化算法。圖論中的計(jì)算問題包括圖的搜索、路徑問題、連通性問題、可平面性檢驗(yàn)、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中的著名算法有：求最小生成樹的Kruskal算法、求最短路徑的Dijkstra算法和Floyd算法、求二部圖最大匹配（指派問題）的匈牙利算法、求一般圖最大匹配的Edmonds“花”算法、求網(wǎng)絡(luò)最大流和最小割的算法等。 求最小生成樹的Kruskal算法 由于這個(gè)是大家都熟悉的，我只簡單的說說：為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小。Kruskal算法的做法就是：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。算法如下: 構(gòu)造非連通圖 ST=( V,{ } ); k = i = 0; while (k ++i; 從邊集 E 中選取第i條權(quán)值最小的邊(u,v); 若(u,v)加入ST后不使ST中產(chǎn)生回路， 則 輸出邊(u,v); k++; } ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 20:08:26 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊(cè)：2003-8-28 第 5 樓 求最短路徑的Dijkstra算法： Dijkstra算法是一種解決最短路徑問題的非常有效的算法，時(shí)間復(fù)雜度為 O(│V│2)，下面是一段精確的描述（本段引自MIT的課程主頁，不翻譯了，保持原作）中文描述一般的書上都會(huì)有： 1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2. 2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v. 3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1. 4. Let Si+1 = Si cup {ui+1}. 5. Replace i by i+1. If i=│V│-1 then stop, otherwise go to step 2. 6. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If │V│ = 1 then stop, otherwise go to step 2. 7. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v. 8. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1. 9. Let Si+1 = Si cup {ui+1}. 10. Replace i by i+1. If i=│V│-1 then stop, otherwise go to step 2. 求二部圖最大匹配（指派問題）的匈牙利算法： 談匈牙利算法自然避不開Hall定理，即是：對(duì)于二部圖G，存在一個(gè)匹配M，使得X的所有頂點(diǎn)關(guān)于M飽和的充要條件是：對(duì)于X的任意一個(gè)子集A，和A鄰接的點(diǎn)集為T(A)，恒有： │T(A)│ >= │A│ 匈牙利算法是基于Hall定理中充分性證明的思想，其基本步驟為： 1．任給初始匹配M； 2．若X已飽和則結(jié)束，否則進(jìn)行第3步； 3．在X中找到一個(gè)非飽和頂點(diǎn)x0，作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2則因?yàn)闊o法匹配而停止，否則任選一點(diǎn)y ∈T(V1)\V2； 5．若y已飽和則轉(zhuǎn)6，否則做一條從x0 →y的可增廣道路P，M←M⊕E(P)，轉(zhuǎn)2； 6．由于y已飽和，所以M中有一條邊(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 轉(zhuǎn)4； 關(guān)于求網(wǎng)絡(luò)最大流和最小割的標(biāo)號(hào)算法： 給定一個(gè)有向圖G=(V,E)，把圖中的邊看作管道，每條邊上有一個(gè)權(quán)值，表示該管道的流量上限。給定源點(diǎn)s和匯點(diǎn)t，現(xiàn)在假設(shè)在s處有一個(gè)水源，t處有一個(gè)蓄水池，問從s到t的最大水流量是多少。這就叫做網(wǎng)絡(luò)流問題。用數(shù)學(xué)語言描述就是： 設(shè)G=(V,E)是一個(gè)流網(wǎng)絡(luò)，設(shè)c(u, v)>＝0 表示從u到v的管道的流量上限。設(shè)s為源，t為匯。G的流是一個(gè)函數(shù)f: V×V →R，且滿足下面三個(gè)特征： 1. 容量限制：對(duì)于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v) 2. 斜對(duì)稱性：對(duì)于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u) 3. 流的會(huì)話：對(duì)于所有的 u ∈ V - {s, t}，要求∑ f(u, v) = 0；v∈V f(u,v)稱為從結(jié)點(diǎn)u到v的網(wǎng)絡(luò)流，它可以為正也可以為負(fù)。流 f 的值定義為： │f│ = ∑ f(s, v) v∈V 即從源出發(fā)的所有流的總和。 最大流問題就是找出給定流網(wǎng)絡(luò)的最大流。網(wǎng)絡(luò)流問題可以歸結(jié)為一類特殊的線性規(guī)劃問題。 尋找最大流的基本方法是Ford-Fulkerson方法，該方法有多種實(shí)現(xiàn)，其基本思想是從某個(gè)可行流F出發(fā)，找到關(guān)于這個(gè)流的一個(gè)可改進(jìn)路經(jīng)P，然后沿著P調(diào)整F，對(duì)新的可行流試圖尋找關(guān)于他的可改進(jìn)路經(jīng)，如此反復(fù)直至求得最大流。現(xiàn)在要找最小費(fèi)用的最大流，可以證明，若F是流量為V(F)的流中費(fèi)用最小者，而P是關(guān)于F的所有可改進(jìn)路中費(fèi)用最小的可改進(jìn)路，則沿著P去調(diào)整F,得到的可行流F'一定是流量為V(F')的所有可行流中的最小費(fèi)用流。這樣，當(dāng)F是最大流時(shí)候，他就是所要求的最小費(fèi)用最大流。 注意到每條邊的單位流量費(fèi)用B(i,j)≥0，所以F=0必是流量為0的最小費(fèi)用流，這樣總可以 從F=0出發(fā)求出最小費(fèi)用最大流。一般的，設(shè)已知F是流量V(F)的最小費(fèi)用流，余下的問題就是如何去尋找關(guān)于F的最小費(fèi)用可改進(jìn)路。為此我們將原網(wǎng)絡(luò)中的每條弧變成兩條方向相反的?。?nbsp; 1。前向弧，容量C和費(fèi)用B不變，流量F為0； 2。后向弧，容量C為0，費(fèi)用為-B，流量F為0； 每一個(gè)頂點(diǎn)上設(shè)置一個(gè)參數(shù)CT，表示源點(diǎn)至該頂點(diǎn)的通路上的費(fèi)用和。如果我們得出一條關(guān)于F的最小費(fèi)用可改進(jìn)路時(shí)，則該路上的每一個(gè)頂點(diǎn)的CT值相對(duì)于其它可改進(jìn)路來說是最小的。每一次尋找最小費(fèi)用可改進(jìn)路時(shí)前，源點(diǎn)的CT為0，其它頂點(diǎn)的CT為+∞。 設(shè)cost為流的運(yùn)輸費(fèi)用，初始時(shí)由于F=0,則cost=0,我們每求出一條關(guān)于F的最小費(fèi)用可改進(jìn)路，則通過cost ← cost + ∑B(e)*d, （其中e∈P,d為P的可改進(jìn)量）來累積流的運(yùn)輸費(fèi)用 的增加量。顯然，當(dāng)求出最小費(fèi)用最大流時(shí)，cost便成為最大流的運(yùn)輸費(fèi)用了。 另外設(shè)置布爾變量break為最小費(fèi)用可改進(jìn)路的延伸標(biāo)志，在搜索了網(wǎng)絡(luò)中的每一個(gè)頂點(diǎn)后 ，若break=true表示可改進(jìn)路還可以延伸，還需要重新搜索網(wǎng)絡(luò)中的頂點(diǎn)；否則說明最小費(fèi) 用的可改進(jìn)路已經(jīng)找到或者最大流已經(jīng)求出。 下面是算法的偽代碼： cost ← 0; repeat 可改進(jìn)路撤空； 設(shè)源點(diǎn)的CT值為0并進(jìn)入可改進(jìn)路； repeat break ← false; for u ←1 to N do begin 分析U出發(fā)的所有弧; if (的流量可改進(jìn)）and(源點(diǎn)至U有通路)and(U的CT值+的費(fèi)用 < V的CT值) then begin break ← true; V的CT值 ← U的CT值+的費(fèi)用； V進(jìn)入可改進(jìn)路經(jīng)并為之標(biāo)號(hào)； end if end for until break=false if 匯點(diǎn)已標(biāo)號(hào) then begin 從匯點(diǎn)出發(fā)倒向修正可改進(jìn)路的流量； cost ← cost + ∑B(e)*d（其中e∈P,d為P的可改進(jìn)量）； end if until 匯點(diǎn)未標(biāo)號(hào)； 可見，上述的算法和求最大流的Edmonds-Karp標(biāo)號(hào)算法幾乎一樣，因?yàn)檫@兩種算法都使用寬度優(yōu)先搜索來來尋找增廣路徑，所以復(fù)雜度也相同，都是O(VE)，其中V是節(jié)點(diǎn)數(shù)目，E是邊數(shù)目。 其他的就不詳述了，大家感興趣的可以查閱TAOCP或者是算法導(dǎo)論的相關(guān)內(nèi)容。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 20:09:12 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊(cè)：2003-8-28 第 6 樓 貪心法與擬陣： 貪心法是求解關(guān)于獨(dú)立系統(tǒng)組合優(yōu)化問題的一種簡單算法，求最小生成樹的Kruskal算法就是一種貪心算法。但是貪心法并不總能找到最優(yōu)獨(dú)立集。貪心法能求得最優(yōu)獨(dú)立集的充分必要條件是L為一個(gè)擬陣。事實(shí)上，求最大生成樹是關(guān)于擬陣的組合優(yōu)化問題，而二部圖的所有匹配構(gòu)成的獨(dú)立系統(tǒng)U不是擬陣。 貪心法的基本思路是：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。 該算法存在問題： 1. 不能保證求得的最后解是最佳的； 2. 不能用來求最大或最小解問題； 3. 只能求滿足某些約束條件的可行解的范圍。 實(shí)現(xiàn)該算法的過程： 從問題的某一初始解出發(fā)； while 能朝給定總目標(biāo)前進(jìn)一步 do 求出可行解的一個(gè)解元素； 由所有解元素組合成問題的一個(gè)可行解； 窮舉搜索： 組合算法要解決的問題只有有限種可能，在沒有跟好算法時(shí)總可以用窮舉搜索的辦法解決，即逐個(gè)的檢查所有可能的情況?？梢韵胂螅闆r較多時(shí)這種方法極為費(fèi)時(shí)。實(shí)際上并不需要機(jī)械的檢查每一種情況，常常是可以提前判斷出某些情況不可能取到最優(yōu)解，從而可以提前舍棄這些情況。這樣也是隱含的檢查了所有可能的情況，既減少了搜索量，又保證了不漏掉最優(yōu)解。這方面怒火之炮寫過文章，我認(rèn)為沒必要敖述了。 分支限界法： 這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 算法思想：分枝定界（branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)镋-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。 有兩種常用的方法可用來選擇下一個(gè)E-節(jié)點(diǎn)（雖然也可能存在其他的方法）： 1) 先進(jìn)先出（F I F O） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。 2) 最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果查找 一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建立，下一個(gè)E-節(jié)點(diǎn)就是具有最小耗費(fèi) 的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個(gè) E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn)。 動(dòng)態(tài)規(guī)劃： 動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究 多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著Dynamic Programming，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。 一般來說，只要問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了 子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。 由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問題是獨(dú)立的 (即不包含公共的子子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇，該方法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。 因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。 設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行： 1．劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意這若干 個(gè)階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動(dòng)態(tài)規(guī) 劃求解。 2．選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示 出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移 有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。 所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實(shí)上，我們常常是 反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。 3．寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式 化表達(dá)式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較 簡單的。 動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡單。 分治法： 對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解 決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。 任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。例如，對(duì)于n個(gè)元素的排序問題，當(dāng)n=1時(shí)，不需任何計(jì)算。n=2時(shí)，只要作一次比較即可排好序。n=3時(shí)只要作3次比較即可，…。而當(dāng)n較大時(shí)，問題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。 如果原問題可分割成k個(gè)子問題，1 < k ≤ n ，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 其基本步驟是： 分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題； 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題； 合并：將各個(gè)子問題的解合并為原問題的解。 它的一般的算法設(shè)計(jì)模式如下： Divide-and-Conquer(P) 1．if │P│≤n0 2．then return( ADHOC(P) ) 3．將P分解為較小的子問題 P1 ,P2 ,...,Pk 4．for i←1 to k 5．do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi 6．T ← MERGE(y1,y2,...,yk) △ 合并子問題 7．return(T) 其中│P│表示問題P的規(guī)模；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時(shí)，問題已 容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法，用于直接 解小規(guī)模的問題P。因此，當(dāng)P的規(guī)模不超過n0時(shí)，直接用算法ADHOC(P)求解。算法 MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1 ,P2 ,... ,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。 根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個(gè)子問題才較適宜？各個(gè)子問題的規(guī) 模應(yīng)該怎樣才為適當(dāng)？這些問題很難予以肯定的回答。但人們從大量實(shí)踐中發(fā)現(xiàn)， 在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。換句話說，將一個(gè)問題分 成大小相等的k個(gè)子問題的處理方法是行之有效的。許多問題可以取k=2。這種使子 問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是 比子問題規(guī)模不等的做法要好。 分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復(fù)雜，或者是有多種合并方案，或者是合并方案不明顯，究竟應(yīng)該怎樣合并，沒有統(tǒng)一的模式，需要具體問題具體分析。 其他的一些經(jīng)典的算法，如快速傅里葉變換，大家都非常熟悉，這里就不再涉及。如果想深入學(xué)習(xí)不妨參考San Diego 州立大學(xué)的相關(guān)課程主頁 http://www.eli./courses/fall95/cs660/notes/ 組合算法的設(shè)計(jì)是一門藝術(shù)，需要高度的技巧和靈感。算法分析的任務(wù)是分析算法的優(yōu)劣，算法分析的任務(wù)是分析算法的優(yōu)劣，主要是討論算法的時(shí)間復(fù)雜性和空間復(fù)雜性。它的理論基礎(chǔ)是組合分析，包括計(jì)數(shù)和枚舉。計(jì)算復(fù)雜性理論，特別是NP完全性理論，與組合算法是緊密相關(guān)的。NP完全性概念的提出，正是為了刻畫包括旅行商問題、圖著色問題、圖著色問題、整數(shù)規(guī)劃等一大批組合問題的計(jì)算難度。計(jì)算復(fù)雜性理論研究算法在時(shí)間和空間限制下的能力以及問題的難度，使組合算法的研究有了更加清晰的框架，將組合算法的研究提高到一個(gè)新的水平。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); |
|
|
