蠻力法演示文稿

蠻力法演示文稿目前一頁\總數二十六頁\編于十二點1蠻力法的設計思想蠻力法是指采用遍歷（掃描）技術，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解。依次處理所有元素是蠻力法的關鍵，為了避免陷入重復試探，應保證處理過的元素不再被處理。目前二頁\總數二十六頁\編于十二點蠻力法（枚舉法、窮舉法，暴力法）要求設計者找出所有可能的情況，然后選擇其中一種情況，若該情況不可行（或不是最優(yōu)解）則試探下一種可能的情況。蠻力法是一種直接解決問題的方法，常常直接基于問題的描述和所設計的概念定義?！傲Α薄赣嬎銠C的能力，而不是人的智力。蠻力法常常是最容易應用的方法。求an（n為非負整數）用連續(xù)整數檢測算法計算GCD(m,n)關于蠻力法思考目前三頁\總數二十六頁\編于十二點蠻力法不是一個最好的算法（巧妙和高效的算法很少出自蠻力）,但當我們想不出更好的辦法時,它也是一種有效的解決問題的方法。它可能是惟一一種幾乎什么問題都能解決的一般性方法，常用于一些非?；尽⒌质种匾乃惴?。關于蠻力法思考目前四頁\總數二十六頁\編于十二點蠻力法的優(yōu)點邏輯清晰，編寫程序簡潔對于一些重要的問題（比如：排序、查找、矩陣乘法和字符串匹配），可以產生一些合理的算法解決問題的實例很少時，可以花費較少的代價可以解決一些小規(guī)模的問題（使用優(yōu)化的算法沒有必要，而且某些優(yōu)化算法本身較復雜）可以作為其他高效算法的衡量標準目前五頁\總數二十六頁\編于十二點使用蠻力法的幾種情況搜索所有的解空間搜索所有的路徑直接計算模擬和仿真目前六頁\總數二十六頁\編于十二點一個簡單的例子——百元買百雞問題目前七頁\總數二十六頁\編于十二點根據問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時一一列舉出的情況數目很大，如果超過了我們所能忍受的范圍，則需要進一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數目。用蠻力法解決問題，通常可以從兩個方面進行算法設計：1）找出枚舉范圍：分析問題所涉及的各種情況。2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達式表示。蠻力法解題步驟目前八頁\總數二十六頁\編于十二點思考下面問題：找出枚舉范圍和約束條件思路：枚舉范圍：100—999，共900個。約束條件：設三位數的百位、十位、個位的數字分別為x，y，z。則有x2+y2+z2≤10,進而1≤x≤3,0≤y≤3,0≤z≤3。求所有的三位數,它除以11所得的余數等于它的三個數字的平方和.解：所求三位數必在以下數中：

100，101，102，103，110，111，112，

120，121，122，130，200，201，202，

211，212，220，221，300，301，310。不難驗證只有100，101兩個數符合要求。目前九頁\總數二十六頁\編于十二點2查找問題中的蠻力法—順序查找思路：順序查找從表的一端向另一端逐個將元素與給定值進行比較，若相等，則查找成功，給出該元素在表中的位置；若整個表檢測完仍未找到與給定值相等的元素，則查找失敗，給出失敗信息。目前十頁\總數二十六頁\編于十二點101524612354098550123456789i查找方向101524612354098550123456789i查找方向哨兵K101524612354098550123456789i查找方向2查找問題中的蠻力法—順序查找目前十一頁\總數二十六頁\編于十二點intSeqSearch1(intr[],intn,intk){i=n;while(i>0&&r[i]!=k)i--;returni;}intSeqSearch2(intr[],intn,intk){r[0]=k;i=n;while(r[i]!=k)i--;returni;}2查找問題中的蠻力法—順序查找目前十二頁\總數二十六頁\編于十二點2查找問題中的蠻力法—串的匹配BF算法KMP算法本趟開始位置S模式T

tjj回溯

si

……回溯i…i下一次開始位置i下一次開始位置j回溯next[j]目前十三頁\總數二十六頁\編于十二點3排序問題中的蠻力法—選擇排序選擇排序開始的時候，掃描整個序列，找到整個序列的最小記錄和序列中的第一個記錄交換，從而將最小記錄放到它在有序區(qū)的最終位置上，然后再從第二個記錄開始掃描序列，找到n-1個序列中的最小記錄，再和第二個記錄交換位置。一般地，第i趟排序從第i個記錄開始掃描序列，在n-i+1（1≤i≤n-1）個記錄中找到關鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。r1≤r2……≤ri-1riri+1…rmin…

rn

有序區(qū)無序區(qū)已經位于最終位置rmin為無序區(qū)的最小記錄交換目前十四頁\總數二十六頁\編于十二點3排序問題中的蠻力法—選擇排序voidSelectSort(intr[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)if(r[j]<r[index])index=j;if(index!=i)r[i]←→r[index];}}目前十五頁\總數二十六頁\編于十二點3排序問題中的蠻力法—起泡排序voidBubble1(intr[],intn){for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)if(r[j]>r[j+1])r[j]←→r[j+1]；

}voidBubble3(intr[],intn){exchange=n;while(exchange)

{bound=exchange;exchange=0；

for(j=1;j<bound;j++)

if(r[j]>r[j+1])

{r[j]←→r[j+1]；

exchange=j；

}}}目前十六頁\總數二十六頁\編于十二點用蠻力法設計的算法，一般來說，經過適度的努力后，都可以對算法的第一個版本進行一定程度的改良，改進其時間性能，但只能減少系數，而數量級不會改變。蠻力法一般觀點目前十七頁\總數二十六頁\編于十二點4組合問題中的蠻力法—0/1背包問題問題描述：給定n個重量為{w1,w2,…

,wn}、價值為{v1,v2,…

,vn}的物品和一個容量為C的背包，求這些物品中的一個最有價值的子集，且要能夠裝到背包中。目前十八頁\總數二十六頁\編于十二點4組合問題中的蠻力法—0/1背包問題序號子集重量價值序號子集重量價值1172183194205216227238249251026112712281329143015311632對于一個具有n個元素的集合,其子集數量是2n,所以,不論生成子集的算法效率有多高,蠻力法都會導致一個Ω(2n)的算法.目前十九頁\總數二十六頁\編于十二點4組合問題中的蠻力法—任務分配問題問題描述：假設有n個任務需要分配給n個人執(zhí)行，每個任務只分配給一個人，每個人只分配一個任務，且第j個任務分配給第i個人的成本是C[i,j]（1≤i,j≤n），任務分配問題要求找出總成本最小的分配方案。

目前二十頁\總數二十六頁\編于十二點4組合問題中的蠻力法—任務分配問題可以用一個n元組(j1,j2,…,jn)來描述任務分配問題的一個可能解，其中第i個分量ji（1≤i≤n）表示在第i行中選擇的列號，因此用蠻力法解決任務分配問題要求生成整數1~n的全排列，然后把成本矩陣中相應元素相加來求得每種分配方案的總成本，最后選出具有最小和的方案。目前二十一頁\總數二十六頁\編于十二點5圖問題中的蠻力法—TSP問題TSP問題是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。求解:一個加權連通圖中的最短哈密頓回路問題。TSP問題有著簡單的表述、重要的應用、以及和其他NP完全問題的重要關系，它在近100年的時間里強烈地吸引著計算機科學工作者.

目前二十二頁\總數二十六頁\編于十二點5圖問題中的蠻力法—TSP問題序號路徑路徑長度是否最短1a→b→c→d→a18否2a→b→d→c→a11是3a→c→b→d→a23否4a→c→d→b→a11是5a→d→b→c→a23否6a→d→c→b→a18否18abdc2357目前二十三頁\總數二十六頁\編于十二點蠻力法求解TSP問題存在的問題注意到圖中有3對不同的路徑，對每對路徑來說，不同的只是路徑的方向，因此，可以將這個數量減半，則可能的解有(n-1)!/2個。隨著n的增長，TSP問題的可能解也在迅速地增長。一個10城市的TSP問題有大約180,000個可能解。一個20城市的TSP問題有大約

60,000,000,000,000,000個可能解。一個50城市的TSP問題有大約1062個可能解，而一個行星上也只有1021升水。蠻力法求解TSP問題，只能解決問題規(guī)模很小的實例。目前二十四頁\總數二十六頁\編于十二點6幾何問題中的蠻力法—凸包問題對于平面上的一個點的有限集合，如果以集合中任