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

基本概念：

把一個復雜的問題分成兩個或更多的相同的或相似的子問題崇猫。再把子問題分成更小的子問題。直到最后子問題可以簡單的解決曼玩。

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

分治法適用范圍情況：

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

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

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

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

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

分治法的基本步驟：

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

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

一般設計模式：

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

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

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）

分治法的復雜性分析

總結(jié)

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

2.找到求解的遞歸函數(shù)式后（各種規(guī)墓卮或因子）侥涵，設計遞歸程序即可。

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

基本概念

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

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

動態(tài)規(guī)劃解決問題多數(shù)有重疊子問題這個特點，為減少重復計算径荔，對每一個子問題只解一次督禽，將其不同階段的不同狀態(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)第岖，只與當前的狀態(tài)有關(guān)。

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

求解基本步驟

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

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

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

（3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系坐梯，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)徽诲。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫出。但一般是根據(jù)前后的兩個階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程的谎替。

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

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

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

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

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

回溯法解題的一般步驟

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

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

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

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

算法框架

（1）問題框架

設問題的解是一個n維向量（a1绪囱，a2测蹲。。an）鬼吵，約束條件是ai之間滿足某種條件扣甲，記為f（ai）

非遞歸回溯框架

int a[n],i;

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

i=1;

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

｛

? ? ? ? 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;

}

｝

}

}

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

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

（1）分支搜索算法

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

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

分支限界法的一般過程

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

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

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

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

五大常用算法之貪心算法

基本概念

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

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

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

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

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

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

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

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

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

while（朝給定總目標前進一步）｛

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

｝

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

例子

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

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

A B C D E F G

重量 35 30 60 50 40 10 25

價值 10 40 30 50 35 40 30

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

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

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

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

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

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

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

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

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