算法設(shè)計(jì)方法的分類及經(jīng)典算法

黃友亮

簡(jiǎn)單來(lái)說(shuō)，所謂算法就是定義良好的計(jì)算過(guò)程，他取一個(gè)或一組值作為輸入，并產(chǎn)生一個(gè)或者一組值作為輸出。亦即，算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)換為輸出結(jié)果。

我們還可以將算法看作一種工具，用來(lái)解決一個(gè)具有良好規(guī)格說(shuō)明的計(jì)算問(wèn)題。有關(guān)該問(wèn)題的表述可以用通用語(yǔ)言，來(lái)規(guī)定所需要的輸入/輸出關(guān)系。與之對(duì)應(yīng)的算法則描述了一個(gè)特定的計(jì)算過(guò)程，用于實(shí)現(xiàn)這一輸入/輸出關(guān)系。

計(jì)算機(jī)科學(xué)經(jīng)過(guò)幾十年的發(fā)展，孕育出許多算法設(shè)計(jì)的方法以及運(yùn)用這些方法設(shè)計(jì)的算法，他們廣泛運(yùn)用于計(jì)算機(jī)研究領(lǐng)域以及計(jì)算機(jī)意外的現(xiàn)實(shí)生活中的各個(gè)領(lǐng)域。其中，算法設(shè)計(jì)的方法包含有一下幾類：

一、分治法

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

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

分解（Divide）：將原問(wèn)題分解成一系列子問(wèn)題;

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

合并（Combine）：將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。

﹒分治法的經(jīng)典算法——合并排序（merge sort）。

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

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

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

解決：用合并排序法對(duì)兩個(gè)子序列遞歸地排序;

合并：合并兩個(gè)已排序的子序列以得到排序結(jié)果。

在對(duì)子序列排序時(shí)，其長(zhǎng)度為1時(shí)遞歸結(jié)束。單個(gè)元素被視為是已排好序的。

合并排序的關(guān)鍵步驟在于合并步驟中的合并兩個(gè)已排序子序列。為做合并，引入一個(gè)輔助過(guò)程MERGE（A，p，q，r），其中A是個(gè)數(shù)組，p、q和r是下標(biāo)，滿足p<=q

二、代換法

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

用代換法解遞歸式需要兩個(gè)步驟：

1）猜測(cè)解的形式。

2）用數(shù)學(xué)歸納法找出使解真正有效的常數(shù)。

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

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

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

代換法亦是一種經(jīng)典的解決遞歸問(wèn)題的算法。

三、隨機(jī)化

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

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

為了利用概率分析，需要了解關(guān)于輸入分布的一些情況。在許多情況下，我們對(duì)輸入分布知之甚少。即使知道關(guān)于輸入分布的某些信息，從計(jì)算上來(lái)說(shuō)，可能也無(wú)法對(duì)這紅分布知識(shí)建立模型。然而，通過(guò)使一個(gè)算法中某些部分的行為隨機(jī)化，就常常可以利用概率和隨機(jī)性作為算法設(shè)計(jì)和分析的工具。

隨機(jī)化的經(jīng)典算法——隨機(jī)算法（randomized algorithm）。

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

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

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

動(dòng)態(tài)規(guī)劃通常應(yīng)用于最優(yōu)化問(wèn)題。此類問(wèn)題可能有很多種可行解。每個(gè)解有一個(gè)值，而我們希望找出一個(gè)具有最優(yōu)（最大或最小）值得解。稱這樣的解為該問(wèn)題的“一個(gè)”最優(yōu)解（而不是“確定的”最優(yōu)解），因?yàn)榭赡艽嬖诙鄠€(gè)最優(yōu)值的解。

動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)可以分為以下4個(gè)步驟：

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

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

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

4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解。

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

最優(yōu)二叉樹的實(shí)現(xiàn)目的是從已給出的目標(biāo)帶權(quán)結(jié)點(diǎn)（單獨(dú)的結(jié)點(diǎn)）經(jīng)過(guò)一種方式的組合形成一棵樹.使樹的權(quán)值最小。

（1）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合F={T1，T2，…，Tn};

（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和;

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

（4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。

（作者單位：武警警官學(xué)院訓(xùn)練基地信息技術(shù)教研室）