組合算法

絕地戰(zhàn)士 2011-01-26

展開全文

組合算法概論(A Brief Introduction to Combinatorial Algorithm)

組合算法是算法分析學(xué)當(dāng)中非常重要的一個分支，關(guān)于它在計算機科學(xué)的地位我就不敖述了，下面為大家整理了整個材料，算法是我收集的，只是分門別類簡單介紹一下，然后把我的材料做了個整理，大家收藏吧，感覺挺有用的，費了我好長時間和精力呀，我現(xiàn)在準備考研了，沒有太多時間發(fā)很多經(jīng)典文章了，這片算是大部頭了。

關(guān)于組合學(xué)問題的算法，計算對象是離散的、有限的數(shù)學(xué)結(jié)構(gòu)。從方法學(xué)的角度，組合算法包括算法設(shè)計和算法分析兩個方面。關(guān)于算法設(shè)計，歷史上已經(jīng)總結(jié)出了若干帶有普遍意義的方法和技術(shù)，包括動態(tài)規(guī)劃、回溯法、分支限界法、分治法、貪心法等。下面我們著重談?wù)剮讉€有代表性的組合算法：

單純形法：

這是一種線性規(guī)劃算法，由G.B.Dantzig在1947年提出，后來由他和其他的學(xué)者又提出了單純形法的變形和改進。這些被實踐證明都是行之有效的，線性規(guī)劃研究線性目標函數(shù)在一組線性等式與線性不等式約束下的極值問題。這本來是連續(xù)問題，Dantzig發(fā)現(xiàn)線性規(guī)劃問題的可行解集（即滿足約束條件的點的全體）是一個超多面體。如果它的最優(yōu)解存在，那么這個最優(yōu)解一定可以在超多面體的一個頂點取到。由于超多面體的頂點只有有限個，從而使線性規(guī)劃成為一個組和優(yōu)化問題。單純形法是按照一定的規(guī)則，從可行解集的一個頂點轉(zhuǎn)移到另一個頂點，使得目標函數(shù)的值不斷地得到改進，最后達到最優(yōu)。盡管單純形法一直使用得很好，但是在最壞情況下它需要指數(shù)運行時間，從而使線性規(guī)劃問題是否屬于P類一度成為人們關(guān)心的問題。后來的橢球算法和投影算法都很好的解決了這個問題。

排序和檢索：

這兩部分應(yīng)當(dāng)是大家比較熟悉的，所謂排序，就是將給定的元素序列按照某種順序關(guān)系重新排列成有序序列。例如將n個數(shù)組成的序列按照從小到大的順序重新排列；將n個英語單詞組成的的序列按照字典順序重新排列。所謂檢索，就是在給定的集合中查找某個特定的元素或是元素組。排序和檢索已經(jīng)成為計算機科學(xué)技術(shù)中最基本、使用最頻繁的算法。下面我們專門談?wù)勁判蛩惴ǎ╯orting

algorithm）。

在討論此種算法時，數(shù)據(jù)通常是指由若干記錄組成的文件，每個記錄包含一個或多個數(shù)據(jù)項，其中能夠標志該記錄的數(shù)據(jù)項稱為鍵碼。給定一文件的n個記錄{R1,R2,…,Rn}及其相應(yīng)的鍵碼的集合{K1,K2,…,Kn}。所謂排序算法就是在數(shù)據(jù)處理中將文件中的記錄按鍵碼的一定次序要求排列起來的算法。若待排序的文件能夠同時裝入計算機的主存中，整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，有一部分必須放在外存上，則稱此類排序問題為外部排序。當(dāng)待排序的文件中包含有一些相同鍵碼的記錄時，如果經(jīng)過排序后這些相同的鍵碼的記錄的相對次序仍然保持不變，則相應(yīng)的排序算法是穩(wěn)定的，否則為不穩(wěn)定的。如果排序算法設(shè)計成單處理機完成的，則此排序算法稱為串行（或順序）排序算法；如果排序算法時設(shè)計成多處理機實現(xiàn)的，則稱為并行排序算法。

首先談?wù)剝?nèi)部排序：內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。

使有序區(qū)中記錄的數(shù)目增加一個或幾個的操作稱為一趟排序。

逐步擴大記錄有序序列長度的方法大致有下列幾類：

一．插入排序

假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：

則一趟直接插入排序的基本思想為：將記錄R

插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]。

顯然，完成這個“插入”需分三步進行：

1．查找R的插入位置j+1；

2．將R[j+1..i-1]中的記錄后移一個位置；

3．將R復(fù)制到R[j+1]的位置上。

[I]直接插入排序

利用順序查找實現(xiàn)“在R[1..i-1]中查找R的插入位置”的插入排序。

注意直接插入排序算法的三個要點：

1．從R[i-1]起向前進行順序查找，監(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．對于在查找過程中找到的那些關(guān)鍵字不小于R.key的記錄，可以在查找的同時實現(xiàn)向后移動；

for (j=i-1; R[0].key<R[j].key; --j);

R[j+1] = R[j]

3．i = 2，3，…, n, 實現(xiàn)整個序列的排序。

template<class Elem>

void InsertionSort ( Elem R[], int n)

{

// 對記錄序列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

時間分析：

實現(xiàn)排序的基本操作有兩個：

（1）“比較”序列中兩個關(guān)鍵字的大??；

（2）“移動”記錄。

對于直接插入排序：

[II]折半插入排序

因為R[1..i-1]是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R[1..i-1]中查找R的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。其算法如下：

template<class Elem>

void BiInsertionSort (Elem R[]， int n)

{

// 對記錄序列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; // 插入點在低半?yún)^(qū)

else

low = m+1; // 插入點在高半?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ù)，但記錄“移動”的次數(shù)不變。

[III]表插入排序

為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。

算法描述如下：

template<class Elem>

void LInsertionSort (Elem SL[]， int n)

{

// 對記錄序列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é)點i插入在結(jié)點j和結(jié)點k之間

}// LinsertionSort

關(guān)于如在排序之后調(diào)整記錄序列：

算法中使用了三個指針:

其中：p指示第i個記錄的當(dāng)前位置；

i指示第i個記錄應(yīng)在的位置；

q指示第i+1個記錄的當(dāng)前位置

template<class Elem>

void Arrange ( SLinkListType SL[ ], int n ) {

// 根據(jù)靜態(tài)鏈表SL中各結(jié)點的指針值調(diào)整

// 記錄位置，使得SL中記錄按關(guān)鍵字非遞減

// 有序順序排列

p = SL[0].next;// p指示第一個記錄的當(dāng)前位置

for ( i=1; i<n; ++i ) {

// SL[1..i-1]中記錄已按關(guān)鍵字有序排列，

// 第i個記錄在SL中的當(dāng)前位置應(yīng)不小于i

while (p<i) p = SL[p].next;

// 找到第i個記錄，并用p指示

// 其在SL中當(dāng)前位置

q = SL[p].next; // q指示尚未調(diào)整的表尾

if ( p!= i ) {

SL[p]←→SL; // 交換記錄，使第i個

// 記錄到位

SL.next = p; // 指向被移走的記錄，

// 使得以后可由while循環(huán)找回

}

p = q; // p指示尚未調(diào)整的表尾，

// 為找第i+1個記錄作準備

}

} // Arrange

二．交換排序

通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度;

[I]起泡排序

假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為：n-i+1

則第i趟起泡插入排序的基本思想為：借助對無序序列中的記錄進行“交換”的操作，將無序序列中關(guān)鍵字最大的記錄“交換”到R[n-i+1]的位置上。

算法描述：

template <class Elem>

void BubbleSort(Elem R[], int n)

{

// i 指示無序序列中最后一個記錄的位置

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ī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

等級：職業(yè)俠客

文章：470

積分：956

門派：黑客帝國

注冊：2003-8-28

第 2 樓

[II]一趟快速排序

目標：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。致使一趟排序之后，記錄的無序序列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è)立兩個指針:low和high，它們的初值分別為:s和t,

之后逐漸減小high，增加low，并保證R[high].key≥52，而R[low].key≤52,否則進行記錄的“交換”。

算法描述如下:

template<class Elem>

int Partition (Elem R[], int low, int high) {

// 交換記錄子序列R[low..high]中的記錄，使

// 樞軸記錄到位，并返回其所在位置，此時，

// 在它之前（后）的記錄均不大（小）于它

pivotkey = R[low].key;

// 用子表的第一個記錄作樞軸記錄

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)整過程中的樞軸位置并不重要，因此，為了減少記錄的移動次數(shù)，應(yīng)先將樞軸記錄“移出”，待求得樞軸記錄應(yīng)在的位置之后(此時low=high),再將樞軸記錄到位。

將上述“一次劃分”的算法改寫如下：

template<class Elem>

int Partition (Elem R[], int low, int high) {

// 交換記錄子序列R[low..high]中的記錄，使

//樞軸記錄到位，并返回其所在位置，此時，

// 在它之前（后）的記錄均不大（?。┯谒?nbsp;

R[0] = R[low];

// 用子表的第一個記錄作樞軸記錄

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]快速排序

在對無序序列中記錄進行了一次分割之后，分別對分割所得兩個子序列進行快速排序，依次類推，直至每個子序列中只含一個記錄為止。

快速排序的算法描述如下:

template<class Elem>

void QSort (Elem R[], int low, int high) {

// 對記錄序列R[low..high]進行快速排序

if (low < high-1) { // 長度大于1

pivotloc = Partition(L, low, high);

// 將L.r[low..high]一分為二

QSort(L, low, pivotloc-1);

// 對低子表遞歸排序，pivotloc是樞軸位置

QSort(L, pivotloc+1, high);

// 對高子表遞歸排序

}

} // QSort

template<class Elem>

void QuickSort(Elem R[], int n) {

// 對記錄序列進行快速排序

QSort(R, 1, n);

} // QuickSort

快速排序的時間分析

假設(shè)一次劃分所得樞軸位置i=k，則對n個記錄進行快排所需時間

T(n) = Tpass(n)+T(k-1)+T(n-k)

其中

Tpass(n)為對n個記錄進行一次劃分所需時間，若待排序列中記錄的關(guān)鍵字是隨機分布的，則k取1至n中任意一值的可能性相同，由此可得快速排序所需時間的平均值為：

設(shè) Tavg(1)≤b

則可得結(jié)果

通常，快速排序被認為是在所有同數(shù)量級O(nlogn)的排序方法中，其平均性能是最好的。但是，若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判?，其時間復(fù)雜度為O(n2)。

為避免出現(xià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 ) {

// 對記錄序列R[1..n]作簡單選擇排序。

for (i=1; i // 選擇第i小的記錄，并交換到位

j = SelectMinKey(R, i);

// 在R[i..n]中選擇key最小的記錄

if (i!=j) R←→R[j];

// 與第i個記錄交換

}

} // SelectSort

時間性能分析

對n個記錄進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)總計為

移動記錄的次數(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

等級：職業(yè)俠客

文章：470

積分：956

門派：黑客帝國

注冊：2003-8-28

第 3 樓

堆排序也是選擇排序的一種，其特點是，在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果。

堆的定義:

堆是滿足下列性質(zhì)的數(shù)列{r1, r2, …，rn}：

或

若將此數(shù)列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當(dāng)左/右子樹不空時，根結(jié)點的值小于(或大于)左/右子樹根結(jié)點的值。

由此，若上述數(shù)列是堆，則r1必是數(shù)列中的最小值或最大值，分別稱作小頂堆或大頂堆。

堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。具體作法是：先建一個“大頂堆”，即先選得一個關(guān)鍵字為最大的記錄，然后與序列中最后一個記錄交換，之后繼續(xù)對序列中前n-1記錄進行“篩選”，重新將它調(diào)整為一個“大頂堆”，再將堆頂記錄和第n-1個記錄交換，如此反復(fù)直至排序結(jié)束。

所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹為堆。

堆排序的算法如下所示：

template

void HeapSort ( Elem R[], int n ) {

// 對記錄序列R[1..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]中最后一個記錄相互交換

HeapAdjust(R, 1, i-1);

// 將R[1..i-1] 重新調(diào)整為大頂堆

}

} // HeapSort

其中篩選的算法如下所示。為將R[s..m]調(diào)整為“大頂堆”，算法中“篩選”應(yīng)沿關(guān)鍵字較大的孩子結(jié)點向下進行。

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]成為一個大頂堆（對其中

// 記錄的關(guān)鍵字而言）

rc = R[s];

for ( j=2*s; j<=m; j*=2 ) {// 沿key較大的孩子結(jié)點向下篩選

if ( j if ( rc.key >= R[j].key ) break; // rc應(yīng)插入在位置s上

R[s] = R[j]; s = j;

}

R[s] = rc; // 插入

} // HeapAdjust

堆排序的時間復(fù)雜度分析：

1. 對深度為k的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為2(k-1);

2．對n個關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進行的關(guān)鍵字比較的次數(shù)至多為4n;

3. 調(diào)整“堆頂”n-1次，總共進行的關(guān)鍵字比較的次數(shù)不超過

2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n)

因此，堆排序的時間復(fù)雜度為O(nlogn)

四．歸并排序：是通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度;歸并排序的基本思想是：將兩個或兩個以上的有序子序列“歸并”為一個有序序列。

在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的有序子序列歸并為一個有序序列。

“歸并”算法描述如下：

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è)計思想得出的。在此，只討論遞歸形式的算法。

這是一種自頂向下的分析方法：

如果記錄無序序列R[s..t]的兩部分R[s..(s+t)/2]和R[(s+t)/2+1..t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列，由此，應(yīng)該先分別對這兩部分進行2-路歸并排序。

template

void Msort ( Elem SR[], Elem TR1[], int s, int t ) {

// 將SR[s..t]進行2-路歸并排序為TR1[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[]) {

// 對記錄序列R[1..n]作2-路歸并排序。

MSort(R, R, 1, n);

} // MergeSort

容易看出，對n個記錄進行歸并排序的時間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時間復(fù)雜度為O(n)，總共需進行l(wèi)ogn趟。

五．基數(shù)排序：借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的算法。

[I]多關(guān)鍵字的排序

假設(shè)有n個記錄……的序列

{ R1, R2, …，Rn}

每個記錄Ri中含有d個關(guān)鍵字(Ki0, Ki1, …,Kid-1),則稱上述記錄序列對關(guān)鍵字(Ki0, Ki1,

…,Kid-1)有序是指：對于序列中任意兩個記錄Ri和Rj(1≤i (Ki0, Ki1, …,Kid-1)< (Kj0, Kj1,

…,Kjd-1)

其中K0被稱為“最主”位關(guān)鍵字，Kd-1被稱為 “最次”位關(guān)鍵字。

實現(xiàn)多關(guān)鍵字排序通常有兩種作法:

最高位優(yōu)先MSD法：先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序，…，依次類推，直至最后對最次位關(guān)鍵字排序完成為止。

最低位優(yōu)先LSD法：先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關(guān)鍵字K0排序完成為止。排序過程中不需要根據(jù)“前一個”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(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

等級：職業(yè)俠客

文章：470

積分：956

門派：黑客帝國

注冊：2003-8-28

第 4 樓

例如:學(xué)生記錄含三個關(guān)鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。LSD的排序過程如下:

[II]鏈式基數(shù)排序

假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關(guān)鍵字間的比較。

對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數(shù)排序法。

例如：對下列這組關(guān)鍵字

{209, 386, 768, 185, 247, 606, 230, 834, 539 }

首先按其“個位數(shù)”取值分別為0, 1, …，9“分配”成10組，之后按從0至9的順序?qū)⑺鼈?#8220;收集”在一起;然后按其“十位數(shù)”

取值分別為0, 1,

…，9“分配”成10組，之后再按從0至9的順序?qū)⑺鼈?#8220;收集”在一起;最后按其“百位數(shù)”重復(fù)一遍上述操作，便可得到這組關(guān)鍵字的有序序列。

在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為：

１．待排序記錄以指針相鏈，構(gòu)成一個鏈表；

２．“分配”時，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊列”中，每個隊列中記錄的“關(guān)鍵字位”相同；

３．“收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;

４．對每個關(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

我們在技術(shù)排序中需要注意的是：

１．“分配”和“收集”的實際操作僅為修改鏈表中的指針和設(shè)置隊列的頭、尾指針；

２．為查找使用，該鏈表尚需應(yīng)用算法Arrange將它調(diào)整為有序表。

基數(shù)排序的時間復(fù)雜度為O(d(n+rd))。

其中，分配為O(n);收集為O(rd)(rd為“基”),d為“分配-收集”的趟數(shù)。

下面我們比較一下上面談到的各種內(nèi)部排序方法

首先，從時間性能上說：

1. 按平均的時間性能來分，有三類排序方法：

時間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序為最好；

時間復(fù)雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關(guān)鍵字近似有序的記錄序列尤為如此；

時間復(fù)雜度為O(n)的排序方法只有，基數(shù)排序。

當(dāng)待排記錄序列按關(guān)鍵字順序有序時，直接插入排序和起泡排序能達到O(n)的時間復(fù)雜度;而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。

3. 簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。

其次，從空間性能上說：

指的是排序過程中所需的輔助空間大小。

1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復(fù)雜度為O(1)；

2. 快速排序為O(logn)，為棧所需的輔助空間;

3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);

4. 鏈式基數(shù)排序需附設(shè)隊列首尾指針，則空間復(fù)雜度為O(rd)。

再次，從排序方法的穩(wěn)定性能上說：

穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。當(dāng)對多關(guān)鍵字的記錄序列進行LSD方法排序時，必須采用穩(wěn)定的排序方法。對于不穩(wěn)定的排序方法，只要能舉出一個實例說明即可。我們需要指出的是：快速排序和堆排序是不穩(wěn)定的排序方法。

我們再談?wù)勱P(guān)于“排序方法的時間復(fù)雜度的下限”

這里討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進行排序的排序方法，可以證明，這類排序法可能達到的最快的時間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法,所以它不受這個限制)?？梢杂靡豢门卸鋪砻枋鲞@類基于“比較關(guān)鍵字”進行排序的排序方法。

例如，對三個關(guān)鍵字進行排序的判定樹如下：

K2< K3 K2

K3 描述排序的判定樹有兩個特點：

１．樹上的每一次“比較”都是必要的;

２．樹上的葉子結(jié)點包含所有可能情況。

則由上圖所示“判定樹的深度為4”可以推出“至多進行三次比較”即可完成對三個關(guān)鍵字的排序。反過來說，由此判定樹可見，考慮最壞情況，“至少要進行三次比較”才能完成對三個關(guān)鍵字的排序。對三個關(guān)鍵字進行排序的判定樹深度是唯一的。即無論按什么先后順序去進行比較，所得判定樹的深度都是3。當(dāng)關(guān)鍵字的個數(shù)超過3之后，不同的排序方法其判定樹的深度不同。例如，對4個關(guān)鍵字進行排序時，直接插入的判定樹的深度為6,

而折半插入的判定樹的深度為5。

可以證明，對4個關(guān)鍵字進行排序，至少需進行5次比較。因為，4個關(guān)鍵字排序的結(jié)果有4!=24種可能，即排序的判定樹上必須有24個葉子結(jié)點，其深度的最小值為6。

一般情況下，對n個關(guān)鍵字進行排序，可能得到的結(jié)果有n! 種，由于含n! 個葉子結(jié)點的二叉樹的深度不小于log2(n!) +1,

則對n個關(guān)鍵字進行排序的比較次數(shù)至少是log2(n!) 。利用斯蒂林近似公式log2(n!)  nlog2n

所以，基于“比較關(guān)鍵字”進行排序的排序方法，可能達到的最快的時間復(fù)雜度為O(nlogn)。

下面我們再來談?wù)勍獠颗判颍?nbsp;

常見的外部排序有：

磁盤排序和磁帶排序，之所以這么分是因為外排序不但與排序的算法有關(guān)，還與外存設(shè)備的特征有關(guān)。結(jié)合外存設(shè)備特征，大體上可分為順序存取（如磁帶）和直接存?。ㄈ绱疟P）兩大類。磁帶排序時間主要取決于對帶的讀寫。（這里只是交代一下，實際上正如大家知道的，基本上現(xiàn)在已經(jīng)淘汰了磁帶存儲的方式）需要指出的是外部排序的這兩種方式的工作過程是一致的，外部排序的基本過程由相對獨立的兩個步驟組成：

１．按可用內(nèi)存大小，利用內(nèi)部排序的方法，構(gòu)造若干(記錄的)有序子序列，通常稱外存中這些記錄有序子序列為“歸并段”;

２．通過“歸并”，逐步擴大(記錄的)有序子序列的長度，直至外存中整個記錄序列按關(guān)鍵字有序為止。

例如：假設(shè)有一個含10,000個記錄的磁盤文件，而當(dāng)前所用的計算機一次只能對1,000個記錄進行內(nèi)部排序，則首先利用內(nèi)部排序的方法得到10個初始歸并段，然后進行逐趟歸并。

假設(shè)進行2路歸并(即兩兩歸并)，則

第一趟由10個歸并段得到5個歸并段;

第二趟由 5 個歸并段得到3個歸并段;

第三趟由 3 個歸并段得到2個歸并段;

最后一趟歸并得到整個記錄的有序序列。

我們來分析上述外排過程中訪問外存(對外存進行讀/寫)的次數(shù)：假設(shè)“數(shù)據(jù)塊”的大小為200，即每一次訪問外存可以讀/寫200個記錄。則對于10,000個記錄，處理一遍需訪問外存100次(讀和寫各50次)。

由此，對上述例子而言，

1) 求得10個初始歸并段需訪問外存100次;

2) 每進行一趟歸并需訪問外存100次;

3) 總計訪問外存 100 + 4  100 = 500次。

外排總的時間還應(yīng)包括內(nèi)部排序所需時間和逐趟歸并時進行內(nèi)部歸并的時間，顯然，除去內(nèi)部排序的因素外，外部排序的時間取決于逐趟歸并所需進行的“趟數(shù)”。

例如，若對上述例子采用5路歸并，則只需進行2趟歸并，總的訪問外存的次數(shù)將壓縮到 100 + 2  100 = 300 次

一般情況下，假設(shè)待排記錄序列含m個初始歸并段，外排時采用k路歸并，則歸并趟數(shù)為

logkm，顯然，隨之k的增大歸并的趟數(shù)將減少，因此對外排而言，通常采用多路歸并。k的大小可選，但需綜合考慮各種因素。

上面談的都是假設(shè)在單處理機上完成的工作，下面將談?wù)劜⑿信判颍?nbsp;

并行排序：是指利用多臺處理機（并行機）進行的排序，其目的主要是為了提高速度。并行排序算法雖然和前面談到的單處理機上的串行排序算法有不少相似之處，但不能認為它只是它是串行算法的簡單推廣和擴充。它的最大特點之一就是他和并行計算機的體系結(jié)構(gòu)密切相關(guān)，不同體系結(jié)構(gòu)導(dǎo)致不同加速和不同設(shè)計風(fēng)格的并行排序算法。

圖與網(wǎng)絡(luò)優(yōu)化算法：

組合算法中內(nèi)容最豐富的部分就是圖與網(wǎng)絡(luò)優(yōu)化算法。圖論中的計算問題包括圖的搜索、路徑問題、連通性問題、可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中的著名算法有：求最小生成樹的Kruskal算法、求最短路徑的Dijkstra算法和Floyd算法、求二部圖最大匹配（指派問題）的匈牙利算法、求一般圖最大匹配的Edmonds“花”算法、求網(wǎng)絡(luò)最大流和最小割的算法等。

求最小生成樹的Kruskal算法

由于這個是大家都熟悉的，我只簡單的說說：為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小。Kruskal算法的做法就是：先構(gòu)造一個只含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

等級：職業(yè)俠客

文章：470

積分：956

門派：黑客帝國

注冊：2003-8-28

第 5 樓

求最短路徑的Dijkstra算法：

Dijkstra算法是一種解決最短路徑問題的非常有效的算法，時間復(fù)雜度為

O(│V│2)，下面是一段精確的描述（本段引自MIT的課程主頁，不翻譯了，保持原作）中文描述一般的書上都會有：

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

求二部圖最大匹配（指派問題）的匈牙利算法：

談匈牙利算法自然避不開Hall定理，即是：對于二部圖G，存在一個匹配M，使得X的所有頂點關(guān)于M飽和的充要條件是：對于X的任意一個子集A，和A鄰接的點集為T(A)，恒有：

│T(A)│ >= │A│

匈牙利算法是基于Hall定理中充分性證明的思想，其基本步驟為：

1．任給初始匹配M；

2．若X已飽和則結(jié)束，否則進行第3步；

3．在X中找到一個非飽和頂點x0，作V1 ← {x0}, V2 ← Φ；

4．若T(V1) = V2則因為無法匹配而停止，否則任選一點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ò)最大流和最小割的標號算法：

給定一個有向圖G=(V,E)，把圖中的邊看作管道，每條邊上有一個權(quán)值，表示該管道的流量上限。給定源點s和匯點t，現(xiàn)在假設(shè)在s處有一個水源，t處有一個蓄水池，問從s到t的最大水流量是多少。這就叫做網(wǎng)絡(luò)流問題。用數(shù)學(xué)語言描述就是：

設(shè)G=(V,E)是一個流網(wǎng)絡(luò)，設(shè)c(u, v)>＝0 表示從u到v的管道的流量上限。設(shè)s為源，t為匯。G的流是一個函數(shù)f: V×V

→R，且滿足下面三個特征：

1. 容量限制：對于所有的 u,v ∈ V, 要求f(u, v) <= c(u, v)

2. 斜對稱性：對于所有的 u,v ∈ V, 要求f(u, v) = - f(v, u)

3. 流的會話：對于所有的 u ∈ V - {s, t}，要求∑ f(u, v) = 0；v∈V

f(u,v)稱為從結(jié)點u到v的網(wǎng)絡(luò)流，它可以為正也可以為負。流 f 的值定義為：

│f│ = ∑ f(s, v)

v∈V

即從源出發(fā)的所有流的總和。

最大流問題就是找出給定流網(wǎng)絡(luò)的最大流。網(wǎng)絡(luò)流問題可以歸結(jié)為一類特殊的線性規(guī)劃問題。

尋找最大流的基本方法是Ford-Fulkerson方法，該方法有多種實現(xiàn)，其基本思想是從某個可行流F出發(fā)，找到關(guān)于這個流的一個可改進路經(jīng)P，然后沿著P調(diào)整F，對新的可行流試圖尋找關(guān)于他的可改進路經(jīng)，如此反復(fù)直至求得最大流?，F(xiàn)在要找最小費用的最大流，可以證明，若F是流量為V(F)的流中費用最小者，而P是關(guān)于F的所有可改進路中費用最小的可改進路，則沿著P去調(diào)整F,得到的可行流F'一定是流量為V(F')的所有可行流中的最小費用流。這樣，當(dāng)F是最大流時候，他就是所要求的最小費用最大流。

注意到每條邊的單位流量費用B(i,j)≥0，所以F=0必是流量為0的最小費用流，這樣總可以

從F=0出發(fā)求出最小費用最大流。一般的，設(shè)已知F是流量V(F)的最小費用流，余下的問題就是如何去尋找關(guān)于F的最小費用可改進路。為此我們將原網(wǎng)絡(luò)中的每條弧變成兩條方向相反的弧：

1。前向弧，容量C和費用B不變，流量F為0；

2。后向弧，容量C為0，費用為-B，流量F為0；

每一個頂點上設(shè)置一個參數(shù)CT，表示源點至該頂點的通路上的費用和。如果我們得出一條關(guān)于F的最小費用可改進路時，則該路上的每一個頂點的CT值相對于其它可改進路來說是最小的。每一次尋找最小費用可改進路時前，源點的CT為0，其它頂點的CT為+∞。

設(shè)cost為流的運輸費用，初始時由于F=0,則cost=0,我們每求出一條關(guān)于F的最小費用可改進路，則通過cost ← cost +

∑B(e)*d, （其中e∈P,d為P的可改進量）來累積流的運輸費用

的增加量。顯然，當(dāng)求出最小費用最大流時，cost便成為最大流的運輸費用了。

另外設(shè)置布爾變量break為最小費用可改進路的延伸標志，在搜索了網(wǎng)絡(luò)中的每一個頂點后

，若break=true表示可改進路還可以延伸，還需要重新搜索網(wǎng)絡(luò)中的頂點；否則說明最小費

用的可改進路已經(jīng)找到或者最大流已經(jīng)求出。

下面是算法的偽代碼：

cost ← 0;

repeat

可改進路撤空；

設(shè)源點的CT值為0并進入可改進路；

repeat

break ← false;

for u ←1 to N do

begin

分析U出發(fā)的所有弧;

if (的流量可改進）and(源點至U有通路)and(U的CT值+的費用 < V的CT值) then

begin

break ← true;

V的CT值 ← U的CT值+的費用；

V進入可改進路經(jīng)并為之標號；

end if

end for

until break=false

if 匯點已標號 then

begin

從匯點出發(fā)倒向修正可改進路的流量；

cost ← cost + ∑B(e)*d（其中e∈P,d為P的可改進量）；

end if

until 匯點未標號；

可見，上述的算法和求最大流的Edmonds-Karp標號算法幾乎一樣，因為這兩種算法都使用寬度優(yōu)先搜索來來尋找增廣路徑，所以復(fù)雜度也相同，都是O(VE)，其中V是節(jié)點數(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

等級：職業(yè)俠客

文章：470

積分：956

門派：黑客帝國

注冊：2003-8-28

第 6 樓

貪心法與擬陣：

貪心法是求解關(guān)于獨立系統(tǒng)組合優(yōu)化問題的一種簡單算法，求最小生成樹的Kruskal算法就是一種貪心算法。但是貪心法并不總能找到最優(yōu)獨立集。貪心法能求得最優(yōu)獨立集的充分必要條件是L為一個擬陣。事實上，求最大生成樹是關(guān)于擬陣的組合優(yōu)化問題，而二部圖的所有匹配構(gòu)成的獨立系統(tǒng)U不是擬陣。

貪心法的基本思路是：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當(dāng)達到某算法中的某一步不能再繼續(xù)前進時，算法停止。

該算法存在問題：

1. 不能保證求得的最后解是最佳的；

2. 不能用來求最大或最小解問題；

3. 只能求滿足某些約束條件的可行解的范圍。

實現(xiàn)該算法的過程：

從問題的某一初始解出發(fā)；

while 能朝給定總目標前進一步 do

　　求出可行解的一個解元素；

由所有解元素組合成問題的一個可行解；

窮舉搜索：

組合算法要解決的問題只有有限種可能，在沒有跟好算法時總可以用窮舉搜索的辦法解決，即逐個的檢查所有可能的情況?？梢韵胂?，情況較多時這種方法極為費時。實際上并不需要機械的檢查每一種情況，常常是可以提前判斷出某些情況不可能取到最優(yōu)解，從而可以提前舍棄這些情況。這樣也是隱含的檢查了所有可能的情況，既減少了搜索量，又保證了不漏掉最優(yōu)解。這方面怒火之炮寫過文章，我認為沒必要敖述了。

分支限界法：

這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。

算法思想：分枝定界（branch and

bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當(dāng)一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結(jié)束。

有兩種常用的方法可用來選擇下一個E-節(jié)點（雖然也可能存在其他的方法）：

1) 先進先出（F I F O）即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活

節(jié)點表的性質(zhì)與隊列相同。

2) 最小耗費或最大收益法在這種模式中，每個節(jié)點都有一個對應(yīng)的耗費或收益。如果查找

一個具有最小耗費的解，則活節(jié)點表可用最小堆來建立，下一個E-節(jié)點就是具有最小耗費

的活節(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點表，下一個

E-節(jié)點是具有最大收益的活節(jié)點。

動態(tài)規(guī)劃：

動態(tài)規(guī)劃(dynamic programming)是運籌學(xué)的一個分支，是求解決策過程(decision

process)最優(yōu)化的數(shù)學(xué)方法。20世紀50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究

多階段決策過程(multistep decision process)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principle of

optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。1957年出版了他的名著Dynamic

Programming，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。

一般來說，只要問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了

子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。

由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的

(即不包含公共的子子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨立，(亦即各子問題可包含公共的子子問題)也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計算。

因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。

設(shè)計一個標準的動態(tài)規(guī)劃算法，通常可按以下幾個步驟進行：

1．劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干

個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)

劃求解。

2．選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示

出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。

確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因為決策和狀態(tài)轉(zhuǎn)移

有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。

所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實上，我們常常是

反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。

3．寫出規(guī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式

化表達式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較

簡單的。動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。

分治法：

對于一個規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解

決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。

任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當(dāng)n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當(dāng)n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當(dāng)困難的。分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

如果原問題可分割成k個子問題，1 < k ≤ n

，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。

其基本步驟是：

分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；

解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；

合并：將各個子問題的解合并為原問題的解。

它的一般的算法設(shè)計模式如下：

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時，問題已

容易直接解出，不必再繼續(xù)分解。ADHOC(P)是該分治法中的基本子算法，用于直接

解小規(guī)模的問題P。因此，當(dāng)P的規(guī)模不超過n0時，直接用算法ADHOC(P)求解。算法

MERGE(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1 ,P2 ,...

,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解。

根據(jù)分治法的分割原則，原問題應(yīng)該分為多少個子問題才較適宜？各個子問題的規(guī)

模應(yīng)該怎樣才為適當(dāng)？這些問題很難予以肯定的回答。但人們從大量實踐中發(fā)現(xiàn)，

在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。換句話說，將一個問題分

成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取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è)計是一門藝術(shù)，需要高度的技巧和靈感。算法分析的任務(wù)是分析算法的優(yōu)劣，算法分析的任務(wù)是分析算法的優(yōu)劣，主要是討論算法的時間復(fù)雜性和空間復(fù)雜性。它的理論基礎(chǔ)是組合分析，包括計數(shù)和枚舉。計算復(fù)雜性理論，特別是NP完全性理論，與組合算法是緊密相關(guān)的。NP完全性概念的提出，正是為了刻畫包括旅行商問題、圖著色問題、圖著色問題、整數(shù)規(guī)劃等一大批組合問題的計算難度。計算復(fù)雜性理論研究算法在時間和空間限制下的能力以及問題的難度，使組合算法的研究有了更加清晰的框架，將組合算法的研究提高到一個新的水平。

----------------------------------------------

plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);