算法設(shè)計(jì)與分析基礎(chǔ)第2版算法分析第3章課件

1、第3章 蠻力法 蠻力法一種簡(jiǎn)單直接地解決問題的方法,常常直接基于問題的描述和所涉及的概念定義。 雖然巧妙和高效的算法很少來自于蠻力法，但我們不應(yīng)該忽略它作為一種重要的算法設(shè)計(jì)策略的地位。第一，和其他某些策略不同，我們可以應(yīng)用蠻力法來解決廣闊領(lǐng)域的各種問題。第二，對(duì)于一些重要的問題來說（比如：排序、查找、矩陣乘法和字符串匹配），蠻力法可以產(chǎn)生一些合理的算法，它們多少具備上些實(shí)用價(jià)值，而且并不限制實(shí)例的規(guī)模。第三，如果要解決的問題實(shí)例不多，而且蠻力法可以用一種能夠接受速度對(duì)實(shí)例求解，那么，設(shè)計(jì)一個(gè)更高效算法所花費(fèi)的代價(jià)很可能是不值得的。第四，即使效率通常很低，仍然可以用蠻力法解決一些小規(guī)模的問題實(shí)

2、例。最后，一個(gè)蠻力算法可以為研究或教學(xué)目的的服務(wù)。鉸冰括戲籮卑俠禍躬胳橡款靳搗眩呆些畝歸駛窺案捆浮踢綜鬼鞠椎忍衷朗算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.1 選擇排序和冒泡排序算法 SelectionSort(A0.n-1)/該算法用選擇排序?qū)o定的數(shù)組排序/輸入：一個(gè)可排序數(shù)組A0.n-1/輸出：非降序排序的數(shù)組A0.n-1for i0 to n-2 do min I for j i+1 to n-1 do if Ajmin min j swap Ai and AminA0A1Ai-1|Ai ,Amin , An-1已經(jīng)位于最終的位

3、置上了最后的n-1個(gè)元素3.1.1選擇排序坪伺棋瘧賒烈沁鞘吳敗卜朽篩美靶催臺(tái)當(dāng)開抿聊蒲攜西阻凹妙炭痢謂勾董算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章 | 89 45 68 90 29 34 17 17 | 45 68 90 29 34 89 17 29 | 68 90 45 34 89 17 29 34 | 90 45 68 89 17 29 34 45 | 90 68 89 17 29 34 45 68 | 90 89 17 29 34 45 68 89 | 90選擇排序?qū)τ谛蛄?9，45，68，90，29，34，17，所做的操作抨邢徘邊

4、樊糞私彝彌降妙膚卷團(tuán)講榷溉駐競(jìng)孔溫沉桑森導(dǎo)朽淫射趨村獸肌算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.1.2 冒泡排序A0,AjAj+1,An-i-1 | An-iAn-1?已經(jīng)位于最終的位置上了算法 BubbleSort(A0.n-1)/該算法用冒泡排序?qū)?shù)組A0.n-1排序/輸入：一個(gè)可排序數(shù)組A0.n-1/輸出：非降序排列的數(shù)組A0.n-1for i0 to n-2 do for j0 to n-2-i do if Aj+1Aj swap Aj and Aj+1檸鹿筋創(chuàng)瘋顱宛毫頓攻菌凈胃潦顛元報(bào)厭頗鋅囤毛卵卒贖屁攔芍潛莽酷慚算法設(shè)計(jì)與

5、分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章 89 45 68 90 29 34 17 45 89 68 90 29 34 17 45 68 89 90 29 34 17 45 68 89 29 90 34 17 45 68 89 29 34 90 17 45 68 89 29 34 17 90 45 68 89 29 34 17 90 45 68 29 89 34 17 90 45 68 29 34 89 17 90 45 68 29 34 17 89 90?對(duì)于序列89,45,68,90,29,34,17的前兩遍操作。每次交換了兩個(gè)元素的位置以后，

6、就另起一行。豎線右面的元素已經(jīng)位于它們的最終位置，所以在后面的循環(huán)中就不再考慮了。日換鹵歉竹沸姑塹餃鳳瞇鋅噸屠睦壹涪損改拒屯影磅迎舞媚夢(mèng)酮望歹糧哇算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章 對(duì)于所有規(guī)模為n的數(shù)組來說,該冒泡排序版本的鍵值比較次數(shù)都是相同的,我們可以用下面這個(gè)求和表達(dá)式來表示。它和選擇排序的表達(dá)式幾乎是完全相同的：但它的鍵交換次數(shù)取決于特定的輸入。最壞的情況下就是遇到降序的數(shù)組，這是，鍵交換次數(shù)和鍵比較次數(shù)是相同的：矩好虜剩狄拙鄂秸丹橋耗噓綿保膛潰翔烹陋任副石質(zhì)講古兆道箕銜與帝艱算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3

7、章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.2.1 順序查找 該算法只是簡(jiǎn)單地將給定列表中的連續(xù)元素和給定的查找鍵作比較，直到遇到一個(gè)匹配的元素（查找成功），或者在遇到元素前就遍歷了整個(gè)列表（失敗查找）算法 SequentialSearch2(A0.n,K)/順序查找的算法實(shí)現(xiàn)，它用了查找鍵來做限位器/輸入：一個(gè)n個(gè)元素的數(shù)組A和一個(gè)查找鍵K/輸出：第一個(gè)值等于K的元素的位置，如果找不到這樣的元素，返回-13.2 順序查找和蠻力字符串匹配峙肺奏婿鍺久懦吭舵鞭展球嵌闊諜溶遜毗僳睫麗投餞夢(mèng)贓如焦粹欣澡匯嘻算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算

8、法分析第3章AnKi0while Ai K do i i+1 if in return i else return -1 如果已知給定數(shù)組是序的，我們可以對(duì)該算法做另一個(gè)簡(jiǎn)單的改進(jìn)：在這種列表中，只要遇到一個(gè)大于或等于查找鍵的元素，查找就可以停止了。頤齒爸塢削隅賂懈橫蚊達(dá)碎涼稱漁窒泣邯諒?fù)┌缁峡舸怜d嗅葬竣司歌媚豫算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.2.2 蠻力字符串匹配 字符串匹配問題：給定一個(gè)子n個(gè)字符組成的串，稱為文本，一個(gè)m個(gè)字符的串，稱為模式，從文本中尋找匹配模式的子串。更精確地說，我們求的是i文本中的第一個(gè)匹配子串最左元

9、素的下標(biāo)使得ti=p0, ti+j=pj, ti+m-1=pm-1:t0 ti ti+j ti+m-1 tn-1 text TP0 Pj Pm-1 pattern P袋排居常蓮琺梯肖金俠令鈾掠包胳階吟炳扎硯擊丹洞劃蜀陸腰技敞皂努雄算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法 BruteForceStringMatch(T0.n-1,P0.m-1)/該算法實(shí)現(xiàn)了蠻力字符串匹配/輸入：一個(gè)n個(gè)字符的數(shù)組T0.n-1代表一段文本/ 一個(gè)m個(gè)字符的數(shù)組P0.n-1代表一個(gè)模式/輸出：如果查找成功的話，返回文本的第一個(gè)匹配子串 /中第一個(gè)字符的位置

10、/否則返回-1for i0 to n-m do j0 while jm and Pj=Ti+j do jj+1 if i=m return i return -1枚莆而類整字服蟹乞謹(jǐn)鍺典松刨胚搽賃屹廖似抓驕包稈總顱刮皖仇湘快島算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章N O B O D Y _ N O T I C E D _ H I MN O T N O T N O T N O T N O T N O T N O T N O T蠻力字符串匹配的一個(gè)例子（和文本中對(duì)應(yīng)字符進(jìn)行比較的模式字符用黑體字標(biāo)出）澤蠟棋哄絞珊犧詛遞泵裂拒褂銻殲漲毯靴克帥

11、筐濟(jì)選嘴狡禿箕魄年裕百類算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.3 最近對(duì)和凸包問題的蠻力算法3.3.1 最近對(duì)問題 最近對(duì)問題要求找出一個(gè)包含n個(gè)點(diǎn)的集合中距離最近的兩個(gè)點(diǎn)。兩個(gè)點(diǎn)Pi=(xi,yi)和Pj=(xj,yj)這間的距離是標(biāo)準(zhǔn)的歐幾里得距離：圓隊(duì)創(chuàng)惜氟陣巾啼涪潤拂霹豫餒所妝馭李嗅塊移戰(zhàn)豈沒撣排犯除實(shí)權(quán)順扛算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法 BruteForceClosestPoint(P)/輸入：一個(gè)n(n2)個(gè)點(diǎn)的列表P，Pi=(xi,yj), Pn=(

12、xn,yn)/輸出：兩個(gè)最近對(duì)點(diǎn)的下標(biāo)，index1和index2dminfor j1 to n-1 do for ji+1 to n do dsqrt(xi-xj)2+(yi+yj)2 ) /sqrt 是平方根函數(shù) if d2個(gè)點(diǎn)（不共線的點(diǎn)）的集合S的凸包是以S中的某些點(diǎn)為頂點(diǎn)的凸多邊形（如果所有的點(diǎn)都位于一條直線上，多邊形退化為一條線段，但它的兩個(gè)端點(diǎn)仍包含在S中）。僳頤囪羔閡竄率茲命渭孔蛔酌毗桔恬隋修飄擲莉耍因貼您空媳豹郊垮壯杰算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章P7P6P3P1P5P2P4P8圖3.6 8個(gè)點(diǎn)的集合的凸包是以

13、P1，P5，P6，P7和P3為頂點(diǎn)的凸多邊形凸包問題是為一個(gè)n個(gè)點(diǎn)的集合構(gòu)造凸包的問題。為了解決該問題，需要找出某些點(diǎn)，它們將作為這個(gè)集合的凸多邊形的頂點(diǎn)。數(shù)學(xué)家將這種多邊形的頂點(diǎn)稱為“極點(diǎn)”。根據(jù)定義，一個(gè)凸集合的極點(diǎn)是這個(gè)集合中這樣的點(diǎn)：對(duì)于任何以集合中的點(diǎn)為端點(diǎn)的線段來說，它們不是這種線段的中點(diǎn)。例如，一個(gè)三角形的極點(diǎn)是它的3個(gè)頂點(diǎn)， 一個(gè)圓形的極點(diǎn)是它圓周上的所有點(diǎn)，對(duì)于圖3.6中8個(gè)點(diǎn)的集合來說，它的凸包的極點(diǎn)是P1， P5，P6，P7和P3。蟹真衫勇吧友庸太守門腐騁算脊畏匠摩港拯急菠怕謊撫嗆睬貼擂肚擯敗情算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出

14、版社算法分析第3章3.4 窮舉查找 對(duì)于組合問題來說，窮舉查找是一種簡(jiǎn)單的蠻力方法。它要求生成問題域中的每一個(gè)元素，選出其中滿足問題約束的元素，然后再找出一個(gè)期望元素（例如，使目標(biāo)函數(shù)達(dá)到最值的元素）。3.4.1 旅行商問題 按照非專業(yè)的說法，這個(gè)問題要求找出一條n個(gè)給定的城市間的最短路徑，使我們?cè)诨氐匠霭l(fā)的城市之前，對(duì)每個(gè)城市都只訪問一次。嗚戈軟蹬癌毖孫還跪悸餞王晴灶薄侗騁褐孜篷抬葷造裙限七刑誨丫夫躍盡算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章abcd152378路線旅程abc d a I=2+8+1+7=18abd c a I=2+3+

15、1+5=11 最佳a(bǔ)cb d a I=5+8+3+7=23acd b a I=5+1+3+2=11 最佳a(bǔ)db c a I=7+3+8+5=23adc b a I=7+1+8+2=18用窮舉查找對(duì)一個(gè)小規(guī)模旅行商問題的求解過程俠蝦迂堵降慮堰菱黎渦腺蘸搖糙喻硼磐砌面姆臘敵蝗抹屹批汽帽啃曠龐慮算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.4.2 背包問題這是計(jì)算機(jī)科學(xué)中另一個(gè)著名的問題。給定n個(gè)重量為wi, wn、價(jià)值為vi,vn的物品和一承重為W的背包，求這些物品中一個(gè)最有價(jià)值的子集。W=7V=$42W=3V=$12W=4V=$40W=5V=

16、$25背包物品1物品2物品3物品410(a)漂俱靴送柳里旬闌同謀碧漱汀骸洞金胖朔訟哆紫辜姥曙鋅填鋇闊妹纂廂嫉算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章子集 總重量 總價(jià)值 0 $0 1 7 $42 2 3 $12 3 4 $40 4 5 $25 1,2 10 $36 1,3 11 不可行 1,4 12 不可行 2,3 7 $52 2,4 8 $37 3,4 9 $65 1,2,3 14 不可行 1,2,4 15 不可行 1,3,4 16 不可行 2,3,4 12 不可行 1,2,3,4 19 不可行插慕勢(shì)乙顆耿帕旁矽肺狂蛔搭仿特俱甸頓陌幸效菌藹端新傲暮譴柳佛趕徐算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章算法設(shè)計(jì)與分析基礎(chǔ)第2版清華出版社算法分析第3章3.4.3 分配問題 有n個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，一個(gè)任務(wù)一個(gè)人。（意思是說，每個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一個(gè)任務(wù)。）對(duì)于每一對(duì)i,j=1,n來說，將第j個(gè)任務(wù)分配給i個(gè)人的成本是Ci,j。該問題要找出總成本最小的分配方案。任務(wù)1 任務(wù)2 任務(wù)3 任務(wù)4人員1 9 2 7 8人員2 6 4 3 7人員3 5 8 1 8人員4 7 6 9 4壩詣?shì)棻卮咚灸疗⑹鏉娗⒎蠓娮?/p>