第3章蛮力法.ppt

1、第3章 蛮力法 *,3.1 蛮力法的设计思想,3.2 查找问题中的蛮力法,3.3 排序问题中的蛮力法,3.4 组合问题中的蛮力法,3.5 图问题中的蛮力法,3.6 几何问题中的蛮力法,3.7 实验项目串匹配问题,3.1 蛮力法的设计思想,蛮力法的设计思想：直接基于问题的描述。* 例：计算an,蛮力法依赖的基本技术扫描技术 关键依次处理所有元素 基本的扫描技术遍历 （1）集合的遍历 （2）线性表的遍历 （3）树的遍历 （4）图的遍历,虽然巧妙和高效的算法很少来自于蛮力法，基于以下原因，蛮力法仍是一种重要的算法设计技术：,（1）理论上，蛮力法可以解决可计算领域的各种问题。 （2）蛮力法经常用来解决

2、一些较小规模的问题。 （3）对于一些重要的问题蛮力法可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。 （4）蛮力法可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。 *,3.2 查找问题中的蛮力法,3.2.1 顺序查找,3.2.2 串匹配问题,顺序查找从表的一端向另一端逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。,3.2.1 顺序查找,算法3.1的基本语句是i0和ri!=k，其执行次数为:,基本语句 ？,将待查值放在查找方向的尽头处，免去了在查找过程中每一次比较后都要

3、判断查找位置是否越界，从而提高了查找速度。,改进的顺序查找,算法3.2的基本语句是ri!=k，其执行次数为:,数量级相同， 系数相差一半,用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。,一般观点：,3.2.2 串匹配问题,串匹配问题属于易解问题。 串匹配问题的特征： （1）算法的一次执行时间不容忽视：问题规模 n 很大，常常需要在大量信息中进行匹配； （2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。,串匹配问题给定两个串S=“s1s2sn” 和T=“t1t2tm”，在主串S

4、中查找子串T的过程称为串匹配，也称模式匹配。,基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。,蛮力法解决串匹配问题BF算法,本趟匹配开始位置,设主串s=“ababcabcacbab”，模式t=“abcac,a b c,i=3，j=3失败； i回溯到2，j回溯到1,第1趟,a,第2趟,i=2

5、，j=1失败 i回溯到3，j回溯到1,第3趟,a b c a c,i=7，j=5失败 i回溯到4，j回溯到1,第4趟,a,i=4，j=1失败 i回溯到5，j回溯到1,第5趟,a,i=5，j=1失败 i回溯到6，j回溯到1,第6趟,i=11，j=6，t中全部字符都比较完毕，匹配成功。,int BF(char S , char T ) i=1; j=1; while (j=T0) if (Si=Tj) i+; j+; else i=i-j+2; j=1; if (jT0) return (i-j+1); else return 0; ,BF C+算法,设串S长度为n，串T长度为m，在匹配成功的情况

6、下，考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一个字符。,例如：S=aaaaaaaaaaab T=aaab 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)m次，第i趟成功的匹配共比较了m次，所以总共比较了im次，因此平均比较次数是：,改进的串匹配算法KMP算法,设计思想：尽量利用已经部分匹配的结果信息，尽量让 i 不回溯，加快模式串的滑动速度。,a b c,i=3，j=3失败；,第1趟,a,第2趟,s2=t2;t1t2 t1s2,第4趟,a,第3趟,a b c a c,i=7，j=5失败,s3=t2;t1t2 t1s4,第5趟,a,s5=t3;t1t3 t1s5,

7、第6趟,i=11，j=6，t中全部字符都比较完毕，匹配成功。,需要讨论两个问题： 如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ 模式应该向右滑多远才是最高效率的?,结论： i可以不回溯，模式向右滑动到的新比较起点k ，并且k 仅与模式串T有关！,请抓住部分匹配时的两个特征：,两式联立可得：T1Tk-1Tj-(k-1) Tj-1,S=a b a b c a b c a c b a b,T=a b c a c,（1）设模式滑动到第k个字符，则T1Tk-1 Si-(k-1) Si-1,（2）则Tj-(k-1) Tj-1 Si-(k-1) Si-1,T1Tk-1Tj-(k-1) Tj-1说明

8、了什么？ （1） k 与 j 具有函数关系，由当前失配位置 j ，可以计算出滑动位置 k（即比较的新起点）； （2）滑动位置k 仅与模式串T有关。,从第1位往右 经过k-1位,从j-1位往左 经过k-1位,kmax k |1kj 且T1Tk-1Tj-(k-1) Tj-1 ,T1Tk-1Tj-(k-1) Tj-1的物理意义是什么？,模式应该向右滑多远才是最高效率的?,next j ,0 当j1时 /不比较 max k | 1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况,令k = next j ，则：,nextj函数表征着模式T中最大相同首子串和尾子串（真子串）的长度。可见，模式

9、中相似部分越多，则nextj函数越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。,此时，比较tk和tj，可能出现两种情况： （1）tktj：说明t1 tk-1tktj-k+1 tj-1tj，由前缀函数定义，nextj+1=k1；,由模式T的前缀函数定义易知，next1=0，假设已经计算出next1，next2，nextj，如何计算nextj1呢？设k=nextj，这意味着t1 tk-1既是t1 tj-1的真后缀又是t1 tj-1的真前缀，即： t1 tk-1tj-k+1tj-k+2 tj-1,计算nextj的方法：,（2）tktj：此时要找出t1 tj-1的后缀中第2大

10、真前缀，显然，这个第2大的真前缀就是nextnextj=nextk。,再比较tnextk和tj，此时仍会出现两种情况，当tnextktj时，与情况（1）类似，nextj+1=nextk+1；当tnextktj时，与情况（2）类似，再找t1 tj-1的后缀中第3大真前缀，重复（2）的过程，直到找到t1 tj-1的后缀中的最大真前缀，或确定t1 tj-1的后缀中不存在真前缀，此时，nextj+1=1。,例如，模式T=a b a a b a b c的next值计算如下： j=1时，next1=0； j=2时，next2=1； j=3时，t1t2， k=next1=0，next3=1； j=4时，t1

11、t3，next4=next3+1=2； j=5时，t2t4，令k=next2=1，t1t4，next5=k+1=2； j=6时，t2t5，next6=3； j=7时，t3t6，next7=4； j=8时，t4t7，k=next4=2，t2t7，next8=k+1=3。,KMP算法用伪代码描述如下：,KMP算法的时间复杂性是O(n+m)，当mn时，KMP算法的时间复杂性是O(n)。,作业,习题3 3 4,3.3 排序问题中的蛮力法,3.3.1 选择排序,3.3.2 起泡排序,3.3.1 选择排序,选择排序第i趟排序从第i个记录开始扫描序列，在n-i+1(= n-(i-1)（1in-1）个记录中找

12、到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。(算法思想见P56),该算法的基本语句是内层循环体中的比较语句rjrindex，其执行次数为：,起泡排序在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就被“沉到”了序列的最后一个位置，第二遍扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1遍扫描后，整个序列就排好序了。 (算法思想见P57),3.3.2 起泡排序,该算法的基本语句是内层循环体中的比较语句rjrj+1，其执行次数为：,可以对起泡排序算法进行一定的改良。注意到，在一趟起泡排序过程中，如果有多个记录交换到最终位置，则下一趟起泡排序将不处理这

13、些记录；另外，在一趟起泡排序过程中，如果没有记录相交换，那么表明这个数组已经有序，算法将终止。,上述改进算法的时间性能分析如下：在最好情况下，待排序记录序列为正序，算法只执行一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂性为O(n)； 在最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大的记录被交换到最终位置，故算法执行n-1趟，第i（1in）趟排序执行了n-i次关键码的比较和n-i次记录的交换，这样，记录的移动次数为： 关键码的比较次数为 ，因此，时间复杂性为O(n2)；在平均情况下，其时间复杂性与最坏情况同数量级。,3.4 组合问题中的蛮力法,3.4.1 生成排

14、列对象,3.4.2 生成子集,3.4.3 0/1背包问题,3.4.4 任务分配问题,3.4.1 生成排列对象,假设已经生成了所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列中的n个位置中去，来得到问题规模为n的所有排列。按照这种方式生成的所有排列都是独一无二的，并且他们的总数应该是n(n-1)!=n!。,开始 1 插入2 12 21 插入3 123 132 312 213 231 321 生成排列的过程,显然，算法3.9的时间复杂性为O(n!)，也就是说和排列对象的数量成正比。,3.4.2 生成子集,n个元素的集合A=a1, a2, an的所有2n个子集和长度为n的所有2n个比特

15、串之间的一一对应关系。 建立对应关系：为每一个子集指定一个比特串b1b2bn，如果ai属于该子集，则bi1；如果ai不属于该子集，则bi0（1in）。,以下是3个元素的集合可构成的8个子集（注意与01串对照）： 比特串 000 001 010 011 100 101 110 111 子集 a3 a2 a2,a3 a1 a1,a3 a1, a2 a1,a2,a2,生成n个元素子集的算法如下：,显然，算法3.10的时间复杂性为O(2n)，也就是说和子集的数量成正比。,3.4.3 0/1背包问题,0/1背包问题是给定n个重量为w1, w2, ,wn、价值为v1, v2, ,vn的物品和一个容量为C的

16、背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。 用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。,对于一个具有n个元素的集合，其子集数量是2n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个(2n)的算法。,3.4.4 任务分配问题,假设有n个任务需要分配给n个人执行，每个任务只分配给一个人，每个人只分配一个任务，且第j个任务分配给第i个人的成本是Ci, j（1i , jn），任务分配问题要求找出总成本最小的分配方案。,下图是一个任务分配问题的成本矩阵

17、，矩阵元素Ci, j代表将任务j分配给人员i的成本。,任务分配问题就是在分配成本矩阵中的每一行选取一个元素，这些元素分别属于不同的列，并且元素之和最小。,可以用一个n元组(j1, j2, , jn)来描述任务分配问题的一个可能解，其中第i个分量ji（1in）表示在第i行中选择的列号，* 因此用蛮力法解决任务分配问题要求生成整数1n的全排列，然后把成本矩阵中的相应元素相加来求得每种分配方案的总成本，最后选出具有最小和的方案。,由于任务分配问题需要考虑的排列数量是n!，所以，其时间复杂度为O(n!)，除了该问题的一些规模非常小的实例外，蛮力法几乎是不实用的。,作业,习题3 6 11,3.5 图问题

18、中的蛮力法,3.5.1 哈密尔顿回路问题,3.5.2 TSP问题,3.5.1 哈密尔顿回路问题,著名的爱尔兰数学家哈密尔顿（William Hamilton，18051865）提出了著名的周游世界问题。他用正十二面体的20个顶点代表20个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。,使用蛮力法寻找哈密尔顿回路的基本思想是：对于给定的无向图G=(V, E)，首先生成图中所有顶点的排列对象(vi1, vi2, , vin)，然后依次考察每个排列对象是否满足以下两个条件： （1）相邻顶点之间存在边，即 (vij, vij+1)E（1jn-1） （2）最后一个顶点和第一个顶点之间

19、存在边，即 (vin, vi1)E 满足这两个条件的回路就是哈密尔顿回路。,(a) 一个无向图 (b) 哈密顿回路求解过程,显然，蛮力法求解哈密尔顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为O(n!)。*,3.5.2 TSP问题,TSP问题是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。,注意到，在图3.16中有3对不同的路径，对每对路径来说，不同的只是路径的方向，因此，可

20、以将这个数量减半，则可能的解有(n-1)!/2个 * 。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速地增长，例如：,一个10城市的TSP问题有大约有180,000个可能解。 一个20城市的TSP问题有大约有 60,000,000,000,000,000个可能解。 一个50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。 用蛮力法求解TSP问题，只能解决问题规模很小的实例。,3.6 几何问题中的蛮力法,3.6.1 最近对问题,3.6.2 凸包问题,3.6.1 最近对问题,最近对问题要求找出一个包含n个点的集合中距离最近的两个点。 简单起见，只考虑二维的情况

21、，并假设所讨论的点是以标准笛卡儿坐标形式（x, y）给出的。因此，在两个点Pi=(xi, yi)和Pj=(xj, yj)之间的距离是标准的欧几里德距离：,蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑ij的那些点对(Pi, Pj)。,int ClosestPoints(int n, int x , int y , int ,算法3.11的基本操作是计算两个点的欧几里德距离。注意到在求欧几里德距离时，避免了求平方根操作，其原因是：如果被开方的数越小，则它的平方根也越小。所以，算法3.11的基本操作就是求平方，其执行次数为

22、：,3.6.2 凸包问题,定义3.1 对于平面上的一个点的有限集合，如果以集合中任意两点P和Q为端点的线段上的点都属于该集合，则称该集合是凸集合。 显然，任意凸多边形都是凸集合。,定义3.2 一个点集S的凸包是包含S的最小凸集合，其中，最小是指S的凸包一定是所有包含S的凸集合的子集。,对于平面上n个点的集合S，它的凸包就是包含所有这些点（或者在内部，或者在边界上）的最小凸多边形。,凸包问题是为一个具有n个点的集合构造凸多边形的问题。为了解决凸包问题，需要找出凸多边形的顶点，这样的点称为极点。 一个凸集合的极点应该具有这样性质：对于任何以凸集合中的点为端点的线段来说，它不是这种线段中的点。,定理