信息學(xué)入門經(jīng)典ch3蠻力法

1、2022/8/26LingJie/GDUT1第3章 蠻力法主要內(nèi)容： 3.1 選擇排序和冒泡排序 3.2 順序查找和蠻力字符串匹配 3.3 最近對和凸包問題的蠻力算法 3.4 窮舉查找2022/8/26LingJie/GDUT23.1 選擇排序和冒泡排序 蠻力算法是一種簡單直接地解決問題的方法.一般高效和巧妙的算法很少來自蠻力法,但蠻力法具有如下優(yōu)點:(1)應(yīng)用范圍廣,(2)不受實例規(guī)模的限制,(3)當(dāng)要解決的問題實例不多,設(shè)計更高效算法的代價太大時可選用,(4)對解決一些小規(guī)模的問題實例仍然有效,(5)可作為衡量其他算法的參照. 2022/8/26LingJie/GDUT33.1.1 選擇排

2、序和冒泡排序問題:給定一個可排序的n元序列,將它們按照非降序方式重新排列.已開發(fā)出數(shù)十種排序算法. 2022/8/26LingJie/GDUT41、選擇排序原理：掃描整個列表，找出最小元素，然后將最小元素與第一個元素交換位置。從第二個元素開始掃描列表，找出n-1個元素中的最小元素，將最小元素與第二個元素交換位置，如此類推，做n-1遍后排序結(jié)束。算法偽代碼：SelectionSort(A0.n-1) for i=0 to n-2 do min=i for j=i+1 to n-1 do if AjAmin min=j swap Ai and Amin2022/8/26LingJie/GDUT5例

3、題：對序列 89,45,68,90,29,34,17用選擇排序 算法進(jìn)行排序第1遍： 89，45，68，90，29，34，17 /求最小元素 17，45，68，90，29，34，89 /交換第2遍： 17，45，68，90，29，34，89 17，29，68，90，45，34，89第3遍： 17，29，68，90，45，34，89 17，29，34，90，45，68，89第4遍： 17，29，34，90，45，68，89 17，29，34，45，90，68，89第5遍： 17，29，34，45，90，68，89 17，29，34，45，68，90，89第6遍： 17，29，34，45，68，9

4、0，89 17，29，34，45，68，89，90 /排序結(jié)束2022/8/26LingJie/GDUT6選擇排序的算法分析： 基本操作：比較AjAmin 比較次數(shù)C(n)：于是 C(n)(n2)鍵值交換次數(shù)最壞情況：(n)2022/8/26LingJie/GDUT72、冒泡排序原理：比較相鄰的元素，將大的元素交換到右邊的位置，重復(fù)多次后，最大元素就“沉淀”到列表的最后一個位置。第二遍將第二大元素沉下去，n-1遍后結(jié)束。算法偽代碼： BubbleSort(A0.n-1) for i=0 to n-2 do for j=0 to n-2-i do if Aj+1Aj swap Aj and Aj

5、+1 2022/8/26LingJie/GDUT8例題：對序列 89,45,68,90,29,34,17用冒泡排序算法進(jìn)行排序第1遍： 8945，68，90，29，34，17 /比較相鄰元素 45，89 68，90，29，34，17 45，68，89 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 /比較n-1=6次第2遍： 45 68，89，29，34，17，90 45，68 89，29，34，17，90 45，68，29 89，34，17，90 4

6、5，68，29 ，89 34，17，90 45，68，29 ，34，89 17，90 45，68，29 ，34，17，89， 90 /比較n-2=5次2022/8/26LingJie/GDUT9冒泡排序的算法分析： 基本操作：比較AjAj+1 比較次數(shù)C(n)：于是 C(n)(n2) 鍵值交換次數(shù)最壞情況：(n2)，次數(shù) 如對列表比較一遍后未出現(xiàn)交換元素位置，則算法停止。2022/8/26LingJie/GDUT10ALGORITHM BubbleSort( A0,n 1 )/ 冒泡排序算法在數(shù)組上的應(yīng)用/ 輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集/ 輸出：按升序排列的數(shù)組Afor i 0 to

7、 n 2 dofor j 0 to n 2 i doif Aj+1 Aj swap(Aj, Aj+1)改進(jìn)的冒泡算法如下：ALGORITHM BubbleSortImproved( A0,n 1 )/ 冒泡排序算法的改進(jìn)/ 輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集/ 輸出：按升序排列的數(shù)組Afor i 0 to n 2 doflag True for j 0 to n 2 i doif Aj+1 Ajswap(Aj, Aj+1)flag False / 如果在某一輪的比較中沒有交換，則flag為True，算法結(jié)束if flag = True return2022/8/26LingJie/GDUT

8、113.2 順序查找和蠻力字符串匹配1、順序查找問題： 已知有n個元素的數(shù)組A0.n. 給定元素K,要求找出一個下標(biāo)i,使得Ai=K.輸出第一個值等于K的元素的位置，找不到返回-1.2022/8/26LingJie/GDUT12算法 SequentialSearch(A0.n-1,K) i:=0; while AiK and in do i:=i+1; if Ai=K then return i else return -1改進(jìn)算法 SequentialSearch2(A0.n-1,K) An=K; i:=0; while AiK do i:=i+1; if in then return i

9、else return -12022/8/26LingJie/GDUT132、蠻力字符串匹配問題： 從文本中尋找匹配模式的子串，即求出第一個匹配模式的子串在文本中的開始位置（子串最左元素的下標(biāo)）。其中：文本給定的由n個字符組成的串 模式指定的由m個字符組成的串蠻力算法： 將模式對準(zhǔn)文本的前m個字符從左往右進(jìn)行比對，如果其中有一個字符不匹配，模式往有移動一位繼續(xù)下一個m個字符的比對。2022/8/26LingJie/GDUT142022/8/26LingJie/GDUT15算法 BruteForceStringMatch(T0.n-1,P0.m-1 for i=0 to n-m do j=0 w

10、hile jm and Pj=Ti+j do j=j+1 if i=m return i return -1/文本T0.n-1長度為n/模式P0.m-1長度為m/查找不成功時返回-12022/8/26LingJie/GDUT16字符串匹配的例題 文本 NOBODY_NOTICED_HIM 模式 NOT算法執(zhí)行過程 N O B O D Y _ N O T I C E D _ H I M N O T i=0, j=3不匹配發(fā)生在第0+3位 N O T i=1 不匹配發(fā)生在第1+1位 N O T i=2 不匹配發(fā)生在第2+1位 N O T 不匹配發(fā)生在第3+1位 N O T 不匹配發(fā)生在第4+1位

11、N O T 不匹配發(fā)生在第5+1位 N O T 不匹配發(fā)生在第6+1位 N O T 匹配開始在第7+1位2022/8/26LingJie/GDUT17蠻力字符串匹配算法分析： 最壞的情形是模式須移動n-m+1次，每次移動模式之前，做足m次比對才發(fā)現(xiàn)不匹配（即第i+m位不匹配），因此，在最壞情況下，該算法屬于(nm)。 平均效率可達(dá)到(n+m) =(n)。2022/8/26LingJie/GDUT183.3 最近對和凸包問題的蠻力算法問題描述： 給定平面S上n個點，找其中的一對點，使得在n(n-1)/2個點對中，該點對的距離最小。 在實際應(yīng)用中，常利用點或者圓等簡單的幾何對象代表現(xiàn)實世界中的實體

12、。例如，在空中交通控制問題中，若將飛機(jī)作為空間中移動的一個點來看待，則具有最大碰撞危險的2架飛機(jī),就是空間中最接近的一對點。 2022/8/26LingJie/GDUT19 記（P.x，P.y）為點P的坐標(biāo)值，則兩個點Pi、Pj之間的距離公式為： 對于給定的n個點，找出其中兩個距離最小的點的問題直觀的想法很簡單，只要把所有的點兩兩組合，比較它們之間的距離即可以得到距離最小的一對。 2022/8/26LingJie/GDUT20算法BruceForceClosestPoints( P ) / 輸入：n個點的數(shù)組P，Pi(xi , yi), i=1,2,n / 輸出：兩個最近點的下標(biāo)index1和

13、index2 dmin for i 1 to n-1 do for j i+1 to n do d sqrt(xi-xj)2+(yi-yj)2) if d 2個點的集合S的凸包，是以S中的某些點位頂點的凸多邊形。特別，如果所有點共線，則多邊形退化為一條直線，它的兩個端點仍在S中。極點： 凸集的極點是指不會出現(xiàn)在集合中任何線段的中間的點。 凸多邊形的頂點是極點。2022/8/26LingJie/GDUT25凸集定義： 設(shè)S是平面點集，如果S中任意兩點的連線都屬于該集合，則稱S是凸的。凸包定義： 一個點集S的凸包是指包含S的最小凸集。 顯然，如果S是凸的，則S的凸包就是S本身。凸包問題： 給定一個

14、n個點的點集S，求S的凸包。2022/8/26LingJie/GDUT26凸包問題的解法 設(shè)點集大小為n，首先將其中的點兩兩配對，得到直線段條；然后對每一條直線段檢查其余的n-2個點的相對于該直線段的正負(fù)性，如果它們都有相同的正負(fù)性，那么這條直線段屬于凸多邊形的邊，其頂點是極點。 設(shè)直線方程為 ax+by=c 則 使ax+by-c0的點在直線右（上）方 使ax+by-c0的點在直線左（下）方2022/8/26LingJie/GDUT272022/8/26LingJie/GDUT283.4 窮舉法窮舉法是一種簡單的蠻力方法，它要求生成所有可能的可行解，再從中選擇最優(yōu)解。原理簡單，大多數(shù)情況下是不

15、可行的。2022/8/26LingJie/GDUT291、旅行商問題TSP問題： 給定n個城市相互之間的距離，求一條能走遍n個城市的最短路徑，使我們能從任一城市開始，訪問每個城市只一次后回到起點。2022/8/26LingJie/GDUT30abcd827534n=4的旅行商問題的一個實例 路線 長度 abcda 2+3+7+5 = 17abdca 2+4+7+8 = 21acbda 8+3+4+5 = 20acdba 8+7+4+2 = 21adbca 5+4+3+8 = 20adcba 5+7+3+2 = 17所有可能的回路有多少條？2022/8/26LingJie/GDUT312、背包問

16、題問題： 給定n 個重量為w1、w2、wn，價值為v1、v2、vn的物品和一個承重為W的背包，要求將物品裝入背包使背包的價值最大。2022/8/26LingJie/GDUT32舉例: 物品類型 重量 價值 背包承重W=16 1 2 $20 2 5 $30 3 10 $50 4 5 $10所有可能的子集個數(shù)有2n個。窮舉法是(2n)的。2022/8/26LingJie/GDUT33Subset Total weight Total value 1 2 $20 2 5 $30 3 10 $50 4 5 $10 1,2 7 $50 1,3 12 $70 1,4 7 $30 2,3 15 $80 2,4 10 $40 3,4 15 $60 1,2,3 17 不可行 1,2,4 12 $60 1,3,4 17 不可行 2,3,4 20 不可行1,2,3,4 22 不可行2022/8/26LingJie/GDUT343、分配問題問題： 有n個任務(wù)需要分配給n個人執(zhí)行