算法設計方法的分類及經典算法

黃友亮

簡單來說，所謂算法就是定義良好的計算過程，他取一個或一組值作為輸入，并產生一個或者一組值作為輸出。亦即，算法就是一系列的計算步驟，用來將輸入數據轉換為輸出結果。

我們還可以將算法看作一種工具，用來解決一個具有良好規格說明的計算問題。有關該問題的表述可以用通用語言，來規定所需要的輸入/輸出關系。與之對應的算法則描述了一個特定的計算過程，用于實現這一輸入/輸出關系。

計算機科學經過幾十年的發展，孕育出許多算法設計的方法以及運用這些方法設計的算法，他們廣泛運用于計算機研究領域以及計算機意外的現實生活中的各個領域。其中，算法設計的方法包含有一下幾類：

一、分治法

有很多算法在結構上是遞歸的：為了解決一個給定的問題，算法要一次或多次地遞歸調用其自身來解決相關的子問題。這些算法通常采用分治策略：將問題劃分成n個規模較小而結構與原問題相似的子問題;遞歸地解決這些iwenti，然后再合并其結果，就得到原問題的解。

分治模式在每一層遞歸上都有三個步驟：

分解（Divide）：將原問題分解成一系列子問題;

解決（Conquer）：遞歸地解決各子問題。若子問題足夠小，則直接求解;

合并（Combine）：將子問題的結果合并成原問題的解。

﹒分治法的經典算法——合并排序（merge sort）。

合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。合并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，得到完全有序的序列;即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表

合并排序直觀地操作如下：

分解：將n個元素分成n/2個元素的子序列;

解決：用合并排序法對兩個子序列遞歸地排序;

合并：合并兩個已排序的子序列以得到排序結果。

在對子序列排序時，其長度為1時遞歸結束。單個元素被視為是已排好序的。

合并排序的關鍵步驟在于合并步驟中的合并兩個已排序子序列。為做合并，引入一個輔助過程MERGE（A，p，q，r），其中A是個數組，p、q和r是下標，滿足p<=q

二、代換法

代換法常用于解遞歸式。為解釋代換法，先引入遞歸式的概念。遞歸式是一組等式或不等式，它所描述的函數是用在更小的輸入下該函數的值來定義的。

用代換法解遞歸式需要兩個步驟：

1）猜測解的形式。

2）用數學歸納法找出使解真正有效的常數。

“代換法“這一名稱源于當歸納假設用較小值時，用所猜測的值代替函數的解。這種方法很有效，但是只能用于解的形式很容易猜的情形。

不幸的是，并不存在通用的方法來猜測遞歸式的正確解。這種猜測需要經驗，有時甚至是創造性的。值得慶幸的是，還有一些試探法可以幫助做出好的猜測。

有時，我們或許能夠猜出遞歸式解的漸進界，但卻會在歸納證明時出現一些問題。通常，問題出在歸納假設不夠強，無法證明其準確的界。遇到這種情況時，可以去掉一個低階項來修改所猜的界，以使證明順利進行。

代換法亦是一種經典的解決遞歸問題的算法。

三、隨機化

隨機化算法是這樣一種算法，在算法中使用了隨機函數，且隨機函數的返回值直接或者間接的影響了算法的執行流程或執行結果。隨機化算法基于隨機方法，依賴于概率大小。

首先引入概率分析（probabilistic analysis），概率分析是在問題的分析紅應用概率技術。大多數情況下，我們使用概率分析來分析一個算法的運行時間。有時候用它分析其他的亮。為了進行概率分析，必須使用關于輸入分布的知識或者對其做的假設。然后分析算法，計算出一個期望的運行時間。這個期望通過對所有可能的輸入分布算出。因此實際上是將所有能輸入的運行時間做平均。在確定輸入的分布時必須非常小心。對于有些問題，我們隊所有可能的輸入集合可以做某種設定，也可以講概率分析作為一種手段來設計高效的算法，并加深對問題的認識。對于其他的一些問題，可能無法描述一個合理的輸入分布，此時就不能使用概率分析方法。

為了利用概率分析，需要了解關于輸入分布的一些情況。在許多情況下，我們對輸入分布知之甚少。即使知道關于輸入分布的某些信息，從計算上來說，可能也無法對這紅分布知識建立模型。然而，通過使一個算法中某些部分的行為隨機化，就常常可以利用概率和隨機性作為算法設計和分析的工具。

隨機化的經典算法——隨機算法（randomized algorithm）。

以經典的雇用問題為例，在雇用問題中，看起來應聘者好像是以隨機的順序出現的，但是我們無法知道這是否正確。因此，為了設計雇用問題的一個隨機算法，必須對面試應聘者的次序有更大的控制。假設雇用代理有n個應聘者，而且實現給我們一份應聘者的名單，我們每天隨機地選擇其中一個來面試。雖然我們不了解任何關于應聘者的事項（除了他們名字），我們已經做了一個顯著的改變。我們控制了應聘者的來到過程且加強了隨機次序，而不是依賴于隨機次序到達這個猜測。

四、動態規劃（dynamic programming）

和分治法一樣，動態規劃是通過組合子問題的解而解決整個問題的。分治算法是將問題分成一些獨立的子問題，遞歸地求解各子問題，然后合并子問題的解而得到原問題的解，與此不同，動態規劃適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題。在這種情況下，若用分治法則會做許多不必要的工作，即重復地求解公共子子問題。動態規劃算法對每個子子問題只求一次，將其結果保存在一張表中，從而避免每次遇到各個子問題時重新計算答案。

動態規劃通常應用于最優化問題。此類問題可能有很多種可行解。每個解有一個值，而我們希望找出一個具有最優（最大或最小）值得解。稱這樣的解為該問題的“一個”最優解（而不是“確定的”最優解），因為可能存在多個最優值的解。

動態規劃算法的設計可以分為以下4個步驟：

1）描述最優解的結構。

2）遞歸定義最優解的值。

3）按自底向上的方式計算最優解的值。

4）由計算出的結果構造一個最優解。

動態規劃的經典算法——最優二叉樹算法。

最優二叉樹的實現目的是從已給出的目標帶權結點（單獨的結點）經過一種方式的組合形成一棵樹.使樹的權值最小。

（1）由給定的n個權值{W1，W2，…，Wn}構造n棵只有一個葉結點的二叉樹，從而得到一個二叉樹的集合F={T1，T2，…，Tn};

（2）在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和;

（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中;

（4）重復（2）（3）兩步，當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

（作者單位：武警警官學院訓練基地信息技術教研室）