算法設(shè)計與分析 課件全套 楊紅云 第1-8章 緒論、蠻力法 - 線性規(guī)劃

計算機(jī)算法設(shè)計與分析第1章概述例1.1求兩個正整數(shù)的最大公約數(shù)方法一：利用質(zhì)因數(shù)分解法求解最大公約數(shù)，其具體步驟描述如下：（1）輸入兩個正整數(shù)a和b。（2）將a和b分別進(jìn)行質(zhì)因數(shù)分解，得到它們的所有質(zhì)因數(shù)的乘積形式。（3）將a和b中相同的所有質(zhì)因數(shù)乘積計算出來，得到的結(jié)果即為a和b的最大公約數(shù)。若a或b無質(zhì)因數(shù)（除1和該數(shù)本身外），則最大公約數(shù)為1。例1.1求任意兩個正整數(shù)的最大公約數(shù)以具體計算為例，假設(shè)需要求解的兩個整數(shù)為42和28，42=2×3×7，28=2×2×7共同的質(zhì)因數(shù)2和7，因此，42和28的最大公約數(shù)為2×7=14利用方法一可以快速求出兩個整數(shù)的最大公約數(shù)，但方法一的描述過程不能稱為一個正真意義上的算法，因為第(2)步?jīng)]有明確如何將正整數(shù)a和b進(jìn)行質(zhì)因數(shù)分解，且質(zhì)因數(shù)分解是一個NP類問題，目前尚未找到有效的解決方法。第(3)步也沒有明確定義在兩個質(zhì)因數(shù)序列中如何找到相同的質(zhì)因數(shù)元素。因此方法一描述不滿足算法的確定性和可行性。例1.1求任意兩個正整數(shù)的最大公約數(shù)方法二：利用蠻力窮舉法求解最大公約數(shù)，具體步驟描述如下：（1）輸入a和b。（2）將a和b中的較小者賦值給r。（3）若a、b除以r的余數(shù)同時等于0，轉(zhuǎn)（5），否則往下執(zhí)行（4）。（4）執(zhí)行r=r-1，轉(zhuǎn)（3）。（5）輸出r，執(zhí)行結(jié)束。主要思想：是從兩個整數(shù)中較小者開始，去逐步尋找能被兩整數(shù)同時整除的數(shù)，一旦發(fā)現(xiàn)則終止尋找，并將該數(shù)作為兩整數(shù)的最大公約數(shù)。例1.1求任意兩個正整數(shù)的最大公約數(shù)r=2842%28=14,28%28=0,r=28-1=2742%27=15,28%27=1,r=27-1=2642%26=16,28%26=2,r=26-1=2542%25=17,28%25=3,r=25-1=2442%24=18,28%24=4,r=24-1=2342%23=19,28%23=5,r=23-1=2242%22=20,28%22=6,r=22-1=2142%21=0,28%21=7,r=21-1=2042%20=2,28%20=8,r=20-1=1942%19=4,28%19=9,r=19-1=1842%18=6,28%18=10,r=18-1=1742%17=8,28%17=11,r=17-1=1642%16=10,28%16=12,r=16-1=1542%15=12,28%15=13,r=15-1=1442%14=0,28%14=0輸出r，結(jié)果為14。以具體計算為例，設(shè)a=42和b=28，則計算過程為：例1.1求任意兩個正整數(shù)的最大公約數(shù)在a=42，b=28的情況下，窮舉法運行了15步才計算出結(jié)果。方法二窮舉法非常簡單，計算過程易于理解，但窮舉法的效率非常低。例1.1求任意兩個正整數(shù)的最大公約數(shù)方法三：利用輾轉(zhuǎn)相除法（也稱歐幾里得算法）求解最大公約數(shù)，具體步驟描述如下：（1）輸入兩個整數(shù)a和b。（2）若a<b則將a，b的值互換，以保持a是兩個整數(shù)中較大者，b為較小者。（3）將a除以b的余數(shù)賦值給r，若余數(shù)r等于0，則執(zhí)行（5），否則往下執(zhí)行（4）（4）將除數(shù)b賦值給a，將余數(shù)r賦值給b，轉(zhuǎn)（3）重復(fù)執(zhí)行（5）b為所求最大公約數(shù)，輸出b，執(zhí)行結(jié)束。例1.1求任意兩個正整數(shù)的最大公約數(shù)以具體計算為例，設(shè)a=42和b=28，則計算過程為：r=42%28=14,a=28,b=14r=28%14=0輸出b，結(jié)果為14。在a=42，b=28的情況下，輾轉(zhuǎn)相除法只運行了2步就計算出結(jié)果。例1.1求任意兩個正整數(shù)的最大公約數(shù)算法：輾轉(zhuǎn)相除法;輸入：兩個正整數(shù)a,b;

輸出：最大公約數(shù)Max_common_divisor(a,b)beginifa<bthena與b互換endramodbwhiler≠0doab,br,ramodbendprintbend計算機(jī)算法設(shè)計與分析第一章緒論一個快遞小哥從快遞中心點出發(fā)，到周邊四個小區(qū)送快遞，要求經(jīng)過每個小區(qū)且只能每個小區(qū)僅經(jīng)過一次，最后回到快遞中心點。問快遞小哥應(yīng)如何安排派送路線較好？例1.3快遞員路線安排問題起

終ABCDEA03456B30265C42043D56405E65350（1）問題分析與問題抽象，這是一個典型的TSP問題將小區(qū)抽象為下圖的頂點，兩個小區(qū)之間有路直達(dá)，則對應(yīng)的兩個頂點之間有邊關(guān)聯(lián)，邊的權(quán)值為兩個小區(qū)之間的距離。則將快遞員路線安排問題抽象為從頂點A(設(shè)A為快遞中心)出發(fā)經(jīng)過圖中其余頂點后回到頂點A的最短簡單回路問題。例1.3快遞員路線安排問題3365456542EBDCA（2）數(shù)學(xué)建模：例1.3快遞員路線安排問題3365456542EBDCA（3）方法一蠻力法：列出每一條可供選擇的路線，計算出每條路線的距離長度，最后從中選擇出一條最短路線。最短路程為：A-->B-->C-->E-->D-->A或者A-->D-->E-->C-->B-->A，最短路徑長度為:18。例1.3快遞員路線安排問題3365456542EBDCA（3）蠻力法算法效率分析：使用蠻力法列舉除出發(fā)小區(qū)外所有小區(qū)的排列，然后選取路徑最短的路線。n-1個小區(qū)的排列數(shù)為(n-1)!，當(dāng)n=20時，遍歷路線總數(shù)約為1.216×1017，計算機(jī)以每秒1000萬條路線的檢索速度計算，則約需要386年才能完成。故蠻力法的時間復(fù)雜度太高，當(dāng)頂點數(shù)過多時并不適用。例1.3快遞員路線安排問題（3）方法二貪心法：每次在選擇下一個小區(qū)時，只考慮當(dāng)前情況。在沒有經(jīng)過的小區(qū)中，選擇距離當(dāng)前小區(qū)最近的一個，直到經(jīng)過所有小區(qū)，最后回到快遞中心。A例1.3快遞員路線安排問題3365456542EBDCA貪心法的優(yōu)點是效率很高，只要n-1步判斷就能得到結(jié)果。但缺點是不一定能找到問題的最優(yōu)解。算法：貪心法—偽代碼描述輸入：小區(qū)數(shù)量n，鄰接矩陣e[i,j]，頂點v[i]，出發(fā)小區(qū)編號go_city，index當(dāng)前小區(qū)編號。輸出：最短路線上的頂點信息，最短路徑長度min_l。Greedy(index):beginfori

1tondo ifi不是出發(fā)頂點go_citythen forj

1tondo if沒有經(jīng)過小區(qū)jthen

篩選與當(dāng)前出發(fā)點最短的頂點，并標(biāo)記為cur_j endifendfor min_l

min_l+e[index,cur_j] index

cur_j//從出發(fā)點cur_j，繼續(xù)下一步求解

并置cur_j頂點為經(jīng)過標(biāo)記

endifend for

min_lmin_l+e[index,go_city]//加上最后一個小區(qū)到go_city小區(qū)的距離end例1.3快遞員路線安排問題計算機(jī)算法設(shè)計與分析第一章概述1.4.1算法的效率分析目的評估算法體現(xiàn)算法運行時所需要消耗的計算機(jī)資源占用CPU的計算時間量稱為時間復(fù)雜度占用內(nèi)存的存儲空間量稱為空間復(fù)雜度算法復(fù)雜度分析一般采用事前分析方式而是不事后統(tǒng)計法算法的效率分析算法的時間復(fù)雜度T和空間復(fù)雜度S的函數(shù)：T=T(N,I)S=S(N,I)N表示問題規(guī)模，I表示算法輸入在實際應(yīng)用中，關(guān)注時間效率多于空間效率。算法時間復(fù)雜度分析評估算法時間復(fù)雜度，應(yīng)盡量做到客觀反映算法的本質(zhì)特征和屬性。所以，算法時間復(fù)雜度分析應(yīng)該要有一個不依賴于計算機(jī)硬件配置、問題規(guī)模和輸入實例的抽象表示。算法時間復(fù)雜度分析假設(shè)在一臺抽象的計算機(jī)上提供了k種元運算O1，O2，…，Ok，每個元運算執(zhí)行的時間分別為t1，t2，...，tk。元運算通常指的是算法中最基本的操作步驟，一個元運算可以是基本的算術(shù)運算（如加法、減法、乘法、除法）、比較操作、賦值操作、數(shù)組訪問或迭代循環(huán)等。算法時間復(fù)雜度分析T(N，I)表示算法在這臺抽象計算機(jī)上運行所需要的的時間，設(shè)，在算法中

元運算Oi被調(diào)用的次數(shù)為ei，ei=ei(N,I)，因此，T(N,I)一般化的表示：算法時間復(fù)雜度分析為消除公式中ti表示的元運算執(zhí)行的具體時間，不妨假設(shè)所有的元運算都在一個單位時間內(nèi)完成或者將ti抽象表示為一條執(zhí)行語句或表達(dá)式所用時間，則計算T(N,I)的工作就變?yōu)榻y(tǒng)計計算語句的頻度，從而簡化復(fù)雜度的求解。例1.4插入排序問題時間復(fù)雜度計算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個數(shù)n

輸出：升序的數(shù)組元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動元素6 j

j–17 end8 array[j+1]

key9

endend當(dāng)輸入數(shù)據(jù)為1,2,3,4,5時，語句2、3、8被執(zhí)行4次，語句5、6被執(zhí)行0次。當(dāng)輸入數(shù)據(jù)為5,4,3,2,1時，語句2、3、8被執(zhí)行4次，語句5、6被執(zhí)行10次。算法時間復(fù)雜度分析對同一個算法，運行不同的輸入實例時，算法語句執(zhí)行的次數(shù)差異明顯。實際上，在統(tǒng)計時間復(fù)雜度時，我們不可能對規(guī)模N的每一種合法輸入都去統(tǒng)計各個算法語句執(zhí)行的次數(shù)，這時就需要對輸入實例做一個合理簡化，即將輸入實例進(jìn)行特化。算法時間復(fù)雜度分析（1）最壞情況下的時間復(fù)雜度：IN是規(guī)模為N的合法輸入集合，I*是IN中使T(N,I)達(dá)到Tmax(N)的合法輸入。最壞情況下的時間復(fù)雜度就是將所有的合法輸入實例中最壞的那個輸入實例I*找出來，統(tǒng)計在輸入實例I*時算法語句執(zhí)行的次數(shù)來評估算法時間復(fù)雜度。算法時間復(fù)雜度分析（2）最好情況下的時間復(fù)雜度：I'是IN中使T(N,I)達(dá)到Tmin(N)的合法輸入，將所有的合法輸入實例中最好的那個輸入實例I'找出來，統(tǒng)計在輸入實例I'時算法語句執(zhí)行的次數(shù)來評估算法時間復(fù)雜度。算法時間復(fù)雜度分析（3）平均情況下的時間復(fù)雜度：P(I)是算法應(yīng)用中出現(xiàn)輸入實例I的概率，全部合法輸入實例的概率總和為1。平均時間復(fù)雜度是用每一個輸入實例出現(xiàn)的概率，計算其數(shù)學(xué)期望。在分析算法時間復(fù)雜度的時候，往往關(guān)注的是最壞情況下算法的時間復(fù)雜度。例1.4插入排序問題時間復(fù)雜度計算

算法：插入排序（升序排序）

輸入：數(shù)組元素array，元素個數(shù)n

輸出：升序的數(shù)組元素array

InsertSort(array,n):begin1fori

1ton–1do2key

array[i]3j

i–14whilej>=0andarray[j]>keydo5array[j+1]

array[j]//往后移動元素6 j

j–17 end8 array[j+1]

key9

endend語句2,3,8分別執(zhí)行N-1次語句5,6執(zhí)行的次數(shù)分為1,2,3，...，N-1次算法時間復(fù)雜度分析語句2,3,8分別執(zhí)行N-1次，語句5,6執(zhí)行的次數(shù)分為1,2,3，...，N-1次，所以：當(dāng)N比較大時，N2/2為主要因素，后面項為次要因素忽略次要因素，簡化時間復(fù)雜度函數(shù)的表示。計算機(jī)算法設(shè)計與分析第一章概述漸近時間復(fù)雜度分析設(shè)T(N)是算法A的時間復(fù)雜度函數(shù)，N是問題規(guī)模，N≥0，且N∈Z。當(dāng)N

∞時，T(N)

∞。對于T(N)，如果存在T'(N)，使得當(dāng)N

∞時有那么，我們就說T'(N)是算法A當(dāng)N

∞的漸近復(fù)雜度。漸近時間復(fù)雜度分析在漸近復(fù)雜度函數(shù)T'(N)中，階與T'(N)中的常數(shù)因子沒有關(guān)系，所以T'(N)可進(jìn)一步簡化，省略常數(shù)因子。例1.4中的T'(N)可取值N2即可。需要注意的是，函數(shù)簡化并不是一種精確計算復(fù)雜度的方法，而是一種近似評估的方式。例1.4中的T'(N)=N2/2+5N/2-3漸近時間復(fù)雜度分析定義1.1設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c≥0和自然數(shù)N0，使得當(dāng)N≥N0時有0≤f(N)≤cg(N)，則稱函數(shù)f(N)充分大時上有界，g(N)是f(N)的一個上界，記為f(N)=O(g(N))，即f(N)的階不高于g(N)的階，如圖所示。不是直接比較f(N)和g(N)的數(shù)值大小，O表示的只是一個充分大的上界，上界的階越低則算法時間復(fù)雜度的評估越精確，結(jié)果值越有價值N0cg(N)f(N)漸近時間復(fù)雜度分析例1.5求5n+4，n2+nlogn，2n+n2，10000的上界。n≥4時，5n+4≤6n，則5n+4=O(n)n≥1時，n2+nlogn≤2n2，則n2+nlogn=O(n2)n≥1時，2n+n2≤2*2n，則2n+n2=O(2n)對于常整數(shù)10000，算法執(zhí)行時間與問題規(guī)模無關(guān)，無論問題規(guī)模多大，算法都在固定時間內(nèi)完成。因此無論是10000還是其他任何常數(shù)輸入，它的時間復(fù)雜度是一個常數(shù)級別的復(fù)雜度，即O(1)。漸近時間復(fù)雜度分析例1.6給定多項式函數(shù)：

試證明T(n)=O(nm)。證明：設(shè)n0=1,對于任意的n，若n≥n0=1，則：存在c≥0和自然數(shù)n0=1，使得當(dāng)n≥n0時有T(n)≤cnm，故T(n)=O(nm)成立。漸近時間復(fù)雜度分析根據(jù)定義1.1，我們有如下O(n)的性質(zhì)：（1）O(f)+O(g)=O(max(f,g))；算法最復(fù)雜的部分運行時間就是算法的時間復(fù)雜度。（2）O(f)+O(g)=O(f+g)；算法中并行語句的時間復(fù)雜度等于各個語句運行時間之和。（3）O(f)×O(g)=O(f×g)；循環(huán)的時間復(fù)雜度等于循環(huán)體運行時間與循環(huán)次數(shù)的乘積。（4）O(cf(n))=O(f(n))，c∈Z+；算法的時間復(fù)雜度是運行時間函數(shù)的數(shù)量級。（5）如果g(n)=O(f(n))，則O(f)+O(g)=O(f)；算法的時間復(fù)雜度是運行時間函數(shù)的最高階。（6）f=O(f)。漸近時間復(fù)雜度分析定義1.2設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c≥0和自然數(shù)N0，使得當(dāng)N≥N0時有f(N)≥cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時下有界，且g(N)是f(N)的一個下界，記為f(N)=Ω(g(N))，即f(N)的階不低于g(N)的階，如圖所示。N0cg(N)f(N)漸近時間復(fù)雜度分析例1.8求5n+1，n2+nlogn的下界。當(dāng)n≥1時，5n+1≥5n，則5n+1=Ω(n)當(dāng)n≥1時，n2+nlogn≥n2，則n2+

nlogn

=Ω(n2)；n2+

nlogn

≥nlogn，則n2+

nlogn

=Ω(nlogn)，但nlogn≠Ω(n2)。根據(jù)定義1.2可知，n2+nlogn=Ω(n2)和n2+

nlogn

=Ω(nlogn)都成立，算法時間復(fù)雜度一般取最大下界。下界的階越高，評估越精確，結(jié)果越有價值，Ω通常也表示求解問題的最好情況下的時間復(fù)雜度。漸近時間復(fù)雜度分析定義1.3設(shè)f(N)和g(N)是正整數(shù)集上的函數(shù)。如果?c1≥0、?c2≥0和自然數(shù)N0，使得當(dāng)N≥N0時有0≤c1g(N)≤f(N)≤c2g(N)，則稱g(N)是f(N)的緊確界。記為f(N)=θ(g(N))，如圖1.7所示。若f(N)=θ(g(N))，則當(dāng)且僅當(dāng)f(n)=O(g(N))且f(N)=Ω(g(N))，也稱g(N)和f(N)同階。N0c1g(N)f(N)c2g(N)漸近時間復(fù)雜度分析例1.9

求n2+nlogn的緊確界。由例1.5和例1.8可知：n2+nlogn=O(n2)，n2+nlogn=Ω(n2)，因此n2+nlogn=θ(n2)。計算機(jī)算法設(shè)計與分析第一章概述非遞歸算法的時間復(fù)雜度分析在分析非遞歸算法時，主要遵循如下步驟：（1）確定核心操作：比如算法中的賦值、比較、算術(shù)運算、邏輯運算、變量輸入輸出等操作，一般稱為基本操作。也可以將內(nèi)層循環(huán)的若干個基本操作構(gòu)成的程序塊整體看成一個稍大一點的基本操作。（2）計算核心操作總的執(zhí)行次數(shù)：計算核心基本操作的執(zhí)行次數(shù)，一般是多項式和的形式。（3）求解其漸近解：對核心操作總執(zhí)行次數(shù)表達(dá)式進(jìn)行計算化簡，并用O(?)形式表示。非遞歸算法的時間復(fù)雜度分析例1.10查找元素t在數(shù)組a中第一次出現(xiàn)的位置，若查找失敗返回-1。分析順序查找算法時間復(fù)雜度。本算法描述中的核心操作是語句3，最好的情況下，時間復(fù)雜度T(n)=O(1)。最壞的情況是整個循環(huán)語句1執(zhí)行完畢，即語句3被執(zhí)行n次而結(jié)束，此時T(n)=O(n)非遞歸算法的時間復(fù)雜度分析例1.11查找元素t在升序數(shù)組a中第一次出現(xiàn)的位置，若查找失敗返回-1。分析二分查找算法時間復(fù)雜度。非遞歸算法的時間復(fù)雜度分析核心操作是語句3~6，最好的情況下，執(zhí)行到語句4直接結(jié)束，時間復(fù)雜度T(n)=O(1)。最壞情況是每次進(jìn)入while循環(huán)，搜索范圍a[left]~a[right]減少一半，直到最后只剩下1個元素比較最后一遍查找成功返回位置或者返回-1結(jié)束算法函數(shù)。不妨假設(shè)起始數(shù)組元素個數(shù)n=2m第1次執(zhí)行后，搜索數(shù)組范圍2m-1第2次執(zhí)行后，搜索數(shù)組范圍2m-2，...，第m次執(zhí)行后，搜索數(shù)組范圍剩下1個元素而結(jié)束。最壞情況下的程序塊總執(zhí)行次數(shù)為m次，算法時間復(fù)雜度T(n)=m=logn=O(logn)計算機(jī)算法設(shè)計與分析第一章概述遞歸算法的時間復(fù)雜度分析分析遞歸算法時間復(fù)雜度的主要步驟如下：（1）確定算法的核心操作：確定每一邏輯塊的時間復(fù)雜度，若是非遞歸的程序塊，則用非遞歸方法分析程序塊的時間復(fù)雜度；若是遞歸的程序塊，則分析遞歸程序塊的結(jié)構(gòu)，根據(jù)其問題規(guī)模遞推的形式來表示復(fù)雜度。（2）構(gòu)造時間復(fù)雜度函數(shù)的遞推方程：非遞歸程序塊的時間加上遞歸程序塊的時間。（3）求解遞歸方程和漸近階，并用O(?)表示算法時間復(fù)雜度。遞歸算法的時間復(fù)雜度分析例1.12

求n!算法描述核心操作遞歸算法的時間復(fù)雜度分析核心操作為n*FN(n-1),是一次乘法操作遞推方程：遞歸算法的時間復(fù)雜度分析例1.13

快速排序問題遞歸求解算法描述：核心操作1核心操作2遞歸算法的時間復(fù)雜度分析非遞歸程序塊的執(zhí)行次數(shù)為n-1次，最壞的情況遞歸函數(shù)語句14每次范圍為0，則遞歸函數(shù)語句15的范圍則是n-1，則快速排序問題的時間復(fù)雜度：最壞的情況快速排序問題的漸近時間復(fù)雜度為T(n)=O(n2)遞歸算法的時間復(fù)雜度分析平均情況下，不妨設(shè)兩個遞歸函數(shù)語句14,15的元素個數(shù)差不多各占一半即n/2，也不妨設(shè)n=2m，則快速排序問題的時間復(fù)雜度平均情況下的快速排序問題的漸近時間復(fù)雜度為T(n)=O(nlogn)遞歸算法的時間復(fù)雜度分析MasterTheorem主定理，遞推方程其中a≥1，b>1，且a，b為常數(shù)，則有如下結(jié)果：遞歸算法的時間復(fù)雜度分析例1.13求解遞推方程a=4，b=2，c=3，k=1；a=4>bk=2；由定理第一種情況可知，T(n)=O(n2)計算機(jī)算法設(shè)計與分析第二章

蠻力法學(xué)習(xí)目標(biāo)了解蠻力法的適用場景掌握蠻力法的設(shè)計思想掌握蠻力法解決實際問題。2.1蠻力法概述蠻力法（BruteForce），又稱暴力法、窮舉法，它遍歷解空間的所有可能解，然后一一驗證，直到找到問題的解或所有可能解都驗證完畢。該方法是一種簡單直接地解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。它完全依靠計算機(jī)的算力來直接對問題進(jìn)行求解。隨著計算機(jī)硬件技術(shù)的不斷進(jìn)步，計算機(jī)的算力也在不斷提高。蠻力法借助于計算機(jī)強(qiáng)大的計算能力就能夠解決很大一部分問題。雖然它顯得過于愚笨，但往往卻能以最簡單直接的方式來解決問題，甚至有些問題只能用蠻力法求解。2.1蠻力法概述雖然巧妙和高效的算法很少來自于蠻力法，但不應(yīng)該忽略它作為一種重要的算法設(shè)計策略的地位。主要體現(xiàn)在以下幾個方面：（1）蠻力法的使用范圍廣，幾乎沒什么限制，可以解決廣闊領(lǐng)域的各種問題。實際上，它可能是唯一一種幾乎什么問題都能解決的一般性方法。（2）對于一些重要的問題（如排序、查找、字符串匹配等）來說，規(guī)模不大時，蠻力法可以產(chǎn)生一些合理的算法。2.1蠻力法概述雖然巧妙和高效的算法很少來自于蠻力法，但不應(yīng)該忽略它作為一種重要的算法設(shè)計策略的地位。主要體現(xiàn)在以下幾個方面：（3）如果要解決的問題規(guī)模不大，從某種意義上說蠻力法是最劃算的一種算法。（4）即使計算效率通常較低，但仍可使用蠻力法解決一些小規(guī)模的問題實例。（5）蠻力法可作為研究或教學(xué)目的服務(wù)，比如可以以它作為參照標(biāo)準(zhǔn)，來衡量解決相同問題的其他算法是否更為高效，如把蠻力法作為計算最壞時間復(fù)雜度。2.2蠻力法的設(shè)計思想蠻力法本質(zhì)是先有策略地進(jìn)行窮舉，然后一一驗證。蠻力法的設(shè)計的需要從三個方面進(jìn)行：問題解的表示形式及范圍；使用何種方法將其窮舉，要求不能重復(fù)也不能遺漏；將每個列舉的可能解代入具體問題的各個條件進(jìn)行比對。這三個方面中最為核心的是第二個，也就是窮舉方法。為了避免陷入重復(fù)驗證，應(yīng)保證驗證過的可能解不再被驗證。對于線性問題來說，處理次序依次即可，而對于非線性問題，就需要用到一些特定的方法，比如樹形結(jié)構(gòu)的前序遍歷、中序遍歷和后序遍歷；圖結(jié)構(gòu)的寬度優(yōu)先搜索和深度優(yōu)先搜索等。在設(shè)計時一般都是用循環(huán)語句和判斷語句來實現(xiàn)。使用循環(huán)是枚舉所有的情況，使用判斷是驗證當(dāng)前的狀態(tài)是否滿足問題的所有條件。若滿足，則找到問題的一個解，可以結(jié)束，如需要求其他解，則繼續(xù)循環(huán)；若不滿足，則繼續(xù)循環(huán)驗證其他狀態(tài)。2.2蠻力法的設(shè)計思想2.2蠻力法的設(shè)計思想基本格式：for(循環(huán)變量x取所有可能的值){┇

if(x滿足指定的條件)

輸出x;┇}2.2蠻力法的設(shè)計思想使用蠻力法通常有如下幾種情況：搜索所有的解空間：問題的解存在于規(guī)模不大的解空間中。搜索所有的路徑：這類問題中不同的路徑對應(yīng)不同的解。直接計算：按照基于問題的描述和所涉及的概念定義，直接進(jìn)行計算。往往是一些簡單的題，不需要算法技巧的。模擬和仿真：按照求解問題的要求直接模擬或仿真即可。2.2蠻力法的設(shè)計思想編寫一個程序，輸出2～1000之間的所有完全數(shù)。完全數(shù)定義：該數(shù)的各因子（除該數(shù)本身外）之和正好等于該數(shù)本身，例如：6=1+2+3，28=1+2+4+7+14分析：解的范圍：2～1000，范圍小，適合采用蠻力法窮舉方法：依次即可條件比對：1到n/2中依次驗證是否為n的約數(shù)，如是則累加，最終判斷是否和n相等2.2蠻力法的設(shè)計思想偽代碼：PerfectNum(N)輸入：整數(shù)N，表示尋找2～N之間所有的完全數(shù)。輸出：2～N中所有的完全數(shù)forn←2toNdo

//解空間的范圍sum←1fori←2ton/2doifi整除nthensum←sum+i

//若是約數(shù)，則累加endifendforifsum=nthen

//若約數(shù)之和與原數(shù)相等，則是完全數(shù)輸出nendifendfor2.2蠻力法的設(shè)計思想C源代碼：#include<stdio.h>#include<math.h>voidPerfectNum(intN){intsum,n,i; for(n=2;n<=N;n++){

sum=1; for(i=2;i<sqrt(n);i++){ if(n%i==0){ sum+=i; if(n/i!=i)

sum+=n/i; }} if(sum==n){ printf("%d\t",n); } }}voidmain(){ PerfectNum(1000);}2.3蠻力法的典型實例蠻力法適用于很多場景，具體來說，包括這幾類：搜索所有的解空間。問題的解存在于規(guī)模不大的解空間中。解決這類問題一般是找出某些滿足特定條件或要求的解。使用蠻力法就是把所有的解都列舉出來，從中選出符合要求的解。搜索所有的路徑。這類問題中不同的路徑對應(yīng)不同的解，需要找出特定解。使用蠻力法搜索所有可能的路徑并計算路徑對應(yīng)的解，找出特定解。直接計算?；趩栴}的描述直接進(jìn)行計算。模擬和仿真。根據(jù)問題要求直接模擬或仿真。2.3.1蠻力法的典型實例——0-1背包問題1.問題描述給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的承重量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中的物品重量在不超過C的前提下，總價值最大？附加條件：在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包（1或0）。每種物品只有一份，不能將物品i裝入背包多次，也不能將物品i分割只裝入其的一部分。2.問題分析確定解的表示形式：每種物品要么裝入背包，要么不裝入背包，分別用1和0表示，總共有n種物品，因此解的表示形式為n維的0-1向量，解的范圍有2n種組合。窮舉方法：當(dāng)n比較小時，規(guī)模不大，使用蠻力法是可行的。用一個0～2n-1中的整數(shù)的二進(jìn)制形式來代表某種組合，二進(jìn)制對應(yīng)位數(shù)為1的表示裝入對應(yīng)的第i個物品。比如，假設(shè)n=5，用6=(00110)2，它的第2，3位為1，則代表裝入第2，3種物品。約束條件：裝入的物品重量和要≤背包的承重量C。目標(biāo)是在滿足條件情況下總價值最大。對于每種符合條件的物品組合其總價值可以很方便計算出來，然后判斷是否大于前面驗證過的組合物品總價值，若是，則將最大值更新，否則，最大值不變。2.3.1蠻力法的典型實例——0-1背包問題2.3.1蠻力法的典型實例——0-1背包問題3.算法實現(xiàn)KnapSack_BruteForce(W,V,n,C)輸入：n個物品的重量數(shù)組W[]，價值數(shù)組V[]，背包的承重量C輸出：背包能容下的價值最大的物品組合及總價值w←0，v←0 //包中初始沒放入任何物品，重量為0，價值為0fori←1to2n-1do //窮舉所有組合j←0temp←0whilej<ndo

if(i的第j位是1)//i的第j位為1,表示第i種組合將第j個物品裝入背包

w←w+W[j]

temp←temp+V[j]

endifendwhileifw<=C且temp>vthen //如果滿足條件，且背包中價值更大，則更新最大價值v←tempk←iendifendfor2.3.1蠻力法的典型實例——0-1背包問題#include<stdio.h>intmax_w=0,

max_v=0,

ans=-1;voidKnapSack_BruteForce(intW[],intV[],intn,intC){ intw,v,i,j,k,f,N=1<<n; for(i=1;i<N;i++){ k=i;j=n-1;

w=0;v=0; while(k!=0){ f=k&1;

w+=f*W[j];

v+=f*V[j]; j--;

k>>=1; } if(w<=C&&v>max_v){max_w=w;

max_v=v;

ans=i; } }}voidmain(){ intW[]={2,3,4,7},V[]={1,3,5,9}; intC=10; KnapSack_BruteForce(W,V,4,C); printf("max_w=%d,max_v=%d,ans=%d\n",max_w,max_v,ans);}4.算法效率分析該算法時間復(fù)雜度為，當(dāng)n的規(guī)模較小時，該算法有效。當(dāng)n較大時，蠻力法比較難以在規(guī)定時間內(nèi)得出結(jié)果。當(dāng)然上述的算法還可以優(yōu)化，比如當(dāng)某個物品組合超過承重量C時，那么包含以上組合的肯定都超過C，因此這樣的組合就不必驗證，直接跳過，這樣可以減少一些驗證，提高效率。但無論如何，蠻力法求解0-1背包問題總有局限性，其實求解該問題還有更好的方法，比如動態(tài)規(guī)劃法，這個在后續(xù)的章節(jié)里介紹。2.3.1蠻力法的典型實例——0-1背包問題2.3.2蠻力法的典型實例——全排列問題1.問題描述全排列就是一個序列所有可能的排序。例如，有1,2,3三個元素，其全排列的結(jié)果就是[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]，一共6種。根據(jù)數(shù)學(xué)公式，我們知道含有n個元素的全排列的個數(shù)為n！。所以生成全排列算法的時間復(fù)雜度不會低于O(n!)。給定正整數(shù)n，生成1～n的全排列。2.問題分析算法一：增量法。假設(shè)n=3，增量法產(chǎn)生1～3的全排列過程如下：首先初始化數(shù)列為[1]，然后將2插入到1的前后兩個位置得數(shù)列[1,2]和[2,1]，繼續(xù)將3插入以上兩個數(shù)列的3個位置得到6個數(shù)列[1,2,3]，[1,3,2]，[3,1,2]，[2,1,3]，[2,3,1]，[3,2,1]。過程如下圖所示。雖然增量法思路簡單，但需要存儲大量的中間結(jié)果，所以空間復(fù)雜度比較高。2.3.2蠻力法的典型實例——全排列問題11,21,2,31,3,23,1,22,12,1,32,3,13,2,1初始化為1將2插入各位將3插入各位2.問題分析算法二：遞歸法。對于給定的數(shù)組，先確定序列的第一個元素，剩余的序列又可以看成是一個不包含第一個元素的全排列。對剩余的序列重復(fù)這樣的操作，直到剩余序列中只一個元素為止。這樣就獲得了所有的可能序列。這是一個遞歸的過程。整個過程如下圖所示：2.3.2蠻力法的典型實例——全排列問題1231322132313213121231232133213.總結(jié)遞歸算法求全排列（蠻力法）(1)

n個元素的全排列=（一個元素作為前綴）+（剩下n-1個元素的全排列）；(2)

結(jié)束：如果只有一個元素的全排列，說明已經(jīng)排完，輸出數(shù)組；(3)

不斷將每個元素放作第一個元素，然后將這個元素作為前綴，并將其余元素繼續(xù)全排列，等到結(jié)束。出去后還需要還原數(shù)組。2.3.2蠻力法的典型實例——全排列問題2.3.2蠻力法的典型實例——全排列問題voidPerm(intarr[],intbegin,intend){//如果遍歷到begin==end，則全排列已經(jīng)做完，只需輸出即可 if(begin==end) Print(arr); //輸出整個排列，需實現(xiàn) else{

//遞歸，生成剩余元素的排列 for(inti=begin;i<=end;i++){//將當(dāng)前元素與第一個元素交換，需實現(xiàn)

Swap(arr[begin],arr[i]);//遞歸調(diào)用，保持第一個元素固定并生成其余元素的排列

Perm(arr,begin+1,end);

//進(jìn)行回溯

Swap(arr[begin],arr[i]);}}}例2.2五星填數(shù)。在五星圖案結(jié)點填上數(shù)字1~12，不包括7和11。要求每條直線上數(shù)字和相等。如圖2.3就是一個恰當(dāng)?shù)奶罘āＵ埶阉魉锌赡艿奶罘ㄓ卸嗌俜N。注意：旋轉(zhuǎn)或鏡像后相同的算同一種填法。2.3.2蠻力法的典型實例——全排列問題310121492865分析：上述問題將1～12，不包括7和11，按不同順序填入圓圈中，其實是一個以上10個數(shù)的一種排列，如果驗證5條線的數(shù)字和相等就是一種正確的填法。把所有的排列一一驗證，這樣就可以統(tǒng)計出全部正確的填法。所以該問題的核心就是一個全排列的問題。解：經(jīng)過上述的分析，整個求解過程分為3步：①寫出1～12不包括7和11的全排列；②判斷每條線上的4個數(shù)字和是否相等，若都相等則是正確的填法，其填法的計數(shù)加1；③剔除旋轉(zhuǎn)和鏡像，因為五角星旋轉(zhuǎn)和鏡像都屬于同一種填法，因此，最終應(yīng)該在全部正確的填法種數(shù)上除以10。2.3.2蠻力法的典型實例——全排列問題具體實現(xiàn)過程如下：（1）先來定義五星數(shù)組，因為全排列中沒用到數(shù)字0，所以定義數(shù)組時下標(biāo)為0的不用。intstar[]={0,1,2,3,4,5,6,8,9,10,12};//0不用（2）定義5條直線數(shù)字的和。#defineA(star[1]+star[3]+star[6]+star[9])#defineB(star[1]+star[4]+star[7]+star[10])#defineC(star[2]+star[3]+star[4]+star[5])#defineD(star[2]+star[6]+star[8]+star[10])#defineE(star[5]+star[7]+star[8]+star[9])2.3.2蠻力法的典型實例——全排列問題具體實現(xiàn)過程如下：（3）寫出1～12不包括7和11的全排列，這步借鑒前面全排列的算法。（4）驗證5條線上的數(shù)字和是否相等。if((A==B)&&(A==C)&&(A==D)&&(A==E))count++;（5）剔除旋轉(zhuǎn)和鏡像。count/=10;2.3.2蠻力法的典型實例——全排列問題2.3.3蠻力法的典型實例——串匹配問題1.問題描述在進(jìn)行文本編輯處理時，經(jīng)常會對文本內(nèi)容進(jìn)行查找工作，如Word中文本編輯的查找操作，在查找對話框中輸入需要查找的文本字符，可以精準(zhǔn)找到被查字符內(nèi)容在文本中的位置。這個問題稱為字符串匹配問題，即給定兩個串S="s1s2...sn"和T="t1t2...tm"，在主串S中查找子串T的過程，也稱為模式匹配問題，子串T又稱為模式串。2.算法設(shè)計BF（Brute-Force）串匹配算法是一種簡單直觀的字符串匹配蠻力求解算法。它的基本思想是，第一次匹配過程，主串S的第一字符與模式串T的第一個字符對齊進(jìn)行比較。若相等，則比較主串S和模式串T的后續(xù)字符。若不等，則進(jìn)行下一次匹配過程，主串S本次比較起始字符的下一個字符與模式串T的第一個字符對齊進(jìn)行比較。重復(fù)上述過程，直到進(jìn)行第k次匹配過程，主串S的第k個字符開始的m個字符與模式串T的m個字符全部相等，匹配查找成功。若主串S中字符全部比較完畢也沒有匹配成功，則匹配失敗。2.3.3蠻力法的典型實例——串匹配問題舉例說明：如主串S="abcababcabc"，模式串T="abcabc"，BF算法的匹配過程下所示。第一次匹配過程：主串和模式串第一個不等字符：s6≠t6，則i回到本次比較起始字符下一個位置2，j回到1位置。第二次匹配過程：主串和模式串第一個不等字符：s2≠t1，則i回到本次比較起始字符下一個位置3，j回到1位置。2.3.3蠻力法的典型實例——串匹配問題舉例說明：如主串S="abcababcabc"，模式串T="abcabc"，BF算法的匹配過程下所示。第三次匹配過程：主串和模式串第一個不等字符：s3≠t1，則i回到本次比較起始字符下一個位置4，j回到1位置。第四次匹配過程：主串和模式串第一個不等字符：s6≠t3，則i回到本次比較起始字符下一個位置5，j回到1位置。2.3.3蠻力法的典型實例——串匹配問題舉例說明：如主串S="abcababcabc"，模式串T="abcabc"，BF算法的匹配過程下所示。第五次匹配過程：主串和模式串第一個不等字符：s5≠t1，則i回到本次比較起始字符下一個位置6，j回到1位置。第六次匹配過程：主串和模式串完全匹配，則模式串在主串的6位置匹配成功。2.3.3蠻力法的典型實例——串匹配問題2.3.3蠻力法的典型實例——串匹配問題3.算法設(shè)計輸入：主串文本S，模式串T輸出：模式串在主串中匹配成功的位置，若不成功為-1。BFSearch(S,T)begini←1,j←1while

i<S.length

and

j<T.length

doifS[i]=T[j]theni←i+1j←j+1elsei←i-j+2j←1endifendwhileif

j=T.lengththenv←i-T.length+1elsev←-1endifreturnvend2.3.3蠻力法的典型實例——串匹配問題#include<stdio.h>#include<string.h>intBFStringMatch(char*S,char*T){inti=0,j=0;

//字符串下標(biāo)從0開始while(S[i]!='\0'&&T[j]!='\0')

if(S[i]==T[j]){i++;

j++; }else{

i=i-j+1;

//主串回溯的位置

j=0;

//模式串回溯位置總是從第一個字符開始 } if(j==strlen(T)) returni-j; else

return

-1;}voidmain(){ charS[]="abcababcabc"; charT[]="abcabc"; printf("模式串T在主串S中的位置：%d\n",BFStringMatch(S,T)); }4.算法效率分析設(shè)主串長度為n，模式串長度為m，最壞情況下為前n-m次匹配過程都是主串與模式串匹配到模式串的最后一個位置出現(xiàn)不等，即每次匹配過程都比較了m次發(fā)現(xiàn)不等回溯的，主串與模式串最后的m位也各比較了1次?？偙容^次數(shù)為：（n-m+1）×m，若m遠(yuǎn)小于n，則BF算法時間復(fù)雜度為O(n*m)。2.3.3蠻力法的典型實例——串匹配問題2.3.4蠻力法的典型實例——圖搜索問題對于非線性解空間，要想窮舉所有情況，就必須用到特定的搜索順序。在解決實際問題中，最常見的有兩種搜索順序：寬度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）。寬度優(yōu)先搜索寬度優(yōu)先搜索（BreadthFirstSearch，BFS），簡稱寬搜，又稱廣度優(yōu)先搜素或廣搜。它從初始結(jié)點開始，應(yīng)用產(chǎn)生式規(guī)則和控制策略生成第一層結(jié)點，同時檢查目標(biāo)結(jié)點是否在這些生成的結(jié)點中。若沒有，再用產(chǎn)生式規(guī)則將所有第一層結(jié)點逐一拓展，得到第二層結(jié)點，并逐一檢查第二層結(jié)點是否包含目標(biāo)結(jié)點。若沒有，再用產(chǎn)生式規(guī)則拓展第二層結(jié)點。如此依次拓展，檢查下去，直至發(fā)現(xiàn)目標(biāo)結(jié)點為止。如果拓展完所有結(jié)點，都沒有發(fā)現(xiàn)目標(biāo)結(jié)點，則問題無解。BFS屬于盲目搜索，最糟糕的情況下算法時間復(fù)雜度為O(n!)。2.3.4蠻力法的典型實例——圖搜索問題舉例說明：如圖所示，一個長方形的房間里鋪著方磚，每塊磚是“#”或黑點“?”。一個人站在黑磚上，可以按上、下、左、右方向移動到相鄰的磚。要求他只能在“?”黑點磚上移動，而不能在“#”的磚上移動。起點是@。問題：遍歷所有能走的黑點磚。2.3.4蠻力法的典型實例——圖搜索問題分析：可以用寬度優(yōu)先搜索來解決這個問題。如圖所示2.3.4蠻力法的典型實例——圖搜索問題BFS算法一般用隊列這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，其步驟為：（1）把起始結(jié)點S放到queue（隊列）中；（2）如果queue為空，則失敗退出，否則繼續(xù)；（3）在queue中取最前面的結(jié)點node移到CLOSED表中（出隊）；（4）擴(kuò)展node結(jié)點，若沒有后繼（即葉結(jié)點），則轉(zhuǎn)向（2）；（5）把node的所有后繼結(jié)點放在queue表的末端，即入隊；（6）若后繼結(jié)點中某一個是目標(biāo)結(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）。2.3.4蠻力法的典型實例——圖搜索問題BFS算法優(yōu)缺點寬度優(yōu)先搜索的優(yōu)點：①對于解決最短或最少問題特別有效，而且尋找深度??；②每個結(jié)點只訪問一遍，結(jié)點總是以最短路徑被訪問，所以第二次路徑確定不會比第一次短。寬度優(yōu)先搜索的缺點：一般需要存儲產(chǎn)生的所有結(jié)點，內(nèi)存耗費量大(需要開大量的數(shù)組單元用來存儲狀態(tài))，因此程序設(shè)計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題。2.3.4蠻力法的典型實例——圖搜索問題深度優(yōu)先搜索深度優(yōu)先搜索（DepthFirstSearch，DFS），簡稱深搜，是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的結(jié)點，盡可能深的搜索樹的分支。當(dāng)結(jié)點v的所在邊都己被探尋過或者在搜尋時結(jié)點不滿足條件，搜索將回溯到發(fā)現(xiàn)結(jié)點v的那條邊的起始結(jié)點。整個進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點都被訪問為止。DFS也屬于盲目搜索，最糟糕的情況下算法時間復(fù)雜度為O(n!)。2.3.4蠻力法的典型實例——圖搜索問題分析：也可以用深度優(yōu)先搜索來解決這個問題。如圖所示2.3.4蠻力法的典型實例——圖搜索問題DFS算法一般用棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，其步驟為：（1）把起始結(jié)點S放到stack（棧）中；（2）如果stack為空，則失敗退出，否則繼續(xù)；（3）在stack中把棧頂?shù)慕Y(jié)點node移到CLOSED表中（出棧）；（4）若結(jié)點node的深度等于最大深度，則轉(zhuǎn)向（2）；（5）擴(kuò)展node結(jié)點，若沒有后繼（即葉結(jié)點），則轉(zhuǎn)向（2），否則把node的所有后繼結(jié)點進(jìn)棧；（6）若后繼結(jié)點中某一個是目標(biāo)結(jié)點，則找到一個解，成功退出。否則轉(zhuǎn)向（2）。2.3.4蠻力法的典型實例——圖搜索問題DFS算法優(yōu)缺點深度優(yōu)先搜索的優(yōu)點：①能找出所有解決方案；②優(yōu)先搜索一棵子樹，然后是另一棵，所以和廣搜對比，有著內(nèi)存需要相對較少的優(yōu)點。深度優(yōu)先搜索的缺點：①要多次遍歷，搜索所有可能路徑，標(biāo)識做了之后還要取消；②在深度很大的情況下效率不高；③從輸出結(jié)果可看出，深度優(yōu)先搜索找到的第一個解并不一定是最優(yōu)解。2.3.4蠻力法的典型實例——圖搜索問題3.廣度優(yōu)先搜索和深度優(yōu)先搜索區(qū)別廣度優(yōu)先搜索與深度優(yōu)先搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對擴(kuò)展結(jié)點選取上。這兩種算法每次都擴(kuò)展一個結(jié)點的所有子結(jié)點。而不同的是，深度優(yōu)先搜索下一次擴(kuò)展的是本次擴(kuò)展出來的子結(jié)點中的一個，而廣度優(yōu)先搜索擴(kuò)展的則是本次擴(kuò)展的結(jié)點的兄弟結(jié)點。在具體實現(xiàn)上為了提高效率,各自采用了不同的數(shù)據(jù)結(jié)構(gòu)，廣度優(yōu)先搜索使用的是隊列的數(shù)據(jù)結(jié)構(gòu)，而深度優(yōu)先搜索使用的是棧的數(shù)據(jù)結(jié)構(gòu)。廣度優(yōu)先搜索是一個分層的搜索過程，沒有回退過程，是非遞歸的。只是每次都盡可能地擴(kuò)展當(dāng)前結(jié)點的鄰居結(jié)點，之后再向其子結(jié)點進(jìn)行擴(kuò)展。深度優(yōu)先搜索是一個遞歸過程，有回退過程。盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續(xù)搜索下去。當(dāng)結(jié)點V的所有邊都已被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點V有那條邊的始結(jié)點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點都被發(fā)現(xiàn)為止。2.3.4蠻力法的典型實例——圖搜索問題計算機(jī)算法設(shè)計與分析第三章

分治法學(xué)習(xí)目標(biāo)掌握分治法的基本思想掌握分治法的特點和基本框架掌握分治法解決實際問題3.1分治法基本思想孫子兵法兵勢篇曰：凡治眾如治寡，分?jǐn)?shù)是也。其大致意思就是管理大規(guī)模部隊和管理小股部隊是一樣的，分開治理就是了。這就是分治法在軍事上的運用。分治法的基本思想就是將一個較難以解決的規(guī)模大的問題，分割成多個相似的規(guī)模較小的子問題，先求出小規(guī)模子問題的解，然后將各小規(guī)模子問題的解組合起來就是規(guī)模大的問題的解。其中的一個關(guān)鍵點是分割的子問題一定要相似，這樣就可以采取同樣的方法來求解，從而將問題簡化。例3.1

二分查找問題。在一個升序的含n個元素的數(shù)組a[]中查找x，輸出x在數(shù)組a中的下標(biāo)位置，若沒查到返回-1。分析：可以考慮使用分治思想來解決，具體做法是設(shè)計三個變量left，mid和right將整個數(shù)組分成3個部分a[left,mid-1],a[mid],a[mid+1,right]。如果a[mid]>x，則使用相同的辦法在較小范圍[left,mid-1]中查找；如果a[mid]=x，則已查找到，返回mid即可；如果a[mid]<x，則使用相同的辦法在較小范圍[mid+1,right]中查找。以上過程都沒查找到的話，則數(shù)組中不存在x，返回-1。3.1分治法基本思想例3.2

二分歸并排序。將含有n個元素的數(shù)組a[]按關(guān)鍵字大小升序排列。以數(shù)組a[8]={8,4,5,7,1,3,6,2}為例來分析。3.1分治法基本思想3.2分治法的特點和基本框架當(dāng)采用分治法時，一般原問題都需要具備以下幾個特征：（1）難度遞降：即原問題的解決難度，隨著數(shù)據(jù)的規(guī)模的縮小而降低，當(dāng)降低到一定程度時，問題很容易解決。（2）問題可分：原問題可以分解為若干個規(guī)模較小的同類型問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。這是應(yīng)用分治法的前提。（3）解可合并：利用所有子問題的解，可合并出原問題的解。這個特征很關(guān)鍵，能否利用分治法完全取決于這個特征。（4）相互獨立：各個子問題之間相互獨立，某個子問題的求解不會影響到另一個子問題。如果子問題之間不獨立，則分治法需要重復(fù)地解決公共的子問題，造成效率低下的結(jié)果。設(shè)P是要求解的問題，|P|為問題P的輸入規(guī)模，現(xiàn)將分治法求解問題的基本框架描述如下：Divide-and-Conquer(P)：if|P|≤cthenS(P)

//當(dāng)問題規(guī)模較小時，很容易求出解endifdividePintoP1,P2,...,Pk//將原問題分割為規(guī)模小的子問題fori=1tokdoxi=Divide-and-Conquer(Pi)//遞歸求解每個子問題endforreturnMerge(x1,x2,...,xk)//將子問題的解合并成原問題的解3.2分治法的特點和基本框架3.3分治法的時間復(fù)雜度分析分治法的實現(xiàn)一般都是采用遞歸算法。分析分治法的時間復(fù)雜度需要使用其遞推公式來推導(dǎo)。分治法中通常的遞推方程有以下兩種類型：第一類是歸約后子問題規(guī)模比原問題規(guī)模呈常數(shù)級減少。遞推方程為如Hanoi塔問題使用分治法，將n個圓盤的問移動題歸約為兩個n-1圓盤移動子問題，也就是歸約后的子問題規(guī)模只比原問題規(guī)模少1。遞推方程為解得：第二類是歸約后子問題規(guī)模比原問題規(guī)模呈倍數(shù)減少。該算法的時間復(fù)雜度可以通過以下遞推公式求出：根據(jù)1.4.4節(jié)介紹的MasterTheorem主定理結(jié)論可知：3.3分治法的時間復(fù)雜度分析3.4.1分治法的典型實例——快速排序快速排序是數(shù)據(jù)結(jié)構(gòu)中經(jīng)典且高效的一種排序算法，它在實踐中應(yīng)用非常廣泛。設(shè)待排的數(shù)組為A，快速排序的基本思想為：用數(shù)組的首元素作為標(biāo)準(zhǔn)將A劃分為前、后兩部分，前部分元素都比首元素小，后部分元素都比首元素大，這兩部分就構(gòu)成兩個新的子問題。算法接著分別對這兩部分遞歸地進(jìn)行排序，各子問題排序完成后自然整個數(shù)組也就排序完成。算法的關(guān)鍵在于怎樣劃分?jǐn)?shù)組A而將其歸約成兩個相同結(jié)構(gòu)的子問題。3.4.1分治法的典型實例——快速排序快速排序算法Quicksort(A,p,r) //p和r分別為數(shù)組A的首元素和尾元素的下標(biāo)輸入：數(shù)組A[p..r],1≤p≤r≤n輸出：從A[p]到A[r]按照升序排好序的數(shù)組Aifp<rthenq←Partition(A,p,r) //劃分?jǐn)?shù)組，找到首元素A[p]在排好序后的位置qA[p]?A[q] //交換A[p]，A[q]中元素的值Quicksort(A,p,q-1) //對前部分繼續(xù)遞歸地用快速排序算法Quicksort(A,q+1,r) //對后部分繼續(xù)遞歸地用快速排序算法endif其算法中的Partition函數(shù)是劃分的過程函數(shù)，它實現(xiàn)的就是以A[p..r]的首元素A[p]作為標(biāo)準(zhǔn)，輸出q表示A[p]應(yīng)該處在的正確位置，即排好序后A[p]應(yīng)該放在數(shù)組下標(biāo)為q的位置。過程如下：（1）先從后向前掃描數(shù)組A，找到第一個不大于A[p]的元素A[j]（2）從前向后掃描A找到第一個大于A[p]的元素A[i]（3）當(dāng)i＜j時，交換A[i]與A[j]。這時A[j]后面的元素都大于A[p]，A[i]前面的元素都小于或等于A[p]。（4）接著對數(shù)組A從i到j(luò)之間的部分繼續(xù)上面的掃描過程，直到i和j相遇，當(dāng)i>j時，j就代表了A在排好序的數(shù)組中的正確位置q。此刻在q位置之前的元素都不大于A[p]，在q位置后面的元素都大于A[p]。3.4.1分治法的典型實例——快速排序3.4.1分治法的典型實例——快速排序劃分算法Partition(A,p,r)輸入：數(shù)組A[p..r],1≤p≤r≤n輸出：數(shù)組首元素A[p]在排好序的數(shù)組中的位置x←A[p]i←pj←r+1whiletruedorepeatj←j-1untilA[j]≤x//從后往前找到不大于x的元素repeati←i+1untilA[i]>x//從前往后找到大于x的元素ifi<jthenA[i]?A[j]//交換A[i]，A[j]中元素的值elsereturnj //i，j相遇，返回相遇的位置即為數(shù)組首元素A[p]的正確位置endifendwhile舉例說明一趟劃分的過程數(shù)組A[6]={64，57，86，42，12，53}，第一趟劃分以64為標(biāo)準(zhǔn)，p=1i=2j=5交換A[2]和A[5]的值，繼續(xù)循環(huán)。j=4i=5i<j不成立，一趟劃分結(jié)束，返回值為4。在Quicksort中q=4,交換A[p]，A[q]中元素的值，就得到一次劃分后的結(jié)果。在一趟快速排序結(jié)束后，繼續(xù)對兩個子數(shù)組{12,57,53,42}和{86}實施相同的操作。3.4.1分治法的典型實例——快速排序第1次循環(huán)645786421253第2次循環(huán)645753421286劃分后1257534264863.4.2分治法的典型實例——大整數(shù)乘法1.問題描述采用分治法設(shè)計一個有效的算法，計算兩個n位大整數(shù)的乘法。（n=2k,k=1,2,3....）。2.問題分析根據(jù)分治法的思想，可以將兩個大的整數(shù)乘法分而治之。將大整數(shù)按位數(shù)的一半分成兩個小整數(shù)，轉(zhuǎn)換成稍簡單的小整數(shù)乘法，再進(jìn)行合并。上述的過程可以重復(fù)進(jìn)行，直到得到最簡單的兩個1位數(shù)的乘法，從而解決上述問題。

3.4.2分治法的典型實例——大整數(shù)乘法3.4.2分治法的典型實例——大整數(shù)乘法3.算法設(shè)計BigIntMul(X,Y,n)輸入：大整數(shù)X，Y和位數(shù)n輸出：X與Y的乘積結(jié)果sx←sign(X),sy←sign(Y) //取X，Y的符號s←sx*sy //求出X×Y的符號ifs=0thenreturn0endifX←|X|,Y←|Y|ifn=1thenreturns*X*YendifA←X的左邊n/2位, B←X的右邊n/2位C←Y的左邊n/2位, D←Y的右邊n/2位m1←BigIntMul(A,C，n/2), m2←BigIntMul((A-B),(D-C)，n/2)m3←BigIntMul(B,D，n/2)S←m1*10^n+(m1+m2+m3)*10^(n/2)+m3returnS舉例:以計算3141×5247為例來說明。將3141分拆成31和41，5247分拆成52和47。然后計算31×52，-10×-5，41×47。當(dāng)出現(xiàn)兩個數(shù)位數(shù)不等時，可以將位數(shù)小的高位補0再進(jìn)行計算。如：-10×-5=10×05=(1×10+0)×(0×10+5)=1×0×100+(1×5+1×0+0×5)×10+0×5=0+50+0=50其他兩個個同理算出：31×52=1612，41×47=1927。帶入原來的算式得：3141×5247=16120000+(50+1612+1927)×100+1927=16480827。3.4.2分治法的典型實例——大整數(shù)乘法4.算法效率分析根據(jù)上述的計算過程得到遞推方程。改進(jìn)前：根據(jù)主定理理論可得：改進(jìn)后：根據(jù)主定理可得：

，有較大的改進(jìn)。3.4.3分治法的典型實例——平面內(nèi)最近點問題

3.4.3分治法的典型實例——平面內(nèi)最近點問題

2.問題分析如果采用蠻力法，就需要遍歷平面上任意兩個點之間的距離，然后比較得出最小的值。很顯然其時間復(fù)雜度是O(n2)。那有沒有更快的方法呢？考慮分治法，如圖3.2所示，用一條垂直的直線l將整個平面中的點分為左半平面PL和右半平面PR兩部分，使得兩部分的點數(shù)近似相等。

3.4.3分治法的典型實例——平面內(nèi)最近點問題

3.4.3分治法的典型實例——平面內(nèi)最近點問題

3.4.4分治法的典型實例——選擇第k小問題

3.4.3分治法的典型實例——平面內(nèi)最近點問題平面上最臨近點對算法MinDistance(P,X,Y)輸入：n()個點集合P，X,Y分別表示n個點的x,y坐標(biāo)的值輸出：最近的兩個點以及距離ifn≤

3then直接計算n個點之間的最短距離endifSort(n,X,Y) //把所有的點按照橫坐標(biāo)X排序

l←mid(X) //用一條豎直的線L將所有的點分成兩等份MinDistance(PL,XL,YL)d1←PL中最短距離MinDistance(PR,XR,YR)d2←PR中最短距離d←min(d1,d2)while(PL中的點andXL≥l-d)dowhile(PR中的點andXR≤l+d)doifdistance(XL,YL,XR,YR)<dthen存儲點對(XL,YL),(XR,YR)d←distance(XL,YL,XR,YR)endifendwhileendwhile該算法是遞歸算法，且里面有排序，為了提高效率，可以把排序操作放到遞歸算法的外面。另外在直線l兩邊距離不超過d的區(qū)域內(nèi)檢查與所取點的距離是否小于d的點不超過7個即可。

3.4.3分治法的典型實例——平面內(nèi)最近點問題

3.4.4分治法的典型實例——選擇第k小問題1.問題描述設(shè)A是含有n個元素的數(shù)組，從A中選出第k小的元素，其中1≤k≤n。所以選最小就是k=1；選最大就是k=n；選次大就是k=n-1；選中位數(shù)就是k=n/2。

3.4.4分治法的典型實例——選擇第k小問題

3.4.4分治法的典型實例——選擇第k小問題

計算機(jī)算法設(shè)計與分析第四章

動態(tài)規(guī)劃學(xué)習(xí)目標(biāo)了解動態(tài)規(guī)劃法的基本概念。掌握動態(tài)規(guī)劃法的基本思想。掌握動態(tài)規(guī)劃法解決實際問題。4.1動態(tài)規(guī)劃的提出在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，如下圖所示。這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。1狀態(tài)決策2狀態(tài)狀態(tài)決策n狀態(tài)狀態(tài)...決策4.1動態(tài)規(guī)劃的提出在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關(guān)的，決策取決于當(dāng)前的狀態(tài)，然后又會引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在不斷變化的狀態(tài)中依次產(chǎn)生出來的，故有動態(tài)的含義。因此，把處理它的方法稱為動態(tài)規(guī)劃方法。但是，一些與時間沒有關(guān)系的靜態(tài)規(guī)劃，如線性規(guī)劃、非線性規(guī)劃等問題，只要人為地引進(jìn)時間因素，也可把它視為多階段決策問題，用動態(tài)規(guī)劃方法去處理。4.2動態(tài)規(guī)劃基本概念1.階段動態(tài)規(guī)劃方法求解的問題都屬于多階段決策問題。因此需要將所求問題劃分為若干個階段。把描述階段的變量稱為階段變量，用k來表示。在劃分階段時，要求劃分后的階段按照時間或空間特征是有序的，否則問題就無法求解。在下圖中，階段可以劃分為5個，即k=1,2,3,4,5。2.狀態(tài)每個階段所處的客觀條件稱為狀態(tài)，它描述了研究問題過程的中間狀況。狀態(tài)就是某階段的出發(fā)位置，既是該階段某支路的起點，又是前一階段某支路的終點。通常一個階段有若干狀態(tài)。在下圖中，第一階段只有狀態(tài){A}，第二階段有狀態(tài){B1，B2}，第三階段有狀態(tài){C1，C2，C3，C4}。描述狀態(tài)的變量稱為狀態(tài)變量。通常用Sk表示第k階段的狀態(tài)變量。在圖中，S3={C1，C2，C3，C4}，該集合就稱為第三階段的可達(dá)狀態(tài)集。4.2動態(tài)規(guī)劃基本概念2.狀態(tài)這里的狀態(tài)必須滿足無后效性（