算法设计与分析基础ch3蛮力法

广东工业大学计算机学院第3章2020/2/24LingJie/GDUT1第3章蛮力法•主要内容：3.1选择排序和冒泡排序3.2顺序查找和蛮力字符串匹配3.3最近对和凸包问题的蛮力算法3.4穷举查找广东工业大学计算机学院第3章2020/2/24LingJie/GDUT23.1选择排序和冒泡排序•蛮力算法是一种简单直接地解决问题的方法.一般高效和巧妙的算法很少来自蛮力法,但蛮力法具有如下优点:(1)应用范围广,(2)不受实例规模的限制,(3)当要解决的问题实例不多,设计更高效算法的代价太大时可选用,(4)对解决一些小规模的问题实例仍然有效,(5)可作为衡量其他算法的参照物.广东工业大学计算机学院第3章2020/2/24LingJie/GDUT33.1.1选择排序和冒泡排序•问题:给定一个可排序的n元序列,将它们按照非降序方式重新排列.•已开发出数十种排序算法.广东工业大学计算机学院第3章2020/2/24LingJie/GDUT41、选择排序•原理：扫描整个列表，找出最小元素，然后将最小元素与第一个元素交换位置。从第二个元素开始扫描列表，找出n-1个元素中的最小元素，将最小元素与第二个元素交换位置，如此类推，做n-1遍后排序结束。•算法伪代码：SelectionSort(A[0..n-1])fori=0ton-2domin=iforj=i+1ton-1doifA[j]A[min]min=jswapA[i]andA[min]广东工业大学计算机学院第3章2020/2/24LingJie/GDUT5例题：对序列{89,45,68,90,29,34,17}用选择排序算法进行排序•第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，90，89}{17，29，34，45，68，89，90}//排序结束广东工业大学计算机学院第3章2020/2/24LingJie/GDUT6•选择排序的算法分析：•基本操作：比较A[j]A[min]•比较次数C(n)：•于是C(n)∈Θ(n2)2020112)1()1(1)(nininijnninnC广东工业大学计算机学院第3章2020/2/24LingJie/GDUT72、冒泡排序•原理：比较相邻的元素，将大的元素交换到右边的位置，重复多次后，最大元素就“沉淀”到列表的最后一个位置。第二遍将第二大元素沉下去，n-1遍后结束。•算法伪代码：BubbleSort(A[0..n-1])fori=0ton-2doforj=0ton-2-idoifA[j+1]A[j]swapA[j]andA[j+1]广东工业大学计算机学院第3章2020/2/24LingJie/GDUT8例题：对序列{89,45,68,90,29,34,17}用冒泡排序算法进行排序•第1遍：{8945，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}{45，68，29，8934，17，90}{45，68，29，34，8917，90}{45，68，29，34，17，89，90}//比较n-2=5次广东工业大学计算机学院第3章2020/2/24LingJie/GDUT9•冒泡排序的算法分析：•基本操作：比较A[j]A[j+1]•比较次数C(n)：•于是C(n)∈Θ(n2)•问：冒泡排序最坏的情形是什么？2020202)1()1(1)(niniinjnninnC广东工业大学计算机学院第3章2020/2/24LingJie/GDUT10•ALGORITHMBubbleSort(A[0,…,n–1])•//冒泡排序算法在数组上的应用•//输入：数组A，数组中的元素属于某偏序集•//输出：按升序排列的数组A•fori←0ton–2do•forj←0ton–2–ido•ifA[j+1]A[j]swap(A[j],A[j+1])•改进的冒泡算法如下：•ALGORITHMBubbleSortImproved(A[0,…,n–1])•//冒泡排序算法的改进•//输入：数组A，数组中的元素属于某偏序集•//输出：按升序排列的数组A•fori←0ton–2do•flag←True•forj←0ton–2–ido•ifA[j+1]A[j]•swap(A[j],A[j+1])•flag←False•//如果在某一轮的比较中没有交换，则flag为True，算法结束•ifflag=Truereturn广东工业大学计算机学院第3章2020/2/24LingJie/GDUT113.2顺序查找和蛮力字符串匹配•1、顺序查找问题：已知有n个元素的数组A[0...n].给定元素K,要求找出一个下标i,使得A[i]=K.输出第一个值等于K的元素的位置，找不到返回-1.广东工业大学计算机学院第3章2020/2/24LingJie/GDUT12•算法SequentialSearch(A[0..n-1],K)i:=0;whileA[i]≠Kandindoi:=i+1;ifA[i]=Kthenreturnielsereturn-1改进算法SequentialSearch2(A[0..n-1],K)A[n]=K;i:=0;whileA[i]≠Kdoi:=i+1;ifinthenreturnielsereturn-1广东工业大学计算机学院第3章2020/2/24LingJie/GDUT13•2、蛮力字符串匹配问题：从文本中寻找匹配模式的子串，即求出第一个匹配模式的子串在文本中的开始位置（子串最左元素的下标）。其中：文本——给定的由n个字符组成的串模式——指定的由m个字符组成的串•蛮力算法：将模式对准文本的前m个字符从左往右进行比对，如果其中有一个字符不匹配，模式往有移动一位继续下一个m个字符的比对。广东工业大学计算机学院第3章2020/2/24LingJie/GDUT14目标text：模式pattern：t0t1t2tm-1tmtm+1tn-1…p0p1p2pm-1……目标text：模式pattern：t0t1t2tm-1tmtm+1tn-1…p0p1p2pm-1……目标text：模式pattern：t0t1titi+1ti+m-1tn-1…p0p1pm-1………||||||广东工业大学计算机学院第3章2020/2/24LingJie/GDUT15•算法BruteForceStringMatch(T[0..n-1],P[0..m-1]fori=0ton-mdoj=0whilejmandP[j]=T[i+j]doj=j+1ifi=mreturnireturn-1//文本T[0..n-1]长度为n//模式P[0..m-1]长度为m//查找不成功时返回-1广东工业大学计算机学院第3章2020/2/24LingJie/GDUT16•字符串匹配的例题•文本NOBODY_NOTICED_HIM•模式NOT•算法执行过程NOBODY_NOTICED_HIMNOTi=0,j=3——不匹配发生在第0+3位NOTi=1——不匹配发生在第1+1位NOTi=2——不匹配发生在第2+1位NOT——不匹配发生在第3+1位NOT——不匹配发生在第4+1位NOT——不匹配发生在第5+1位NOT——不匹配发生在第6+1位NOT——匹配开始在第7+1位广东工业大学计算机学院第3章2020/2/24LingJie/GDUT17•蛮力字符串匹配算法分析：最坏的情形是模式须移动n-m+1次，每次移动模式之前，做足m次比对才发现不匹配（即第i+m位不匹配），因此，在最坏情况下，该算法属于Θ(nm)。平均效率可达到Θ(n+m)=Θ(n)。广东工业大学计算机学院第3章2020/2/24LingJie/GDUT183.3最近对和凸包问题的蛮力算法问题描述：给定平面S上n个点，找其中的一对点，使得在n(n-1)/2个点对中，该点对的距离最小。在实际应用中，常利用点或者圆等简单的几何对象代表现实世界中的实体。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机,就是空间中最接近的一对点。广东工业大学计算机学院第3章2020/2/24LingJie/GDUT19•记（P.x，P.y）为点P的坐标值，则两个点Pi、Pj之间的距离公式为：•对于给定的n个点，找出其中两个距离最小的点的问题直观的想法很简单，只要把所有的点两两组合，比较它们之间的距离即可以得到距离最小的一对。22(,)(..)(..)ijijijdPPPxPxPyPy广东工业大学计算机学院第3章2020/2/24LingJie/GDUT20•算法BruceForceClosestPoints(P)//输入：n个点的数组P，Pi(xi,yi),i=1,2,…,n//输出：两个最近点的下标index1和index2dmin←∞fori←1ton-1doforj←i+1tondod←sqrt((xi-xj)2+(yi-yj)2)ifddmindmin←dindex1←i;index2←jreturnindex1,index2广东工业大学计算机学院第3章2020/2/24LingJie/GDUT21•注：可用(xi-xj)2+(yi-yj)2代替sqrt((xi-xj)2+(yi-yj)2)。•基本操作：平方运算•执行次数：得C(n)∈Θ(n2)20111)1()(22)(nininijnninnC进一步的算法思路:1)将平面上的n个点分成大致相等的2个子集S1和S22)分别求S1和S2中的最接近点对3)求一点在S1、另一点在S2中的最近点对4)从上述三对点中找距离最近的一对.广东工业大学计算机学院第3章2020/2/24LingJie/GDUT22•凸集定义：设S是平面点集，如果S中任意两点的连线都属于该集合，则称S是凸的。•凸包定义：一个点集S的凸包是指包含S的最小凸集。显然，如果S是凸的，则S的凸包就是S本身。•凸包问题：给定一个n个点的点集S，求S的凸包。2、凸包问题广东工业大学计算机学院第3章2020/2/24LingJie/GDUT23•凸集这是一个重要的数学概念，为简单起见，这里仅给出它在几何上的定义，这个意义下凸集的概念是很直观的。例如下图中的凸多边形P1P3P4P6P8是点集{P1,P2,P3,P4,P5,P6,P7,P8}的凸包。P1P3P4P6P8P2P5P7广东工业大学计算机学院第3章2020/2/24LingJie/GDUT24•定理：任意包含n2个点的集合S的凸包，是以S中的某些点位顶点的凸多边形。特别，如果所有点共线，则多边形退化为一条直线，它的两个端点仍在S中。•极点：凸集的极点是指不会出现在集合中任何线段的中间的点。凸多边形的顶点是极点。广东工业大学计算机学院第3章2020/2/24LingJie/GDUT25•凸集定义：设S是平面点集，如果S中任意两点的连线都属于该集合，