1、2023-1-8成都学院计算机系1第4章 穷举法2023-1-8成都学院计算机系-2-2023-1-8成都学院计算机系-3-主要知识点掌握好算法的评价标准掌握好算法的评价标准;了解影响程序运行时间的因素了解影响程序运行时间的因素;掌握算法的评价标准掌握算法的评价标准:时间复杂度和空间复杂时间复杂度和空间复杂度的概念度的概念;掌握渐近时间复杂度的几种表示方式掌握渐近时间复杂度的几种表示方式;掌握常见时间复杂度渐近表示之间的关系掌握常见时间复杂度渐近表示之间的关系.2023-1-8成都学院计算机系44.1 穷举法思想2023-1-8成都学院计算机系-5-一、穷举法定义 是一种简单而直接地解决问题的
2、方法，常是一种简单而直接地解决问题的方法，常常直接基于问题的描述。常直接基于问题的描述。是是最容易最容易应用的方法，其时间性能比较应用的方法，其时间性能比较低低。通常典型的通常典型的指数时间指数时间算法一般都是通过穷算法一般都是通过穷举法搜索而得到的。举法搜索而得到的。2023-1-8成都学院计算机系-6-二、设计思想采用的基本技术是采用的基本技术是扫描技术扫描技术，即使用一定的策，即使用一定的策略将待求解问题的所有元素略将待求解问题的所有元素依次处理一次依次处理一次，从，从而找到问题的解。而找到问题的解。为了避免重复试探，在基本的数据结构中采用为了避免重复试探，在基本的数据结构中采用遍历遍历
3、来处理每一个元素。来处理每一个元素。2023-1-8成都学院计算机系-7-（1 1）集合的遍历）集合的遍历 按照元素序号的顺序依次处理每个元素。按照元素序号的顺序依次处理每个元素。（2 2）线性表的遍历）线性表的遍历 元素序号，如数组是按元素的下标来处理。元素序号，如数组是按元素的下标来处理。（3 3）树的遍历）树的遍历 先序、中序、后序先序、中序、后序2023-1-8成都学院计算机系-8-三、采用穷举法的原因理论上可以解决可计算领域的理论上可以解决可计算领域的各种问题各种问题。经常用来解决一些经常用来解决一些较小规模较小规模的问题。的问题。对一些重要问题（排序、查找、字符串匹配等）对一些重要
4、问题（排序、查找、字符串匹配等）有一些有一些实用价值实用价值，且不受问题规模的限制。，且不受问题规模的限制。可作为某类问题时间性能可作为某类问题时间性能下限下限，进行高效算法的，进行高效算法的比较。比较。2023-1-8成都学院计算机系-9-4.2 查找问题中的穷举法 顺序查找顺序查找 思想：从表的一端向另一端逐个将元素与给思想：从表的一端向另一端逐个将元素与给定值进行比较，若相等，查找成功，给出该元定值进行比较，若相等，查找成功，给出该元素的具体位置；若整个表检测完仍未找到与给素的具体位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败！定值相等的元素，则查找失败！2023-1-8成都
5、学院计算机系-10-假设以假设以n n个数放入数组个数放入数组r1r1rnrn中，查找值中，查找值k k的算法。的算法。int Seqsearch(int r,int n,int k)int Seqsearch(int r,int n,int k)i=n;i=n;while(i0&ri!=k)while(i0&ri!=k)i-;i-;return i;return i;2023-1-8成都学院计算机系-11-其基本语句其基本语句 i0i0和和ri!=kri!=k，其执行次数，其执行次数缺陷：每次都要判断缺陷：每次都要判断下标下标i i是否越界是否越界。nininiiiniiinOninninn
6、cpbp1111)(1)1(1)1(12023-1-8成都学院计算机系-12-改进方法：哨兵 将将k k放入到放入到r0r0中，每次将中，每次将r1r1rnrn中的值中的值与与r0r0进行比较。进行比较。int Seqsearch(int r,int n,int k)i=n;r0=k;while(ri!=k)i-;return i;2023-1-8成都学院计算机系-13-其基本语句其基本语句 i0i0和和ri!=kri!=k，其执行次数，其执行次数比较顺序查找方法，减少了系数。比较顺序查找方法，减少了系数。niniiinOninncp11)(21)1(12023-1-8成都学院计算机系-14-
7、4.3 排序问题中的穷举法一、选择排序一、选择排序 思想：开始扫描整个序列，找到最小记录和思想：开始扫描整个序列，找到最小记录和序列中的第一个记录交换，再从第二个记录扫序列中的第一个记录交换，再从第二个记录扫描，找到最小记录与第二个记录交换，直到扫描，找到最小记录与第二个记录交换，直到扫描第描第n-1n-1个记录与第个记录与第n n个记录进行交换，使得整个记录进行交换，使得整个序列有序。个序列有序。2023-1-8成都学院计算机系-15-一般情况，第一般情况，第i i趟排序从第趟排序从第i i个记录开始扫描序个记录开始扫描序列，在列，在n-i+1(1in)n-i+1(1in)个记录中找最小记录
8、，个记录中找最小记录，并与第并与第i i个记录进行交换。个记录进行交换。2023-1-8成都学院计算机系-16-Void Selectsort(int r,int n)Void Selectsort(int r,int n)for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)index=i;index=i;for(j=i+1;j=n;j+)/for(j=i+1;j=n;j+)/找最小记录找最小记录 if(rjrindex)index=j;if(rjrindex;rindex;2023-1-8成都学院计算机系-17-基本语句基本语句 内层循环中的内层循环中的rjrindexrjr
9、index，其，其执行次数为：执行次数为：选择排序选择排序最多交换最多交换n-1n-1次数据。次数据。112111)(2)1()(1nininijnOnnin2023-1-8成都学院计算机系-18-二、冒泡排序二、冒泡排序 一开始就扫描整个序列，在扫描的过程中一开始就扫描整个序列，在扫描的过程中两两两比较相邻记录两比较相邻记录，如反序则交换，最终将最大，如反序则交换，最终将最大记录置于最后一个记录位置，第二大记录置于记录置于最后一个记录位置，第二大记录置于倒数第二个记录位置，重复至整个序列有序。倒数第二个记录位置，重复至整个序列有序。2023-1-8成都学院计算机系-19-Void Bubbl
10、esort(int r,int n)Void Bubblesort(int r,int n)for(i=1;i=n-1;i+)for(i=1;i=n-1;i+)for(j=1;j=n-i;j+)/for(j=1;j=n-i;j+)/找最小记录找最小记录 if(rjrj+1)rj if(rjrj+1;rj+1;2023-1-8成都学院计算机系-20-基本语句基本语句 内层循环中的内层循环中的rjrj+1rjrj+1，其执行次，其执行次数为：数为：不足：如果整个序列已经有序，还是要直接整个不足：如果整个序列已经有序，还是要直接整个外循环执行完。外循环执行完。思想有没有改进的办法？有则写出算法。思想
11、有没有改进的办法？有则写出算法。112111)(2)1()(1niniinjnOnnin2023-1-8成都学院计算机系-21-4.5 几何问题中的穷举法最近对问题最近对问题 要求找出一个包含要求找出一个包含n n个点的集合中距离最个点的集合中距离最近的两个点。近的两个点。应用实例：空中交通应用实例：空中交通2023-1-8成都学院计算机系-22-前提假设前提假设 1.1.二维空间中的点，并且点的坐标形式二维空间中的点，并且点的坐标形式(x,y)(x,y)给出的。给出的。2.2.若若P Pi i=(x=(xi i,y,yi i),P),Pj j=(x=(xj j,y,yj j)，则其间距离，则
12、其间距离d:d:最近对问题的求解过程：分别计算每一对最近对问题的求解过程：分别计算每一对点之间的距离，然后找出距离最小的那一对，点之间的距离，然后找出距离最小的那一对，只考虑只考虑ijij的那些点对。的那些点对。22)()(jijiyyxxd2023-1-8成都学院计算机系-23-int closetpoint(int n,int x,int y,int&index1,int int closetpoint(int n,int x,int y,int&index1,int&index2)&index2)mindist=+;mindist=+;for(i=1;in;i+)for(i=1;in;i
13、+)for(j=i+1;j=n;j+)for(j=i+1;j=n;j+)d=(xi-xj)d=(xi-xj)*(xi-xj)+(yi-yj)(xi-xj)+(yi-yj)*(yi-(yi-yj);yj);if(dmindist)if(dmindist)mindist=d;mindist=d;index1=i;index1=i;index2=j;index2=j;return mindist;return mindist;2023-1-8成都学院计算机系-24-实验串匹配题目：给定一个文本，在该文本中查找并定位任题目：给定一个文本，在该文本中查找并定位任意给定字符串意给定字符串实验目的：实验目的
14、：理解并掌握穷举法的设计思想；理解并掌握穷举法的设计思想；实验要求：实验要求：1.1.实现实现BFBF算法及对其的改进算法算法及对其的改进算法BMBM算法算法 2.2.对对BFBF、BMBM进行时间复杂度的分析并编程验证。进行时间复杂度的分析并编程验证。2023-1-8成都学院计算机系-25-BM算法基本思想：假设将主串中自位置基本思想：假设将主串中自位置i i起往左的一起往左的一个子串与模式进行从右到左的匹配过程中，若个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的发现不匹配，则下次应从主串的i+dist(si+dist(si i)位位置开始重新进行新一轮的匹配，其效果相
15、当于置开始重新进行新一轮的匹配，其效果相当于把模式和主串均右滑过一段距离把模式和主串均右滑过一段距离dist(sdist(si i),),即即跳过跳过dist(sdist(si i)个字符而无需进行比较。个字符而无需进行比较。2023-1-8成都学院计算机系-26-假设字符表假设字符表a,b,c,za,b,c,z，BMBM算法对给定的算法对给定的模式模式T=“tT=“t1 1t t2 2ttm m”,”,定义一个从字符到正整数定义一个从字符到正整数的映射：的映射：dist:cdist:c1,2,1,2,，m,cm,c属于字符表属于字符表 滑动函数给出了正文中可能出现的任意字符在滑动函数给出了正
16、文中可能出现的任意字符在模式中的位置，定义如下：模式中的位置，定义如下：m-j j=maxj|tm-j j=maxj|tj j=c=c且且1jm-11jm-1 dist(c)=dist(c)=c c 若若c c不出现在模式中或不出现在模式中或t tm m=c=c2023-1-8成都学院计算机系-27-Int BM(char s,char t,int n,int m)Int BM(char s,char t,int n,int m)i=m;/i=m;/模式串长度模式串长度 while(i=n)while(i0&si=tj)while(j0&si=tj)j-;j-;i-;i-;if(j=0)return i+1;if(j=0)return i+1;else i=i+dist(si);else i=i+dist(si);return 0;return 0;
