第三章-蠻力法課件

算法分析與設(shè)計(jì)

AnalysisandDesignofComputerAlgorithms第三章蠻力法BruteForce.蠻力法就像寶劍不是撬棍一樣，科學(xué)也很少使用蠻力。——EdwardLytton認(rèn)真做事常常是浪費(fèi)時(shí)間?！猂obertByrne蠻力法是一種簡(jiǎn)單直接地解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。

2.蠻力法的優(yōu)點(diǎn)可以用來解決廣闊領(lǐng)域的問題對(duì)于一些重要的問題，它可以產(chǎn)生一些合理的算法解決問題的實(shí)例很少時(shí)，它讓你花費(fèi)較少的代價(jià)可以解決一些小規(guī)模的問題可以作為其他高效算法的衡量標(biāo)準(zhǔn)3.教學(xué)內(nèi)容選擇排序和冒泡排序順序查找和蠻力字符串匹配最近對(duì)核凸包問題的蠻力算法窮舉查找要求掌握蠻力法的基本思想，了解排序和查找問題的蠻力算法。

4.選擇排序A[min]

5.冒泡排序算法BubbleSort(A[0..n-1])//該算法用冒泡排序?qū)?shù)組A[0..n-1]排序//輸入：一個(gè)可排序的數(shù)組A//輸出：非降序排列的數(shù)組fori0ton-2doforj0ton-2-idoifA[j+1]<A[j]swapA[j]andA[j+1]

6.順序查找

7.蠻力字符串匹配

8.蠻力字符串匹配Θ(n+m)=Θ(n)

9.最近對(duì)問題

10.凸包問題定義對(duì)于平面上的一個(gè)點(diǎn)集合（有限或無限），如果以集合中任意兩點(diǎn)P和Q為端點(diǎn)的線段都屬于這個(gè)集合，則這個(gè)集合是凸的。定義一個(gè)點(diǎn)集合S的凸包是包含S的最小凸集合。

11.凸包問題定理任意包含n>2個(gè)點(diǎn)（不共線）的集合S的凸包是以S中的某些點(diǎn)為頂點(diǎn)的凸多邊形。凸包問題是為一個(gè)n個(gè)點(diǎn)的集合構(gòu)造凸包的問題。極點(diǎn)：對(duì)于任何一集合中的點(diǎn)為端點(diǎn)的線段來說，它們不是這種線段的中點(diǎn)。對(duì)于一個(gè)n個(gè)點(diǎn)集合中的兩個(gè)點(diǎn)Pi和Pj，當(dāng)且僅當(dāng)該集合中的其他點(diǎn)都位于穿過這兩點(diǎn)的直線的同一邊時(shí)它們的連線是該集合凸包邊界的一部分。直線方程：ax+by=ca=y2-y1,b=x1-x2,c=x1y2-y1x2

12.窮舉查找旅行商問題

13.窮舉查找背包問題

14.窮舉查找分配問題N個(gè)任務(wù)分配給n個(gè)人，任務(wù)j分配給人i的成本是C[I,j]

15.小結(jié)蠻力法是一種簡(jiǎn)單直接地解決問題的方法，通常直接基于問題的描述和所涉及的概念定義。蠻力法的主要優(yōu)點(diǎn)是它廣泛的適用性和簡(jiǎn)單性；它的主要缺點(diǎn)是大多數(shù)蠻力算法的效率都不高。除了相關(guān)問題的一些規(guī)模非常小的實(shí)例，窮舉查找法幾乎是不實(shí)用的。

16.習(xí)題3.2-10找詞游戲.習(xí)題3.2-11海戰(zhàn)游戲.習(xí)題3.4-9幻方幻方是我國(guó)古代的一種智力游戲，它是在N×N的矩陣方格中填入1...N2

的正整數(shù)，使得其每行每列及對(duì)角線的和相等。很明顯，這個(gè)和對(duì)某一階幻方是一個(gè)定值。設(shè)此值為SN，則不難解出：SN=

N2·(N2+1)/2N=N·(N2+1)/2。.外延法(由巴謝提出)構(gòu)造奇階幻方.H·Coxeter構(gòu)造幻方的方法首先在正方形最上面一行的正中間的小方格內(nèi)填寫1，然后到它的左上方的小格內(nèi)填寫下一個(gè)數(shù)(