課件3蠻力法數(shù)據(jù)分析與算法設(shè)計

數(shù)據(jù)分析與算法設(shè)計第3章蠻力法數(shù)據(jù)分析與算法設(shè)計第3章蠻力法22選擇排序和冒泡排序順序查找和蠻力字符串匹配最近對和凸包問題的蠻力算法窮舉查找深度優(yōu)先查找和廣度優(yōu)先查找選擇排序和冒泡排序順序查找和蠻力字符串匹配最近對和凸包問題的蠻力算法窮舉查找深度優(yōu)先查找和廣度優(yōu)先查找?????3.13.23.33.43.53蠻力法是一種簡單直接地解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。Justdoit!??蠻力法是一種簡單直接地解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。Justdoit!??–––指數(shù)(m,n)的連續(xù)整數(shù)檢測算法基于定義的矩陣乘法算法??一般高效和巧妙的算法很少來自蠻力法蠻力法優(yōu)點：–––應(yīng)用范圍廣能是不值得的可作為衡量其他算法的參照物––43.1選擇排序和冒泡排序?排序問題：給定一個可排序的n3.1選擇排序和冒泡排序?排序問題：給定一個可排序的n元素序列，將它們按照非降序方式重新排列已開發(fā)出幾十種排序算法?53.1.1選擇排序?原理：–掃描整個列表，找出最小元素，然后將最小元素與第一個元素交換位置。從第二個元素開始掃描列表，找出n-13.1.1選擇排序?原理：–掃描整個列表，找出最小元素，然后將最小元素與第一個元素交換位置。從第二個元素開始掃描列表，找出n-1個元素中的最小元素，將最小元素與第二個元素交換位置。如此類推，做n-1遍后排序結(jié)束。––?SelectionSort(A[0..n-1])fori=0ton-2domin=iforj=i+1ton-1doifA[j]<A[min]min=jswapA[i]andA[min]6例題：對序列{89,45,68,90,29,34,17}用選擇排序算法進(jìn)行排序?例題：對序列{89,45,68,90,29,34,17}用選擇排序算法進(jìn)行排序?{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}//求最小元素//交換?????//排序結(jié)束7???選擇排序算法的效率分析：比較次數(shù)???選擇排序算法的效率分析：比較次數(shù)C(n)：C(n)1(n1i)n(n1)n2 n1 n22i0ji1i0?于是C(n)∈Θ(n2)83.1.2冒泡排序?原理（比如：軍訓(xùn)排隊）––比較相鄰的元素，將大的元素交換到右邊的位置。列表的最后一個位置。第二遍將第二大元素沉下去––3.1.2冒泡排序?原理（比如：軍訓(xùn)排隊）––比較相鄰的元素，將大的元素交換到右邊的位置。列表的最后一個位置。第二遍將第二大元素沉下去––n-1遍后結(jié)束，排序完成算法偽代碼：?BubbleSort(A[0..n-1])fori=0ton-2doforj=0ton-2-idoifA[j+1]<A[j]swapA[j]andA[j+1]9例題：{89,45,68,90,29,34,17}用冒泡排序算法進(jìn)行排序例題：{89,45,68,90,29,34,17}用冒泡排序算法進(jìn)行排序{45，8968，90，29，34，17}{45，68，8990，29，34，17}{45，68，89，9029，34，17}{45，68，89，29，9034，17}{45，68，89，29，34，9017}//比較相鄰元素{45，68，89，29，34，17，90}//比較n-1=6次{45，6889，29，34，17，90}{45，68，2989，34，17，90}{45，68，29，8934，17，90}{45，68，29，34，8917，90}，34，17，89，90}//比較n-2=5次10?冒泡排序算法的效率分析：比較次數(shù)C(n)：n(n?冒泡排序算法的效率分析：比較次數(shù)C(n)：n(n1)2n2n2in2i0i0 j0C(n)1(n1i)于是C(n)∈Θ(n2)與選擇排序比較：原理、換位次數(shù)?問：冒泡排序最壞的情形是什么？ALGORITHMBubbleSort(A[0,…,n–1])冒泡排序算法在數(shù)組上的應(yīng)用輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集輸出：按升序排列的數(shù)組A?ALGORITHMBubbleSort(A[0,…,n–1])冒泡排序算法在數(shù)組上的應(yīng)用輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集輸出：按升序排列的數(shù)組A????????????????????i←0ton–2doforj←0ton–for–idoA[j]swap(A[j],2<ifA[j+1]A[j+1])改進(jìn)的冒泡算法如下：ALGORITHMBubbleSortImproved(A[0,…,n冒泡排序算法的改進(jìn)輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集輸出：按升序排列的數(shù)組A–1])i←0ton–2doflag←Trueforton–A[j+1]2–ido<A[j]forj←0ifswap(A[j],A[j+1])flag←False如果在某一輪的比較中沒有交換，則flag為True，算法結(jié)束ifflag=Truereturn123.2順序查找和蠻力字符串匹配?3.2.1順序查找問題：已知有n個元素的數(shù)組3.2順序查找和蠻力字符串匹配?3.2.1順序查找問題：已知有n個元素的數(shù)組A[0...n]，給定元素K，要求找出一個下標(biāo)i，滿足A[i]=K。輸出第一個值等于K的元素的位置，找不到返回-1。13?i:=0;whileA[i]≠Kandi<ndoi:=i+1;ifA[i]=Kthenreturnielse?i:=0;whileA[i]≠Kandi<ndoi:=i+1;ifA[i]=Kthenreturnielsereturn-1?A[n]=K;i:=0;//限位器whileA[i]≠Kdoi:=i+1;ifi<nthenreturnielsereturn-114?3.2.2蠻力字符串匹配問題從文本中尋找匹配模式的子串，即求出第一個匹配模式的子串在文本中的開始位置（子串最左?3.2.2蠻力字符串匹配問題從文本中尋找匹配模式的子串，即求出第一個匹配模式的子串在文本中的開始位置（子串最左元素的下標(biāo)）。其中：文本——給定的由n個字符組成的串?蠻力算法：將模式對準(zhǔn)文本的前m個字符從左往右進(jìn)行比對。如果其中有一個字符不匹配，模式往右移動一位，繼續(xù)下一個m個字符的比對。15目標(biāo)textt0tm+1t1t2tm-1tmtn-1……模式pattern：p0目標(biāo)textt0p1t1p2t2pm-1tm-1目標(biāo)textt0tm+1t1t2tm-1tmtn-1……模式pattern：p0目標(biāo)textt0p1t1p2t2pm-1tm-1…tm+1tmtn-1……p0t1p1…p2ti||p0pm-1…模式pattern：目標(biāo)textt0…ti+1||p1ti+m-1||pm-1tn-1…模式pattern：…16?算法BruteForceStringMatch(T[0..n-1],P[0..m-1]fori=0ton-mdo?算法BruteForceStringMatch(T[0..n-1],P[0..m-1]fori=0ton-mdoj=0whilej<mandP[j]=T[i+j]doj=j+1ifj=mreturnireturn-1//文本T[0..n-1]長度為n//模式P[0..m-1]長度為m//查找不成功時，返回-117????字符串匹配的例題NOT算法執(zhí)行過程NO????字符串匹配的例題NOT算法執(zhí)行過程NOBODY_NOTICED_HIMNOTNOTNOTNOTNOTi=0,j=2不匹配發(fā)生在第0+2位i=1i=2不匹配發(fā)生在第1+0位<——不匹配發(fā)生在第2+0位不匹配發(fā)生在第3+0位不匹配發(fā)生在第4+0位不匹配發(fā)生在第5+0位<——不匹配發(fā)生在第6+0位NOTNOTNOT<——匹配完成在第7+3位18?蠻力字符串匹配算法分析：最壞的情形是模式須移動?蠻力字符串匹配算法分析：最壞的情形是模式須移動n-m+1次，每次移動模式之前，做足m次比對才發(fā)現(xiàn)不匹配（即第i+m-1位不匹配），因此，在最壞情況下，該算法屬于Θ(nm)。平均效率可達(dá)到Θ(n+m)=Θ(n)。193.3最近對和凸包問題的蠻力算法3.3.1最近對問題給定平面S上n個點，找其中的一對點，使得在n(n-1)/2個點對中，該點對的距離最小。在實際應(yīng)用中，常利用點或者圓等簡單的幾何對象代表現(xiàn)實世界中的實體。例如，在空題中，若將飛機作為空間中移動的一個點來通控制問3.3最近對和凸包問題的蠻力算法3.3.1最近對問題給定平面S上n個點，找其中的一對點，使得在n(n-1)/2個點對中，該點對的距離最小。在實際應(yīng)用中，常利用點或者圓等簡單的幾何對象代表現(xiàn)實世界中的實體。例如，在空題中，若將飛機作為空間中移動的一個點來通控制問，則具有最大碰撞對點？的2架飛機,就是空間中最接近的一20?記（P.x，P.y）為點P的坐標(biāo)值，則兩個點Pi、Pj之間的距離公式為：d(P?記（P.x，P.y）為點P的坐標(biāo)值，則兩個點Pi、Pj之間的距離公式為：d(P,P)(P.xP.x)2(P.yP.y)2ijijij?對于給定的n個點，找出其中兩個距離最小的點的問題直觀的想法很簡單，只要把所有的點兩兩組合，比較它們之間的距離即可以得到距離最小的一對。21?算法BruceForceClosestPoints(P輸入：n?算法BruceForceClosestPoints(P輸入：n個點的數(shù)組P，Pi(xiyii=1,2,…,n輸出：兩個最近點的下標(biāo)index1和index2dmin←∞fori←1ton-1doforj←i+1tondod←sqrt((xi-xj)2+(yi-yj)2)ifd<dmindmin←dindex1←i;returnindex1,index2index2←j22???(xi-xj)2+(yi-y???(xi-xj)2+(yi-yj)2代替sqrt((xi-xj)2+(yi-yj)2)。基本操作：平方運算執(zhí)行次數(shù)：C(n)22(ni)n(n1)n1 nn2i1ji1C(n)∈Θ(n2)i0得進(jìn)一步的算法思路:（分治法）1)2)3)4)將平面上的n個點分成大致相等的2個子集S1和S2S1、另一點在S2中的最近點對從上述三對點中找距離最近的一對.233.3.2凸包問題?凸集定義：設(shè)S是平面點集，如果3.3.2凸包問題?凸集定義：設(shè)S是平面點集，如果S中任意兩點的連線都屬于該集合，則稱S是凸的。凸包定義：一個點集S的凸包是指包含S的最小凸集。顯然，如果S是凸的，則S的凸包就是S本身。凸包問題：給定一個n個點的平面點集S，求S的凸包。??24凸集是一個重要的數(shù)學(xué)概念，為簡單起見，這概念是很直觀的。例如下圖中的凸多邊形P1P3P4P6P8是點集{P1,P2,P凸集是一個重要的數(shù)學(xué)概念，為簡單起見，這概念是很直觀的。例如下圖中的凸多邊形P1P3P4P6P8是點集{P1,P2,P3,P4,P5,P6,P7,P8}的凸包?橡皮筋?P1P8P2P7P3P6P5P42017/10/1125?定理：任意包含n>2個點的集合S的凸包，是以S中的某些點為頂點的凸多邊形。特別，如果所有點共?定理：任意包含n>2個點的集合S的凸包，是以S中的某些點為頂點的凸多邊形。特別，如果所有點共在S中。為一條直線，它的兩個端點仍?極點：凸集的極點是指中間的點。出現(xiàn)在集合中任何線段的凸多邊形的頂點是極點。26?凸包問題的解法設(shè)點集大小為n，首先將其中的點兩兩配對，得到直線段條。然后對每一條直線段，?凸包問題的解法設(shè)點集大小為n，首先將其中的點兩兩配對，得到直線段條。然后對每一條直線段，檢查其余的n-2個點是否位于該直線段的同一邊。若是，則該直線段屬于凸多邊形的邊界，其頂點是極點。?設(shè)直線方程為ax+by=cax+by-c的正負(fù)性，如果具有相同的正負(fù)性，則位于同一邊。27 Y n(n-1)/2N28Uu,v構(gòu)成一條直線 Y n(n-1)/2N28Uu,v構(gòu)成一條直線3.4窮舉查找?窮舉法是一種簡單的蠻力方法，它要求生成所有可能的可行解，再從中找出最優(yōu)解。原理簡單，大多數(shù)情況下是不可行的。因為復(fù)雜度過大。3.4窮舉查找?窮舉法是一種簡單的蠻力方法，它要求生成所有可能的可行解，再從中找出最優(yōu)解。原理簡單，大多數(shù)情況下是不可行的。因為復(fù)雜度過大。?293.4.1 旅行商問題?TSP（Travelingsalesmanproblem）：給定n3.4.1 旅行商問題?TSP（Travelingsalesmanproblem）：給定n個城市相互之間的距離，求一條能走遍n個城市的最短路徑，使我們能從任一城市開始，到起點。??等價于“最短Hamilton回路”問題如果城市可以多次，問題如何變化？30n=4的旅行商問題的一個實例2ab路線a→b→c→d→aa→b→d→c→aa→c→b→d→aa→c→d→b→aa→d→b→c→aa→d→c→b→a長度2+3+7+5=172+4+7+8n=4的旅行商問題的一個實例2ab路線a→b→c→d→aa→b→d→c→aa→c→b→d→aa→c→d→b→aa→d→b→c→aa→d→c→b→a長度2+3+7+5=172+4+7+8=218+3+4+5=208+7+4+2=215+4+3+8=205+7+3+2=17534??????8cd76條3對313.4.2背包問題?問題：給定n3.4.2背包問題?問題：給定n個重量為w1、w2、…、wn，價值為v1、v2、…、vn的物品和一個承重為W的背包，要求選擇一些物品（子集）裝入背包，使背包內(nèi)物品的價值之和達(dá)到最大。32?舉例:物品類型1234?舉例:物品類型1234背包承重W=16重量25105價值$20$30$50$10所有可能的子集個數(shù)有2n個。窮舉法是Ω(2n)的。33??????????????????????????SubsetTotalweightTotalvalue{1}{2}{3}{4}{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}{1,2,3}{1,2,4}{1,3,4}{2,3,4}{1,2,3,4}251057127151015171217202234$20$30$50$10$50$70$30$80$40$60不可行$60不可行3.4.3分配問題?問題：有n個任務(wù)需要分配給3.4.3分配問題?問題：有n個任務(wù)需要分配給n個人執(zhí)行，一人一個任務(wù)。將第j個任務(wù)分配給第i個人的成本是C[i,j]，求總成本最小的分配方案。一種分配方案，對應(yīng)一個排列窮舉法要列出所有n!個可能的分配方案。較好的算法是匈牙利方法。???35分配問題的實例：以任務(wù)排列<2，3，4，1>表示：任務(wù)2分配給則有1分配問題的實例：以任務(wù)排列<2，3，4，1>表示：任務(wù)2分配給則有1、任務(wù)3分配給1分配給2、4C7469<1,2,3,4>,cost=9+4+1+4=18<1,2,4,3>,cost=9+4+8+9=30<1,3,2,4>,cost=9+3+8+4=24<1,3,4,2>,cost=9+3+8+6=26……363.5深度優(yōu)先和廣度優(yōu)先查找??用途：遍歷圖的頂點和邊3.5.1深度優(yōu)先查找（DFS：depth-firstsearch）可以從任意頂點開始圖的頂點，然后把該頂點標(biāo)記為已。在每次迭代時，緊接著處理與當(dāng)前頂點鄰接的未頂點。（順藤摸瓜，沿著一個分支越走越遠(yuǎn)）遇到死端時，沿著來路回退一條邊，嘗試?yán)^續(xù)從那里未的頂點。（回溯到上一個分岔口，選擇下一條分支）不存在未的頂點，算法結(jié)束。?3.5深度優(yōu)先和廣度優(yōu)先查找??用途：遍歷圖的頂點和邊3.5.1深度優(yōu)先查找（DFS：depth-firstsearch）可以從任意頂點開始圖的頂點，然后把該頂點標(biāo)記為已。在每次迭代時，緊接著處理與當(dāng)前頂點鄰接的未頂點。（順藤摸瓜，沿著一個分支越走越遠(yuǎn)）遇到死端時，沿著來路回退一條邊，嘗試?yán)^續(xù)從那里未的頂點。（回溯到上一個分岔口，選擇下一條分支）不存在未的頂點，算法結(jié)束。?可用棧來跟蹤深度優(yōu)先查找的操作：–頂點在第一次時，入棧–頂點成為死端時，出棧37DFS遍歷的例子38DFS遍歷的例子38有向圖DFS的例子39有向圖DFS的例子39DFS算法的偽代碼40DFS算法的偽代碼40?DFS的效率與圖的表示有關(guān)?對鄰接矩陣表示的圖：遍歷的效率為Θ(?DFS的效率與圖的表示有關(guān)?對鄰接矩陣表示的圖：遍歷的效率為Θ(V2)遍歷的效率為Θ(V+E)41DFS的應(yīng)用檢查圖的連通性DFS的應(yīng)用檢查圖的連通性找一個圖的連通分量檢查圖的無環(huán)性：有否回邊接的邊之后，圖被分為若干個不相交的部分。????423.5.2廣度優(yōu)先查找search）?過程：按照一種同心圓的方式，首先鄰接的頂點，然后是離它兩條邊的所有未所有和初始頂點頂點，以此類推，直到所有與初始頂點同在過了為止。如果仍然存在未被通分量中的頂點都的頂點，則從圖的的其他連通分量中的任意頂點重新開始?？捎藐犃衼砀檹V度優(yōu)先查找的過程?3.5.2廣度優(yōu)先查找search）?過程：按照一種同心圓的方式，首先鄰接的頂點，然后是離它兩條邊的所有未所有和初始頂點頂點，以此類推，直到所有與初始頂點同在過了為止。如果仍然存在未被通分量中的頂點都的頂點，則從圖的的其他連通分量中的任意頂點重新開始?？捎藐犃衼砀檹V度優(yōu)先查找的過程?–找出所有和隊頭頂點鄰接的未頂點，把它們標(biāo)記為己，再把它們?nèi)腙牗C將隊頭頂點從隊列中移去，出隊43BFS遍歷的例子44BFS遍歷的例子44BFS算法的偽代碼45BFS算法的偽代碼45BFS的應(yīng)用???檢查圖的連通性檢查圖的無環(huán)性BFS的應(yīng)用???檢查圖的連通性檢查圖的無環(huán)性求兩個頂點間的最少邊路徑4