五大常用算法之一：分治算法

基本概念：

把一個復(fù)雜的問題分成兩個或更多的相同的或相似的子問題。再把子問題分成更小的子問題。直到最后子問題可以簡單的解決。

分成的子問題與原問題形式相同，并且互相獨立，遞歸的解決這些子問題。然后將子問題的解合并得到原問題的較小模式。這就為使用遞歸技術(shù)提供了方便。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中。

分治法適用范圍情況：

1）該問題規(guī)?？s小到一定程度就可以輕易解決

2）該問題可以分解為若干個規(guī)模較小相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

3）利用該問題分解出來的子問題的解可以合并為該問題的解。

4）該問題所分解出的各個子問題是相互獨立的。不包含公共子問題。

如果第三條和第四條不滿足，分治法要做許多不必要的方法，需要使用動態(tài)規(guī)劃法較好。

分治法的基本步驟：

step1：分解問題：分成規(guī)模較小，相互獨立，與原問題形式相同的子問題。

step2：若子問題規(guī)模較小容易解決直接解決，否則遞歸的解各個子問題。

一般設(shè)計模式：

Divider-and-Conquer(P)//表示問題的規(guī)模

1.if |p|<n ?//當(dāng)問題小于一個閾值，就可以直接解決了

2.then return (Adhoc(p))

3.將p分解為較小的子問題p1,p2,...pk//否則繼續(xù)分解

4.for i- 1 to k//分解每一個問題帶進方法去解

5.do yi Divide-and-Conquer(Pi)遞歸解決Pi

6.T - Merge(y1,y2,..yk)合并子問題

7.return （T）

分治法的復(fù)雜性分析

總結(jié)

1.一定是要找到最小規(guī)模的解決辦法

2.找到求解的遞歸函數(shù)式后（各種規(guī)?；蛞蜃樱?，設(shè)計遞歸程序即可。

五大常用算法之二：動態(tài)規(guī)劃算法

基本概念

每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策的序列就是就是在變化的狀態(tài)中產(chǎn)生出來的。所以，這種多階段最優(yōu)化決策解決問題的過程叫動態(tài)規(guī)劃。

在思想上與分治法類似，將待求解問題分為若干個子問題，按順序求解子階段，前一子問題的解為后一子問題的求解提供了有用的休息。子啊求解任一子問題時，可以列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟其舍棄其它局部解。依次解決各子問題。最后一個子問題就是初始問題的解。

動態(tài)規(guī)劃解決問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。與分治法最大的差異是：適合于動態(tài)規(guī)劃法求解的問題，經(jīng)分解后問題往往不是相互獨立的

適用的情況

1）最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題也是最優(yōu)的，也就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

2）無后效性：某個階段一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前的狀態(tài)有關(guān)。

動態(tài)規(guī)劃算法最大的優(yōu)勢，就是解決子問題之間重疊的問題。

求解基本步驟

處理的是一個多階段決策問題，一般是由初始狀態(tài)開始，對中間階段決策的選擇，達到結(jié)束時，這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線。

（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定是要有序的或者是可排序的。否則問題就無法求解。

（2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的客觀情況用不同的狀態(tài)表示出來，當(dāng)然狀態(tài)的選擇要滿足無后效性。

（3）確定決策并寫出狀態(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)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程的。

（4）尋找邊界條件：狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

五大常用算法之三：回溯法

在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點時，要先判斷該結(jié)點是否包含問題的解，如果包含，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解，則逐層向其祖先結(jié)點回溯。（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）。

若用回溯法求問題的所有解時，要回溯到根，且根結(jié)點的所有可行的子樹都要已被搜索遍才結(jié)束。

而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。

回溯法解題的一般步驟

（1）針對所有問題。確定問題的解空間。

首先應(yīng)明確定義問題的解空間，問題的解空間應(yīng)至少包含問題的一個（最優(yōu)）解。

（2）確定結(jié)點的擴展搜索規(guī)則

以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

算法框架

（1）問題框架

設(shè)問題的解是一個n維向量（a1，a2。。an），約束條件是ai之間滿足某種條件，記為f（ai）

非遞歸回溯框架

int a[n],i;

初始化數(shù)組a[];

i=1;

while(i>0有路可走，并且未達目標(biāo))

｛

? ? ? ? if(i>n){

? ? ? ? ? ?搜索到一個解，輸出；

}else{

a[i]第一個可能得值

while（a[i]在不滿足約束條件且在搜索空間內(nèi)）｛

? ? ? ? ? a[i]下一個可能的值

｝

}

｝

遞歸的算法框架

一般情況下使用遞歸函數(shù)來實現(xiàn)回溯法比較簡單，其中i為搜索的深度。

int a[n];

try(int i){

if(i>n)

輸出結(jié)果；

else{

? ? ? ? for(j=下界；j<=上界；j=j+1)//枚舉i所有可能得路徑

｛

? ? ? ? ?if(fun(j)){

? ? ? ? ? a[i]=j;

}

｝

}

}

五大常用算法之四：分支限界法

分支限界法與回溯法類似，但是回溯法是求解目標(biāo)中所有滿足約束條件的解，而分支限界法是找出滿足約束條件的一個解，最優(yōu)。

（1）分支搜索算法

會有幾種不同的分支搜索方式。

FIFO搜索，LIFO搜索，優(yōu)先隊列式算法搜索。

分支限界法的一般過程

在每一活結(jié)點出，計算一個函數(shù)值（限界），并根據(jù)這些已計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的節(jié)點作為擴展節(jié)點。

回溯法和分支限界法的一些區(qū)別

回溯法深度優(yōu)先搜索堆?；罱Y(jié)點的所有可行子節(jié)點被遍歷后，才被從棧中彈出找出滿足約束條件的所有解。

分支限界法廣度優(yōu)先或最小消耗優(yōu)先搜索隊列，優(yōu)先隊列每個結(jié)點只有一次成為活結(jié)點的機會找出滿足約束條件的一個解或特定意義下的最優(yōu)解。

五大常用算法之貪心算法

基本概念

所謂貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇，不從整體最優(yōu)考慮，做出的只是某種意義上的局部最優(yōu)解。

它不具有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇，貪心算法不是對所有問題都能得到整體最優(yōu)解。選擇的貪心策略必須具備無后效性，即某個狀態(tài)以后的狀態(tài)不會影響到以前的狀態(tài)。所以對采用的貪心策略一定要仔細分析是否滿足無后效性。

建立數(shù)學(xué)模型來描述問題。

把求解的問題分成若干個子問題。

對每一子問題求解，得到子問題的局部最優(yōu)解。

把子問題的解局部最優(yōu)解合成原來解問題的一個解。

貪心策略使用的前提是，局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。

貪心算法的實現(xiàn)框架

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

while（朝給定總目標(biāo)前進一步）｛

利用可行的決策，求出可行解的一個解元素；

｝

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

例子

[背包問題]有一個背包，背包容量是M=150.有7個物品，物品可以分割成任意大小。

要求盡可能讓裝入背包中的物品總價值最大，但不能超過容量。

A B C D E F G

重量 35 30 60 50 40 10 25

價值 10 40 30 50 35 40 30

分析：目標(biāo)函數(shù)：E pi最大

約束條件：E wi<=M(M=150)

(1)根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)

(2)每次挑選所占重量最小的物品裝入是否能的到最優(yōu)

每次挑選單位重量價值最大的物品，稱為解本題的策略。雖然貪心算法經(jīng)過證明之后，很高效，并且簡單易行，但是它必須經(jīng)過證明才能真正運用到題目的算法中去。

一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由貪心策略中存在的子問題最優(yōu)解得來的。對于例題中的幾種貪心策略，都是無法成立的。

五大常用算法之三：回溯法

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不再滿足求解條件時，就回溯返回，查找別的路徑。

從根節(jié)點出發(fā)深度搜索解空間樹，當(dāng)探索到某一點時，先判斷該節(jié)點是否包含問題的解，如果包含，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解