第四章——蛮力法
蠻力法概述
蠻力法也稱窮舉法(枚舉法)或暴力法，是一種簡(jiǎn)單的直接解決問題的方法，通常根據(jù)問題的描述和所涉及的概念定義，對(duì)問題所有可能的狀態(tài)(結(jié)果)一一進(jìn)行測(cè)試，直到找到解或?qū)⑷靠赡艿臓顟B(tài)都測(cè)試一遍為止。
蠻力法的“力”指的是計(jì)算機(jī)的運(yùn)算能力，蠻力法是基于計(jì)算機(jī)運(yùn)算速度快的特性，減少人的思考而把工作都交給計(jì)算機(jī)的“懶惰”策略(這里的懶惰指的是人懶，不是算法中的懶惰方法)，一般而言是最容易實(shí)現(xiàn)的方法。
蠻力法的優(yōu)點(diǎn)如下：
1.邏輯簡(jiǎn)單清晰，根據(jù)邏輯編寫的程序簡(jiǎn)單清晰。
2.對(duì)于一些需要高正確性的重要問題，它產(chǎn)生的算法一般而言是復(fù)雜度高但合理的。
3.解決問題的領(lǐng)域廣。
4.適用于一些規(guī)模較小，時(shí)間復(fù)雜度要求不高的問題。
5.可以作為其他高校算法的衡量標(biāo)準(zhǔn)，即作為被比較的例子。
主要缺點(diǎn)就是因?yàn)槿鄙偃说乃伎?#xff0c;算法往往設(shè)計(jì)的簡(jiǎn)單而缺乏高的效率。
蠻力法依賴的是將每個(gè)元素(狀態(tài))處理一次的掃描技術(shù)，通常在以下幾種情況使用蠻力法：
搜索所有的解空間：問題的解存在于規(guī)模不大的解空間中。
搜索所有的路徑：這類問題中不同的路徑對(duì)應(yīng)不同的解。
直接計(jì)算：按照基于問題的描述和所涉及的概念定義，直接進(jìn)行計(jì)算。往往是一些簡(jiǎn)單的題，不需要算法技巧的。
模擬和仿真：按照求解問題的要求直接模擬或仿真問題的過程即可。
作為算法的設(shè)計(jì)者，不要被這些人為設(shè)計(jì)的概念框住自己的手腳，通過自己的認(rèn)識(shí)合理的利用資源高效地處理問題才是我們需要做到的。
蠻力法的直接應(yīng)用
介紹一些直接采用蠻力法解決問題的例子。
直接采用蠻力法的一般格式
在直接采用蠻力法設(shè)計(jì)算法中，主要是使用循環(huán)語句和選擇語句：循環(huán)語句用于窮舉所有可能的情況，而選擇語句判定當(dāng)前的條件是否為所求的解。
模型比較簡(jiǎn)單就不看了(不要拘泥于模型，去體會(huì)思想)。
例題 4.1
編寫一個(gè)程序，輸出2到1000之間的所有完全數(shù)。完全數(shù)就是指該數(shù)的各因子(除該數(shù)本身外)之和正好等于該數(shù)本身。
直接采用蠻力法的方式就是將2到1000的所有數(shù)窮舉一遍，對(duì)每個(gè)可能是完全數(shù)的數(shù)，求解他們除本身之外的各因子之和與原數(shù)進(jìn)行比較。
for (m=2;m<=1000;m++){ //求出m的所有因子之和s;if (m==s) 輸出s; }求解所有因子的過程依舊是一個(gè)窮舉的過程，除本身之外的因子大小不會(huì)超過本身的一半，窮舉1到本身的一半判斷能夠整除即可，結(jié)合起來對(duì)應(yīng)的蠻力法如下：
void main(){ int m,i,s;//窮舉2-1000的所有整數(shù) for (m=2;m<=1000;m++){s=0;//s為因子的和//窮舉1到m/2的所有可能為因子的整數(shù) for (i=1;i<=m/2;i++) if (m%i==0) s+=i;//i是m的一個(gè)因子 if (m==s) printf("%d ",m);} }例 4.2
編寫一個(gè)程序，求這樣的四位數(shù)：這個(gè)四位數(shù)的十位是1，個(gè)位是2，這個(gè)四位數(shù)減去7就能被7整除，減去8就能被8整除，減去9就能被9整除。
設(shè)這個(gè)數(shù)的十進(jìn)制表示為ab12，則數(shù)值n=1000*\a+100*b+12，采用窮舉法窮舉a和b：
int n,a,b; //窮舉a和b,即窮舉最后兩位為12的四位數(shù) for (a=1;a<=9;a++) for (b=0;b<=9;b++){n=1000*a+100*b+12;//判斷n是否滿足題中的給定條件//輸出n }減去7被7整除，減去8被8整除，減去9被9整除就是簡(jiǎn)單的基本運(yùn)算的組合，完整的蠻力法如下：
int n,a,b; //窮舉a和b,即窮舉最后兩位為12的四位數(shù) for (a=1;a<=9;a++) for (b=0;b<=9;b++){n=1000*a+100*b+12;//判斷n是否滿足題中的給定條件if ((n-7)%7==0&&(n-8)%8==0&&(n-9)%9==0) printf("n=%d\n",n); }例 4.3
在象棋算式里，不同的棋子代表不同的數(shù)，有以下算式，設(shè)計(jì)一個(gè)算法求這些棋子各代表哪些數(shù)字。
直接采用窮舉法的思想就是，對(duì)于五個(gè)棋子的取值分別進(jìn)行枚舉，然后判斷對(duì)于一套取值是否能在不重復(fù)的前提下，滿足豎式的要求。
對(duì)應(yīng)的蠻力法如下：
void fun(){ int a,b,c,d,e,m,n,s;//分別窮舉兵,炮,馬,卒,車的各種可能 for (a=1;a<=9;a++) for (b=0;b<=9;b++) for (c=0;c<=9;c++) for (d=0;d<=9;d++) for (e=0;e<=9;e++)//避免取值的重復(fù) if (a==b||a==c||a==d||a==e||b==c||b==d||b==e||c==d||c==e||d==e) continue;//判斷是否滿足豎式的條件 else{ m=a*1000+b*100+c*10+d;n=a*1000+b*100+e*10+d;s=e*10000+d*1000+c*100+a*10+d;if (m+n==s)printf("兵:%d 炮:%d 馬:%d卒:%d 車:%d\n",a,b,c,d,e);} }例 4.4
有n個(gè)整數(shù)，存放在數(shù)組a中，設(shè)計(jì)一個(gè)算法從中選出3個(gè)正整數(shù)組成周長(zhǎng)最長(zhǎng)的三角形，并輸出該三角形的周長(zhǎng)，若無法組成三角形就輸出0。
窮舉出n個(gè)整數(shù)中選擇三條邊的所有可能，然后對(duì)于每一種可能判斷能否組成三角形，在能夠組成三角形的前提下，更新最大的周長(zhǎng)值。
對(duì)應(yīng)的蠻力法如下：
void solve(int a[],int n){int i,j,k,len,ma,maxlen=0;for (i=0;i<n;i++) for (j=i+1;j<n;j++) for (k=j+1;k<n;k++){len=a[i]+a[j]+a[k];ma=max3(a[i],a[j],a[k]);//判斷能夠窮舉出來的一種可能的三條邊能否組成一個(gè)三角形 if (ma<len-ma){//更新最大周長(zhǎng) if (len>maxlen) maxlen=len; } }printf("最長(zhǎng)三角形的周長(zhǎng)=%d\n",maxlen); }簡(jiǎn)單選擇排序和冒泡排序
遞歸那里介紹過了，這里不再做贅述(蠻力法本身是最簡(jiǎn)單的方法，以蠻力法的模型再去解析簡(jiǎn)單選擇
排序和冒泡排序不會(huì)有更好的收獲)。
字符串匹配
對(duì)于字符串s和t，若t是s子串，返回t在s中的位置(t的首字符在s中對(duì)應(yīng)的下標(biāo))，否則返回-1。
蠻力法的策略就是找到字符串s中所有長(zhǎng)度為t的字符串的長(zhǎng)度的連續(xù)子串，然后將連續(xù)子串與t進(jìn)行比較，判斷t是否為s的子串，這個(gè)字符串匹配的算法稱為BF算法(Brute-Force算法)也就是暴力算法的意思。
程序的while循環(huán)是一位一位匹配的，實(shí)際上存在回退的過程，就是將一個(gè)一個(gè)的連續(xù)子串與t進(jìn)行比較的過程。
//Brute-Force算法,字符串匹配 int BF(string s,string t){ int i=0,j=0;while (i<s.length()&&j<t.length()){ //匹配當(dāng)前的連續(xù)子串 if (s[i]==t[j]){i++; j++;}//當(dāng)前的連續(xù)子串匹配失敗,對(duì)s串進(jìn)行回退,實(shí)際上就是匹配下一個(gè)字母開頭的連續(xù)子串 else{i=i-j+1; j=0;}}//t的字符比較完畢if (j==t.length()) return i-j;//t是s的子串,返回位置//t不是s的子串,返回-1else return -1; }例 4.5
有兩個(gè)字符串s和t，設(shè)計(jì)一個(gè)算法求t在s中出現(xiàn)的次數(shù)。
用蠻力法處理這個(gè)問題的策略和BF算法是一致的，將字符串s中所有與字符串t長(zhǎng)度相等的連續(xù)子串拿出來進(jìn)行比較，區(qū)別就在于BF算法中完成匹配后直接退出循環(huán)，而這里的問題需要計(jì)算出t在s中出現(xiàn)的次數(shù)，所以t字符串匹配到最后一位后還是要回退直到s字符串匹配完全。
對(duì)應(yīng)的蠻力法算法如下：
//用蠻力法求t在s中出現(xiàn)的次數(shù) int Count(string s,string t){ int num=0;//計(jì)數(shù)器累計(jì)出現(xiàn)次數(shù)int i=0,j=0;while (i<s.length()&&j<t.length()){//匹配當(dāng)前的連續(xù)子串 if (s[i]==t[j]){i++; j++;}//當(dāng)前的連續(xù)子串匹配失敗,對(duì)s串進(jìn)行回退,實(shí)際上就是匹配下一個(gè)字母開頭的連續(xù)子串 else{i=i-j+1; j=0;}//匹配成功時(shí),仍然進(jìn)行回退,計(jì)時(shí)器+1 if(j==t.length()){num++; j=0; }}return num; }求解最大連續(xù)子序列和問題
就是分治法中求解連續(xù)最大子序列和的問題。
用蠻力法就是枚舉出所有連續(xù)的子序列的和，然后找到里面最大的那個(gè)子序列，書上的前兩種蠻力法都是基于的這種思路，解法二計(jì)算從第i個(gè)元素開始的連續(xù)子序列的和時(shí)，計(jì)算長(zhǎng)度長(zhǎng)的連續(xù)子序列的和繼承前面長(zhǎng)度較短的連續(xù)子序列的計(jì)算結(jié)果，相當(dāng)于減少了重復(fù)計(jì)算的內(nèi)容，解法二從某種角度而言其實(shí)已經(jīng)很傾向于動(dòng)態(tài)規(guī)劃算法了。
蠻力法的兩個(gè)解法如下：
//蠻力法求解最大連續(xù)子序列和問題的解法一 int maxSubSum1(int a[],int n){ int i,j,k; int maxSum=a[0],thisSum;//窮舉所有的連續(xù)子序列 for (i=0;i<n;i++) for (j=i;j<n;j++){ //計(jì)算連續(xù)的子序列的和 thisSum=0;for (k=i;k<=j;k++) thisSum+=a[k];//通過比較求最大連續(xù)子序列之和if (thisSum>maxSum) maxSum=thisSum;}return maxSum; } //蠻力法求解最大連續(xù)子序列和問題的解法二 int maxSubSum2(int a[],int n){ int i,j;int maxSum=a[0],thisSum;//窮舉所有的連續(xù)子序列//thisSum記錄以i為首的連續(xù)子序列的和,有點(diǎn)滾動(dòng)數(shù)組的意思 for (i=0;i<n;i++){thisSum=0;for (j=i;j<n;j++){thisSum+=a[j];//通過比較求最大連續(xù)子序列之和if (thisSum>maxSum) maxSum=thisSum;}}return maxSum; }前一種的復(fù)雜度為O(n3)，后一種的復(fù)雜度為O(n2)。
解法3基于的一個(gè)事實(shí)就是最大的連續(xù)子序列一定不可能由一段和為負(fù)的連續(xù)子序列后面拼上別的連續(xù)子序列，因?yàn)樯釛壛饲懊婧螢樨?fù)的連續(xù)子序列，連續(xù)子序列的和變得更大就產(chǎn)生了矛盾。
于是在我們計(jì)算從第i個(gè)元素開始的連續(xù)子序列的和時(shí)，我們只需要計(jì)算到連續(xù)子序列的和小于0之前即可。
我們假設(shè)上面過程枚舉第i個(gè)元素開始的連續(xù)子序列的最后一個(gè)元素，枚舉到第j個(gè)元素為止，也就是說對(duì)于k(i≤k≤j)，都有第i個(gè)元素到第k個(gè)元素的連續(xù)子序列的和非負(fù)，當(dāng)我們考察第k個(gè)元素開始的連續(xù)子序列時(shí)，由于第i個(gè)元素到第k-1個(gè)元素的連續(xù)子序列的和非負(fù)，那么第k個(gè)元素到第j個(gè)元素的連續(xù)子序列的和一定小于等于第i個(gè)元素到第j個(gè)元素的連續(xù)子序列和。
也就是說我們枚舉第k個(gè)元素開始的連續(xù)子序列的最后一個(gè)元素，做多枚舉的不會(huì)超過第j個(gè)元素，且由于第i個(gè)元素到第k-1個(gè)元素的連續(xù)子序列的和非負(fù)，我們枚舉的第k個(gè)元素開始的連續(xù)子序列的值不會(huì)超過枚舉的第i個(gè)元素開始的連續(xù)子序列的值。
所以我們枚舉完第i個(gè)元素開始的連續(xù)子序列的最后一個(gè)元素，枚舉到第j個(gè)元素為止后，下一個(gè)枚舉的元素從第j+1個(gè)元素開始，也就是說只需要從前往后的遍歷一遍。
對(duì)應(yīng)的算法如下：
//蠻力法求解最大連續(xù)子序列和問題的解法三 int maxSubSum3(int a[],int n){ int i,maxSum=0,thisSum=0;for (i=0;i<n;i++){thisSum+=a[i];//若當(dāng)前以第i個(gè)元素開頭枚舉的子序列和為負(fù)數(shù),重新開始枚舉下一元素開頭的連續(xù)子序列if (thisSum<0) thisSum=0;//比較求最大連續(xù)子序列和if (maxSum<thisSum) maxSum=thisSum;}return maxSum; }解法三相比解法二傾向于與貪心思想的結(jié)合，解法二和解法三嚴(yán)格意義上說都不能稱為傳統(tǒng)意義上的蠻力法了。
三個(gè)解法的合集如下：
//蠻力法求解最大連續(xù)子序列和問題的解法一 int maxSubSum1(int a[],int n){ int i,j,k; int maxSum=a[0],thisSum;//窮舉所有的連續(xù)子序列 for (i=0;i<n;i++) for (j=i;j<n;j++){ //計(jì)算連續(xù)的子序列的和 thisSum=0;for (k=i;k<=j;k++) thisSum+=a[k];//通過比較求最大連續(xù)子序列之和if (thisSum>maxSum) maxSum=thisSum;}return maxSum; } //蠻力法求解最大連續(xù)子序列和問題的解法二 int maxSubSum2(int a[],int n){ int i,j;int maxSum=a[0],thisSum;//窮舉所有的連續(xù)子序列//thisSum記錄以i為首的連續(xù)子序列的和,有點(diǎn)滾動(dòng)數(shù)組的意思 for (i=0;i<n;i++){thisSum=0;for (j=i;j<n;j++){thisSum+=a[j];//通過比較求最大連續(xù)子序列之和if (thisSum>maxSum) maxSum=thisSum;}}return maxSum; } //蠻力法求解最大連續(xù)子序列和問題的解法三 int maxSubSum3(int a[],int n){ int i,maxSum=0,thisSum=0;for (i=0;i<n;i++){thisSum+=a[i];//若當(dāng)前以第i個(gè)元素開頭枚舉的子序列和為負(fù)數(shù),重新開始枚舉下一元素開頭的連續(xù)子序列if (thisSum<0) thisSum=0;//比較求最大連續(xù)子序列和if (maxSum<thisSum) maxSum=thisSum;}return maxSum; }求解冪集問題
對(duì)于給定的正整數(shù)n，求1到n構(gòu)成的集合的所有子集(冪集)。例如n=3時(shí)，1到n構(gòu)成的集合的所有子集為：{}，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}。
這個(gè)問題用窮舉法解決的策略就是對(duì)每個(gè)元素考慮選取與不選取的兩個(gè)情況，即從全不選擇，到全都選擇窮舉所有的可能。
第i個(gè)數(shù)選擇為1不選擇為0，于是對(duì)于任意一個(gè)子集我們可以得到一個(gè)長(zhǎng)度為n的二進(jìn)制編碼，這些二進(jìn)制編碼對(duì)應(yīng)的十進(jìn)制數(shù)為0到2n-1，例如n=3時(shí)對(duì)應(yīng)的二進(jìn)制編碼和十進(jìn)制數(shù)如下：
這種窮舉法的思路就是將0到2n-1的十進(jìn)制數(shù)全部轉(zhuǎn)化為二進(jìn)制數(shù)，然后根據(jù)二進(jìn)制數(shù)得到對(duì)應(yīng)的子集，時(shí)間復(fù)雜度為2n*n(這種方法稱為二進(jìn)制法，比較簡(jiǎn)單，書上的寫法很糟糕這里就不多贅述了)。
另一種實(shí)現(xiàn)方法，設(shè)置n層循環(huán)，前i層循環(huán)得到前i個(gè)元素能夠構(gòu)成的2i個(gè)冪集，然后根據(jù)第i+1個(gè)元素選擇和不選擇得到前i+1個(gè)元素能夠構(gòu)成的2i+1個(gè)冪集。
vector<vector<int> >ps;//存放冪集 //求1~n的冪集ps void PSet(int n){ vector<vector<int> >ps1//子冪集vector<vector<int> >::iterator it;//冪集迭代器vector<int> s;ps.push_back(s);//添加{}空集合元素//i層循環(huán)考慮是否添加元素i進(jìn)入現(xiàn)有的子集,從1~i-1的冪集得到1~i的冪集 for (int i=1;i<=n;i++){ ps1=ps;//ps存放上一層循環(huán)得到從1~i-1的冪集,ps1復(fù)制1~i-1的冪集//然后通過1~i-1的冪集后面擴(kuò)展一個(gè)元素i,得到1~i的冪集比起1~i-1的冪集多出來的部分 for (it=ps1.begin();it!=ps1.end();++it) (*it).push_back(i); for (it=ps1.begin();it!=ps1.end();++it) ps.push_back(*it); } }這個(gè)復(fù)雜度相對(duì)前一種實(shí)現(xiàn)方法低，為O(2n)，也是用了類似動(dòng)態(tài)規(guī)劃的思想。
求解0/1背包問題
n個(gè)重量分別為w1，w2，…，wn的物品，它們的價(jià)值分別為v1，v2，…，vn，給定一個(gè)容量為W的背包。
設(shè)計(jì)從這些物品中選取一部分物品放入該背包的方案，每個(gè)物品要么選中要么不選中，要求選中的物品不僅能夠放到背包中，而且具有最大的價(jià)值。
使用蠻力法的策略就是枚舉出所有可能的方案，然后根據(jù)選擇物品的方案得到它們的重量和價(jià)值，然后再用蠻力法將每種方案排查一遍得到滿足容量條件中，價(jià)值最大的方案。
窮舉所有可能選取物品方案的方法和窮舉冪集的策略是一樣的，對(duì)應(yīng)的蠻力法算法如下：
ector<vector<int> >ps;//存放冪集 //求1~n的冪集ps void PSet(int n){ vector<vector<int> >ps1//子冪集vector<vector<int> >::iterator it;//冪集迭代器vector<int> s;ps.push_back(s);//添加{}空集合元素//i層循環(huán)考慮是否添加元素i進(jìn)入現(xiàn)有的子集,從1~i-1的冪集得到1~i的冪集 for (int i=1;i<=n;i++){ ps1=ps;//ps存放上一層循環(huán)得到從1~i-1的冪集,ps1復(fù)制1~i-1的冪集//然后通過1~i-1的冪集后面擴(kuò)展一個(gè)元素i,得到1~i的冪集比起1~i-1的冪集多出來的部分 for (it=ps1.begin();it!=ps1.end();++it) (*it).push_back(i); for (it=ps1.begin();it!=ps1.end();++it) ps.push_back(*it); } } //用蠻力法求所有的方案和最佳方案 void Knap(int w[],int v[],int W){//用求解冪集的方法窮舉出所有的方案 PSet(n); int count=0;//窮舉過程中窮舉的方案的編號(hào)int sumw,sumv;//當(dāng)前窮舉的方案的總重量和總價(jià)值int maxi,maxsumw=0,maxsumv=0;//最佳方案的編號(hào),總重量和總價(jià)值vector<vector<int> >::iterator it;//訪問冪集中每個(gè)子集的迭代器vector<int>::iterator sit;//訪問冪集子集元素的迭代器 //冪集的每一個(gè)子集對(duì)應(yīng)一套方案 for (it=ps.begin();it!=ps.end();++it){ sumw=sumv=0;for (sit=(*it).begin();sit!=(*it).end();++sit){ sumw+=w[*sit-1];//計(jì)算該套方案的重量 sumv+=v[*sit-1];//計(jì)算該套方案的價(jià)值 }//比較求滿足條件的最優(yōu)方案if (sumw<=W&&sumv>maxsumv){ maxsumw=sumw;maxsumv=sumv;maxi=count; }count++; } }求解全排列問題
對(duì)于給定的正整數(shù)n，求1~n的所有全排列。
例如n=3，1~n的全排列為：123，132，213，231，312，321。
用蠻力法求解全排列問題是個(gè)比較經(jīng)典的問題，一種思路是窮舉全排列中每一個(gè)排列每一位出現(xiàn)的數(shù)字，從第一位窮舉到最后一位。
另一種思路就是書上的思路：窮舉數(shù)字i可能出現(xiàn)的位置，從1窮舉到n。和求解冪集問題一樣，前i層窮舉數(shù)字1到i出現(xiàn)的位置，相當(dāng)于窮舉出1到i的全排列，然后在第i+1層循環(huán)中窮舉數(shù)字i+1可能出現(xiàn)的位置，從1到i的全排列擴(kuò)展到1到i+1的全排列(從思想上近似于動(dòng)態(tài)規(guī)劃的思想)。
對(duì)應(yīng)的蠻力法的算法如下：
vector<vector<int> >ps;//存放1到n的全排列 //在排列s中尋找能夠插入i的位置,將得到的新的s1插入到ps1中 vvoid Insert(vector<int> s,int i,vector<vector<int> > &ps1){ vector<int> s1;vector<int>::iterator it;//窮舉將i插入到排列s的位置 for (int j=0;j<i;j++){ s1=s;it=s1.begin()+j;//插入的位置 s1.insert(it,i);//插入整數(shù)ips1.push_back(s1);//將得到的新的排列加入ps1中 } } //求1~n的所有全排列 void Perm(int n){ vector<vector<int> >ps1;//存放1到i-1的全排列 vector<vector<int> >::iterator it;//全排列迭代器vector<int>s,s1;s.push_back(1); ps.push_back(s);//在ps中添加{1}集合元素,得到1到1的全排列 //從2開始窮舉每一個(gè)數(shù)字可能出現(xiàn)的位置 for (int i=2;i<=n;i++){ps1.clear();//ps存放1到i-1的全排列,在1到i-1的每個(gè)排列中尋找i能夠插入的位置//將得到的1到i的全排列中的排列插入到ps1中 for (it=ps.begin();it!=ps.end();++it) Insert(*it,i,ps1); ps=ps1;} }時(shí)間復(fù)雜度為O(n*n!)。
求解任務(wù)分配問題
有n個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只能分配給一個(gè)人，每個(gè)人只能執(zhí)行一個(gè)任務(wù)。第i個(gè)人執(zhí)行第j個(gè)任務(wù)的成本是c[i][j]，求出總成本最小的分配方案。
蠻力法的策略就是窮舉出所有任務(wù)分配的方案，然后計(jì)算出每個(gè)任務(wù)分配的方案的成本，然后比較求解出總成本最小的分配方案。
窮舉出所有任務(wù)分配的方案，我們將第1個(gè)人到第n個(gè)人做的任務(wù)的編號(hào)連在一起得到一個(gè)n位的數(shù)字序列，所有任務(wù)分配的方案對(duì)應(yīng)的n位數(shù)字序列的總集就是1~n的全排列，求解任務(wù)分配問題蠻力法解決實(shí)際上就是求解全排列問題(代碼就不做贅述了)。
上面介紹了用蠻力法求解找到滿足條件的數(shù)的簡(jiǎn)單數(shù)學(xué)問題，排序問題，字符串匹配問題，最大連續(xù)子序列和問題，冪集問題，0/1背包問題，全排列問題，任務(wù)分配問題。
其中蠻力法求解0/1背包問題和任務(wù)分配問題分別屬于蠻力法求解冪集問題和全排列問題的衍生應(yīng)用，分別成為子集問題和排列問題。蠻力法求解冪集問題和全排列問題的解法存在比較高的相似性，包括第二種優(yōu)化的解法(提供給我們動(dòng)態(tài)規(guī)劃在什么地方使用和框架設(shè)計(jì)的思路)。
遞歸在蠻力法中的應(yīng)用
蠻力法是一種處理問題的算法思想，遞歸是一種算法的實(shí)現(xiàn)方式，很多用蠻力法求解問題的過程都可以采用遞歸方式來實(shí)現(xiàn)，遞歸算法的分解規(guī)模較小的問題(階段)的框架也給最基礎(chǔ)的蠻力法帶來一定優(yōu)化方向上的啟發(fā)。
用遞歸方法求解冪集問題，全排列問題
求解冪集問題和全排列問題的第二種解法，都是將問題從最小的規(guī)模(空集，1到1的全排列)一步一步擴(kuò)展(從前i個(gè)元素的冪集擴(kuò)展到前i+1個(gè)元素的冪集，從1到i的全排列擴(kuò)展到1到i+1的全排列)，擴(kuò)展到規(guī)模最大的原問題的解(n個(gè)元素的冪集，1到n的全排列)，本身就是符合遞歸算法設(shè)計(jì)的一般步驟的。
我們前面是用循環(huán)去實(shí)現(xiàn)的，就相當(dāng)于用循環(huán)結(jié)構(gòu)替代遞歸過程的結(jié)果。替換回遞歸過程的策略是給函數(shù)添加一個(gè)·屬性，然后通過屬性值的遞減或遞增進(jìn)行一個(gè)狀態(tài)是順序結(jié)構(gòu)的遞歸，效果和循環(huán)結(jié)構(gòu)是一樣的，這里不做贅述。
用遞歸方法求解組合問題
求從1~n的正整數(shù)中取k個(gè)不重復(fù)整數(shù)的所有組合。
因?yàn)橹蝗個(gè)不重復(fù)整數(shù)，而不是將n個(gè)整數(shù)全部不重復(fù)地取出，前面子問題為求1到i放置位置的可能(全排列)的設(shè)計(jì)在這里就不是很好用。
但我們前面還提到另外一種窮舉法的思路：窮舉每一個(gè)排列每一位出現(xiàn)的數(shù)字，從第一位窮舉到最后一位。
于是我們可以設(shè)規(guī)模最大的原問題為1到n中選取k個(gè)不重復(fù)的數(shù)字，規(guī)模較小的子問題為1到n中選取i個(gè)不重復(fù)的數(shù)字。但是這么設(shè)計(jì)需要注意一個(gè)問題，就是當(dāng)我們從規(guī)模較小的問題的解去求解規(guī)模較大的問題時(shí)，選取的i個(gè)數(shù)字不能在規(guī)模較大的問題中進(jìn)行選取，就是說實(shí)際上取數(shù)的范圍不是1到n，而是1到n中不包括前面選取過的i個(gè)數(shù)字，我們可以用標(biāo)記的方法來解決這個(gè)問題。
但是不同于全排列1，2，3和1，3，2屬于兩種不同的排列，不重復(fù)數(shù)字的組合中的數(shù)字不存在次序關(guān)系，就是說1，4，7，8和4，8，7，1是一種組合，于是我們可以默認(rèn)每一種組合中數(shù)字都是從小到大排列的。
有一種不使用標(biāo)記的更好的設(shè)計(jì)方案：設(shè)規(guī)模最大的原問題為從1到n中從小到大的選取k個(gè)不重復(fù)的數(shù)字，選取的最大數(shù)為max_n。規(guī)模較小的子問題為1到n中從小到大的選取i個(gè)不重復(fù)的數(shù)字，選區(qū)的最大數(shù)為max_i，因?yàn)閷⒔M合中的元素從小到大的排序且添加了一個(gè)max_i的屬性，從規(guī)模為i的子問題擴(kuò)展到規(guī)模為i+1的子問題，第i+1個(gè)數(shù)字的選取可以在max_i到n中選取，不用再通過標(biāo)記的方法來判斷是否出現(xiàn)重復(fù)，第i+1次選取的數(shù)字為max_(i+1)。
前面提到“蠻力法是一種處理問題的算法思想，遞歸是一種算法的實(shí)現(xiàn)方式”，蠻力法算法指的是算法思想，遞歸算法指的是算法思想，兩者并不沖突，我們遞歸那一章中很多遞歸算法采用的算法思想也是蠻力法。
我們?cè)谑褂眠f歸去實(shí)現(xiàn)蠻力法算法時(shí)，會(huì)發(fā)現(xiàn)很多子問題(階段)是重復(fù)求解的，我們將子問題的解保存下來，重復(fù)求解時(shí)直接返回子問題的解能夠提高效率(求解全排列問題和冪集問題用到過這個(gè)方法)，這是我們之后章節(jié)要介紹的內(nèi)容。
圖的深度優(yōu)先和廣度優(yōu)先遍歷
圖的存儲(chǔ)結(jié)構(gòu)
圖的存儲(chǔ)結(jié)構(gòu)主要就是鄰接矩陣存儲(chǔ)方式和鄰接表存儲(chǔ)方式，這主要是數(shù)據(jù)結(jié)構(gòu)篇章的內(nèi)容，我們只做略過，不多做贅述。
鄰接矩陣存儲(chǔ)方法
鄰接矩陣作為一個(gè)矩陣，第行第j列的值表示結(jié)點(diǎn)i到結(jié)點(diǎn)是否存在邊(或者是帶權(quán)圖中邊的權(quán))。
結(jié)構(gòu)體定義如下：
鄰接表存儲(chǔ)方法
圖的鄰接表存儲(chǔ)方法是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
我們對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中存儲(chǔ)與頂點(diǎn)i鄰接的頂點(diǎn)。n個(gè)單鏈表的表頭結(jié)點(diǎn)再通過數(shù)組的方式存儲(chǔ)起來構(gòu)成一個(gè)表頭結(jié)點(diǎn)數(shù)組。
typedef struct ANode{ int adjvex;//鄰接頂點(diǎn)的頂點(diǎn)編號(hào) int weight;//結(jié)點(diǎn)i到鄰接頂點(diǎn)構(gòu)成的邊的權(quán)值 struct ANode *nextarc;//指向下一鄰接頂點(diǎn)的指針 }ArcNode; //頂點(diǎn)結(jié)構(gòu)體,存儲(chǔ)頂點(diǎn)信息和頂點(diǎn)對(duì)應(yīng)單鏈表的表頭結(jié)點(diǎn) typedef struct Vnode{ char data[MAXL];//頂點(diǎn)信息ArcNode *firstarc;//firstarc為頂點(diǎn)對(duì)應(yīng)單鏈表的表頭結(jié)點(diǎn) }VNode; typedef VNode AdjList[MAXV];//AdjList是鄰接表類型,存儲(chǔ)n個(gè)單鏈表的表頭結(jié)點(diǎn) typedef struct{ AdjList adjlist;//鄰接表int n,e;//圖中頂點(diǎn)數(shù)n和邊數(shù)e }ALGraph;圖遍歷算法
從給定(連通)圖中任意指定的頂點(diǎn)(起始點(diǎn))出發(fā)，按照某種順序沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問一次的過程稱為圖的遍歷，對(duì)應(yīng)算法為圖遍歷算法。
圖遍歷算法是圖算法的設(shè)計(jì)基礎(chǔ)，根據(jù)不同的遍歷順序，最經(jīng)典的兩種遍歷方式有深度優(yōu)先遍歷和廣度優(yōu)先遍歷，他們本質(zhì)的算法思想都是蠻力法思路(作為搜索算法的算法思想是蠻力法思路，通過窮舉每個(gè)結(jié)點(diǎn)的可能來找到我們需要搜索的目標(biāo))。
深度優(yōu)先遍歷
深度優(yōu)先遍歷的策略，簡(jiǎn)單來說就是在一條分支上將該分支的結(jié)點(diǎn)先遍歷完，再回溯(這是一個(gè)概念上的回溯，不需要進(jìn)行另外的操作)到前面的祖先結(jié)點(diǎn)遍歷別的分支，直到所有的結(jié)點(diǎn)遍歷完全(見上科大課件的lecture 10)。
算法的過程如下：
1.從圖中某個(gè)初始頂點(diǎn)v出發(fā)，首先訪問初始頂點(diǎn)v。
2.選擇一個(gè)與當(dāng)前正在訪問的結(jié)點(diǎn)相鄰且沒被訪問過的頂點(diǎn)為下一次訪問的當(dāng)前結(jié)點(diǎn)(屬性)，以該結(jié)點(diǎn)進(jìn)行2的操作；當(dāng)某個(gè)結(jié)點(diǎn)無法向下進(jìn)行2的操作，回到上次訪問的結(jié)點(diǎn)選擇另外一個(gè)相鄰且沒有訪問過的頂點(diǎn)進(jìn)行2的操作(就是遞歸堆頂元素求解成功，退棧之后代入回新的棧頂元素進(jìn)行處理的過程)，直到圖中與頂點(diǎn)v連通的所有頂點(diǎn)都被訪問過為止。
顯然，這個(gè)算法過程是個(gè)遞歸過程(算法正確性的證明過程略)。
以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先遍歷算法如下：
//鄰接矩陣的DFS算法 void DFS(MGraph g,int v){ visited[v]=1;//標(biāo)記當(dāng)前正在訪問的結(jié)點(diǎn)v已經(jīng)被訪問//找當(dāng)前正在訪問v的所有相鄰點(diǎn)(矩陣值部不為0,不為INF) for (int w=0;w<g.n;w++)//且相鄰點(diǎn)不能在前面遍歷的過程中被訪問過 if (g.edges[v][w]!=0&&g.edges[v][w]!=INF&&visited[w]==0) DFS(g,w); }時(shí)間復(fù)雜度為O(n2)。
以鄰接表為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先遍歷算法如下(其實(shí)單鏈表也可以用for循環(huán)進(jìn)行遍歷)：
//鄰接表的DFS算法 void DFS(ALGraph *G,int v){ ArcNode *p;visited[v]=1; p=G->adjlist[v].firstarc;//p指向頂點(diǎn)v的第一個(gè)鄰接點(diǎn)while (p!=NULL){ //若頂點(diǎn)未訪問,以該頂點(diǎn)作為下一個(gè)訪問頂點(diǎn) if (visited[p->adjvex]==0) DFS(G,p->adjvex);p=p->nextarc; } }時(shí)間復(fù)雜度為O(n+e)。
這里visited數(shù)組進(jìn)行標(biāo)記來避免圖的遍歷過程中結(jié)點(diǎn)被重復(fù)遍歷。而樹作為圖的一個(gè)特殊大類，樹遍歷算法不需要進(jìn)行標(biāo)記，所以我們往往會(huì)先介紹樹的遍歷算法再?gòu)臉涞母拍顏斫忉寛D遍歷算法中為什么需要對(duì)結(jié)點(diǎn)進(jìn)行標(biāo)記的原因。
事實(shí)上，通過我們這里圖遍歷算法的遞歸過程對(duì)應(yīng)的遞歸樹，也可以從這個(gè)遞歸樹的角度來解釋為什么樹遍歷算法不需要進(jìn)行標(biāo)記。
例 4.6
假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法判斷圖G中從頂點(diǎn)u到v是否存在簡(jiǎn)單路徑。
判斷點(diǎn)u到點(diǎn)v是否存在簡(jiǎn)單路徑，就是判斷點(diǎn)u與點(diǎn)v是否連通。前面提到圖遍歷算法可以通過一個(gè)頂點(diǎn)訪問連通圖所有的頂點(diǎn)，就是訪問所有與該頂點(diǎn)連通的頂點(diǎn)。
對(duì)于這個(gè)問題，我們采用圖遍歷算法，如果存在簡(jiǎn)單路徑，也就是連通，那么通過圖遍歷算法就能夠訪問到，否則不能。
對(duì)應(yīng)的算法如下：
//判斷G中從頂點(diǎn)u到v是否存在簡(jiǎn)單路徑 bool ExistPath(ALGraph *G,int u,int v){ int w; ArcNode *p;visited[u]=1; if (u==v) return true;//當(dāng)前訪問的結(jié)點(diǎn)為v,說明u和v連通,返回true p=G->adjlist[u].firstarc; while (p!=NULL){//遞歸訪問未訪問過的相鄰結(jié)點(diǎn)w=p->adjvex; if (visited[w]==0){ bool flag=ExistPath(G,w,v);if (flag) return true;//當(dāng)前分支連通,就不用回溯到該節(jié)點(diǎn)訪問下一個(gè)相鄰節(jié)點(diǎn) }p=p->nextarc; }return false;//沒有找到v,返回false }例題4.7不僅需要判斷路徑，還需要輸出路徑，這個(gè)問題我們?cè)谇懊孢f歸法的章節(jié)中討論過二叉樹的版本，前面提到圖遍歷算法和樹遍歷算法只有標(biāo)記的區(qū)別，所以不再做贅述(書上的方法是遞歸章節(jié)介紹的第二種方法)。
廣度優(yōu)先遍歷
廣度優(yōu)先遍歷，就是以到起始結(jié)點(diǎn)的邊的數(shù)量作為優(yōu)先級(jí)，每一層訪問同一個(gè)優(yōu)先級(jí)的節(jié)點(diǎn)，然后通過該層某優(yōu)先級(jí)的結(jié)點(diǎn)訪問到下一優(yōu)先級(jí)的結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)全部被訪問過為止。
由于結(jié)點(diǎn)是按照優(yōu)先級(jí)訪問，優(yōu)先級(jí)低的先訪問，優(yōu)先級(jí)的后訪問，且我們通過優(yōu)先級(jí)擴(kuò)展到的相鄰的結(jié)點(diǎn)一定是緊接著的下一優(yōu)先級(jí)的結(jié)點(diǎn)(這一點(diǎn)保證添加進(jìn)容器后，出容器的次序是按照優(yōu)先級(jí)的次序出的)，于是我們可以用隊(duì)列作為寬度優(yōu)先遍歷訪問結(jié)點(diǎn)的容器。
以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的廣度優(yōu)先遍歷算法如下：
//鄰接矩陣的BFS算法 void BFS(MGraph g,int v){ queue<int>qu;//隊(duì)列存儲(chǔ)需要訪問的結(jié)點(diǎn) int w,i;visited[v]=1;//標(biāo)記初始結(jié)點(diǎn)v已經(jīng)被訪問qu.push(v);//v進(jìn)隊(duì)while (!qu.empty()){//出隊(duì)首結(jié)點(diǎn)進(jìn)行訪問并進(jìn)行標(biāo)記 w=qu.top(); qu.pop(); visited[w]=1;//尋找相鄰且訪問的結(jié)點(diǎn)進(jìn)行擴(kuò)展(進(jìn)隊(duì)),擴(kuò)展到下一優(yōu)先級(jí) for (i=0;i<g.n;i++)if (g.edges[w][i]!=0&&g.edges[w][i]!=INF&&visited[i]==0) qu.push(i);} }復(fù)雜度為O(n2)，鄰接表的廣度優(yōu)先遍歷和鄰接表的深度優(yōu)先遍歷一樣，就是在尋找相鄰結(jié)點(diǎn)時(shí)是遍歷一個(gè)單鏈表，復(fù)雜度為O(n+e)。
對(duì)于鄰接矩陣，每遍歷一個(gè)結(jié)點(diǎn)就需要將n個(gè)結(jié)點(diǎn)檢查一遍尋找相鄰且為訪問過的結(jié)點(diǎn)，所以復(fù)雜度為O(n2)；而對(duì)于鄰接表，每遍歷一個(gè)結(jié)點(diǎn)也需要將與它相鄰的結(jié)點(diǎn)檢查一遍，但是相鄰的結(jié)點(diǎn)是通過單鏈表存儲(chǔ)起來的，所以復(fù)雜度為所有節(jié)點(diǎn)相鄰結(jié)點(diǎn)的個(gè)數(shù)之和即為O(e)(加上n是因?yàn)檫€要遍歷節(jié)點(diǎn))。
例 4.8
假設(shè)圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，求不帶權(quán)無向連通圖G中從頂點(diǎn)u到頂點(diǎn)v的一條最短路徑。
例4.8屬于廣度優(yōu)先遍歷的一個(gè)典型應(yīng)用——無權(quán)圖中求兩個(gè)頂點(diǎn)之間的最短路徑，因?yàn)閺V度優(yōu)先遍歷是按照距離起始結(jié)點(diǎn)的邊數(shù)為優(yōu)先級(jí)遍歷的，當(dāng)遍歷到結(jié)點(diǎn)v時(shí)一定起始節(jié)點(diǎn)u到結(jié)點(diǎn)v經(jīng)過邊數(shù)最少的一條路徑，即最短路徑。
對(duì)應(yīng)的算法如下(這里求路徑的方式不同于前面的兩種方式，而是采用記錄擴(kuò)展過程中前繼節(jié)點(diǎn)的方式，然后通過前繼節(jié)點(diǎn)找到最短路徑)：
//求圖G中從頂點(diǎn)u到頂點(diǎn)v的最短路徑path void ShortPath(ALGraph *G,int u,int v,vector<int> &path){ ArcNode *p; int w;queue<int>qu;//存放需要訪問的結(jié)點(diǎn) int pre[MAXV];//pre[i]表示編號(hào)為i的結(jié)點(diǎn)在廣度優(yōu)先遍歷過程中,通過哪個(gè)結(jié)點(diǎn)擴(kuò)展到編號(hào)為i的結(jié)點(diǎn)(前繼結(jié)點(diǎn)編號(hào)) int visited[MAXV];//標(biāo)記結(jié)點(diǎn)是否被訪問過 memset(visited,0,sizeof(visited));//初始化標(biāo)記用的數(shù)組 qu.push(u); visited[u]=1;//標(biāo)記初始結(jié)點(diǎn)v已經(jīng)被訪問pre[u]=-1;//初始結(jié)點(diǎn)作為遞歸樹的根,前繼結(jié)點(diǎn)的編號(hào)為-1while (!qu.empty()){ //出隊(duì)首結(jié)點(diǎn)進(jìn)行訪問并進(jìn)行標(biāo)記w=qu.front(); qu.pop(); visited[w]=1; //當(dāng)前訪問的結(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)v,通過前繼結(jié)點(diǎn)找到路徑path if (w==v){int d=v;while (d!=-1){path.push_back(d); d=pre[d];} return;}//遍歷結(jié)點(diǎn)對(duì)應(yīng)的單鏈表,尋找未訪問過的相鄰結(jié)點(diǎn)加入隊(duì)列//并且記錄前繼結(jié)點(diǎn)的編號(hào) p=G->adjlist[w].firstarc;while (p!=NULL){if (visited[p->adjvex]==0){qu.push(p->adjvex); pre[p->adjvex]=w;}p=p->nextarc;}} }保存的路徑是逆序的，輸出路徑時(shí)需要反向輸出。
求解迷宮問題
給定一個(gè)n*n的迷宮圖，例如下面8*8的迷宮圖：
OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXO
其中O表示可以走的方塊，X表示障礙方塊，我們假設(shè)入口為最左上角方塊，出口為最右下角方塊，設(shè)計(jì)一個(gè)程序求入口到出口的路徑。
我們將每個(gè)可走的方塊看作一個(gè)節(jié)點(diǎn)，如果兩個(gè)方塊上下左右相鄰則認(rèn)為他們之間存在邊，于是這個(gè)迷宮就轉(zhuǎn)化成了圖結(jié)構(gòu)，問題就轉(zhuǎn)化為了在圖結(jié)構(gòu)中求解左上角方格對(duì)應(yīng)結(jié)點(diǎn)到右下角方格對(duì)應(yīng)結(jié)點(diǎn)的路徑。
求解路徑的方法就是廣度優(yōu)先遍歷和寬度優(yōu)先遍歷，因?yàn)槭菙?shù)據(jù)結(jié)構(gòu)中介紹過的問題這里不再做贅述。
值得一提的是，迷宮問題標(biāo)記策略是將訪問過的O方格修改成星號(hào)方格，然后在回溯時(shí)修改回O方格。
那為什么這里的標(biāo)記需要在回溯時(shí)取消標(biāo)記，而前面的BFS算法，DFS算法都不需要取消標(biāo)記呢？
BFS和DFS的目標(biāo)都是將與起始結(jié)點(diǎn)相通的結(jié)點(diǎn)按照一定的順序進(jìn)行訪問，不會(huì)出現(xiàn)一條分支無法訪問，而另一條分支可以訪問卻被前一條無法訪問的分支“擋路”的情況。
求解迷宮問題用的也是BFS和DFS算法，只是我們這樣直接通過修改進(jìn)行標(biāo)記，就不需要將未標(biāo)記過的結(jié)點(diǎn)存儲(chǔ)起來進(jìn)行標(biāo)記，可以節(jié)省一定的空間開銷。取消標(biāo)記不是為了避免“擋路”情況的出現(xiàn)。
總結(jié)
- 上一篇： internal compiler er
- 下一篇： C语言，十进制转化为二进制。