算法設(shè)計(jì)與分析 課件 第2、3章 蠻力法；分治法

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

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

if(x滿足指定的條件)

輸出x;┇}2.2蠻力法的設(shè)計(jì)思想使用蠻力法通常有如下幾種情況：搜索所有的解空間：?jiǎn)栴}的解存在于規(guī)模不大的解空間中。搜索所有的路徑：這類問(wèn)題中不同的路徑對(duì)應(yīng)不同的解。直接計(jì)算：按照基于問(wèn)題的描述和所涉及的概念定義，直接進(jìn)行計(jì)算。往往是一些簡(jiǎn)單的題，不需要算法技巧的。模擬和仿真：按照求解問(wèn)題的要求直接模擬或仿真即可。2.2蠻力法的設(shè)計(jì)思想編寫一個(gè)程序，輸出2～1000之間的所有完全數(shù)。完全數(shù)定義：該數(shù)的各因子（除該數(shù)本身外）之和正好等于該數(shù)本身，例如：6=1+2+3，28=1+2+4+7+14分析：解的范圍：2～1000，范圍小，適合采用蠻力法窮舉方法：依次即可條件比對(duì)：1到n/2中依次驗(yàn)證是否為n的約數(shù)，如是則累加，最終判斷是否和n相等2.2蠻力法的設(shè)計(jì)思想偽代碼：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è)計(jì)思想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蠻力法的典型實(shí)例蠻力法適用于很多場(chǎng)景，具體來(lái)說(shuō)，包括這幾類：搜索所有的解空間。問(wèn)題的解存在于規(guī)模不大的解空間中。解決這類問(wèn)題一般是找出某些滿足特定條件或要求的解。使用蠻力法就是把所有的解都列舉出來(lái)，從中選出符合要求的解。搜索所有的路徑。這類問(wèn)題中不同的路徑對(duì)應(yīng)不同的解，需要找出特定解。使用蠻力法搜索所有可能的路徑并計(jì)算路徑對(duì)應(yīng)的解，找出特定解。直接計(jì)算。基于問(wèn)題的描述直接進(jìn)行計(jì)算。模擬和仿真。根據(jù)問(wèn)題要求直接模擬或仿真。2.3.1蠻力法的典型實(shí)例——0-1背包問(wèn)題1.問(wèn)題描述給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的承重量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中的物品重量在不超過(guò)C的前提下，總價(jià)值最大？附加條件：在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包（1或0）。每種物品只有一份，不能將物品i裝入背包多次，也不能將物品i分割只裝入其的一部分。2.問(wèn)題分析確定解的表示形式：每種物品要么裝入背包，要么不裝入背包，分別用1和0表示，總共有n種物品，因此解的表示形式為n維的0-1向量，解的范圍有2n種組合。窮舉方法：當(dāng)n比較小時(shí)，規(guī)模不大，使用蠻力法是可行的。用一個(gè)0～2n-1中的整數(shù)的二進(jìn)制形式來(lái)代表某種組合，二進(jìn)制對(duì)應(yīng)位數(shù)為1的表示裝入對(duì)應(yīng)的第i個(gè)物品。比如，假設(shè)n=5，用6=(00110)2，它的第2，3位為1，則代表裝入第2，3種物品。約束條件：裝入的物品重量和要≤背包的承重量C。目標(biāo)是在滿足條件情況下總價(jià)值最大。對(duì)于每種符合條件的物品組合其總價(jià)值可以很方便計(jì)算出來(lái)，然后判斷是否大于前面驗(yàn)證過(guò)的組合物品總價(jià)值，若是，則將最大值更新，否則，最大值不變。2.3.1蠻力法的典型實(shí)例——0-1背包問(wèn)題2.3.1蠻力法的典型實(shí)例——0-1背包問(wèn)題3.算法實(shí)現(xiàn)KnapSack_BruteForce(W,V,n,C)輸入：n個(gè)物品的重量數(shù)組W[]，價(jià)值數(shù)組V[]，背包的承重量C輸出：背包能容下的價(jià)值最大的物品組合及總價(jià)值w←0，v←0 //包中初始沒(méi)放入任何物品，重量為0，價(jià)值為0fori←1to2n-1do //窮舉所有組合j←0temp←0whilej<ndo

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

w←w+W[j]

temp←temp+V[j]

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

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

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

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

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

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

Perm(arr,begin+1,end);

//進(jìn)行回溯

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

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

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

j++; }else{

i=i-j+1;

//主串回溯的位置

j=0;

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

return

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

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

二分查找問(wèn)題。在一個(gè)升序的含n個(gè)元素的數(shù)組a[]中查找x，輸出x在數(shù)組a中的下標(biāo)位置，若沒(méi)查到返回-1。分析：可以考慮使用分治思想來(lái)解決，具體做法是設(shè)計(jì)三個(gè)變量left，mid和right將整個(gè)數(shù)組分成3個(gè)部分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]中查找。以上過(guò)程都沒(méi)查找到的話，則數(shù)組中不存在x，返回-1。3.1分治法基本思想例3.2

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

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

3.4.2分治法的典型實(shí)例——大整數(shù)乘法3.4.2分治法的典型實(shí)例——大整數(shù)乘法3.算法設(shè)計(jì)BigIntMul(X,Y,n)輸入：大整數(shù)X，Y和位數(shù)n輸出：X與Y的乘積結(jié)果sx←sign(X),sy←sign(Y) //取X，Y的符號(hào)s←sx*sy //求出X×Y的符號(hào)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舉例:以計(jì)算3141×5247為例來(lái)說(shuō)明。將3141分拆成31和41，52