黃友亮

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

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

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

一、分治法

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

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

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

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

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

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

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

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

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

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

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

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

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

二、代換法

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

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

1）猜測解的形式。

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

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

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

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

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

三、隨機化

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

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

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

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

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

四、動態(tài)規(guī)劃（dynamic programming）

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

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

動態(tài)規(guī)劃算法的設計可以分為以下4個步驟：

1）描述最優(yōu)解的結構。

2）遞歸定義最優(yōu)解的值。

3）按自底向上的方式計算最優(yōu)解的值。

4）由計算出的結果構造一個最優(yōu)解。

動態(tài)規(guī)劃的經典算法——最優(yōu)二叉樹算法。

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

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

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

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

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

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