第3章 蛮力法 (1)

1、算法设计与分析算法设计与分析 1 第第3章章 蛮力法蛮力法 3.1 蛮力法的设计思想蛮力法的设计思想 3.2 查找问题中的蛮力法查找问题中的蛮力法 3.3 排序问题中的蛮力法排序问题中的蛮力法 3.4 组合问题中的蛮力法组合问题中的蛮力法 3.5 图问题中的蛮力法图问题中的蛮力法 3.6 几何问题中的蛮力法几何问题中的蛮力法 算法设计与分析算法设计与分析 2 3.1 蛮力法的设计思想蛮力法的设计思想 蛮力法蛮力法(穷举法穷举法）：是一种简单而直接地解决问题）：是一种简单而直接地解决问题 的方法，常常直接基于问题的描述。的方法，常常直接基于问题的描述。 例：计算例：计算an n次 an=aaa

2、算法设计与分析算法设计与分析 3 n 蛮力法所赖的蛮力法所赖的基本技术基本技术扫描技术扫描技术 n 关键关键依次处理所有元素依次处理所有元素 n 基本的扫描技术基本的扫描技术遍历遍历 （1）集合的遍历：在集合中按照元素序号顺序依次处理）集合的遍历：在集合中按照元素序号顺序依次处理 每个元素。每个元素。 （2）线性表的遍历：在线性表中按照元素序号顺序依次）线性表的遍历：在线性表中按照元素序号顺序依次 处理每个元素。处理每个元素。 （3）树的遍历）树的遍历 ：前序、后序和层序：前序、后序和层序3种，二叉树有前序、种，二叉树有前序、 中序、后序和层序中序、后序和层序4种。种。 （4）图的遍历）图的遍

3、历 ：有深度优先遍历：有深度优先遍历 和广度优先遍历和广度优先遍历 。 算法设计与分析算法设计与分析 4 遍历的结果：遍历的结果：产生一个关于结点的线性序列。产生一个关于结点的线性序列。 设设访问根结点访问根结点记作记作 D 遍历根的左子树遍历根的左子树记作记作 L 遍历根的右子树遍历根的右子树记作记作 R 则可能的遍历次序有则可能的遍历次序有 先序先序 DLR DRL 逆先序逆先序 中序中序 LDR RDL 逆中序逆中序 后序后序 LRD RLD 逆后序逆后序 所谓遍历二叉树，就是遵从某种次序，访所谓遍历二叉树，就是遵从某种次序，访 问二叉树中的问二叉树中的所有结点所有结点，使得每个结点，使

4、得每个结点仅被仅被 访问一次访问一次。 遍历二叉树遍历二叉树 算法设计与分析算法设计与分析 5 先左后右的遍历算法先左后右的遍历算法 先先（根）序的遍历算法（根）序的遍历算法 中（根）序的遍历算法中（根）序的遍历算法 后后（根）序的遍历算法（根）序的遍历算法 根根 左 子树 右 子树 根根根根根根根根根根 算法设计与分析算法设计与分析 6 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）访问根结点；）访问根结点； （2）先序遍历左子树；）先序遍历左子树； （3）先序遍历右子树。）先序遍历右子树。 先（根）序的遍历算法：先（根）序的遍历算法： 算法设计与分析算法设计与分析

5、 7 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）中序遍历左子树；）中序遍历左子树； （2）访问根结点；）访问根结点； （3）中序遍历右子树。）中序遍历右子树。 中（根）序的遍历算法：中（根）序的遍历算法： 算法设计与分析算法设计与分析 8 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则， （1）后序遍历左子树；）后序遍历左子树； （2）后序遍历右子树；）后序遍历右子树； （3）访问根结点。）访问根结点。 后（根）序的遍历算法：后（根）序的遍历算法： 算法设计与分析算法设计与分析 9 A B C D E F G HK 例如：例如： 先序序列：先序序列

6、： 中序序列：中序序列： 后序序列：后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 算法设计与分析算法设计与分析 10 虽然巧妙和高效的算法很少来自于蛮力法，基于虽然巧妙和高效的算法很少来自于蛮力法，基于 以下原因，蛮力法也是一种重要的算法设计技术：以下原因，蛮力法也是一种重要的算法设计技术： （1）理论上，蛮力法可以解决可计算领域的各种问）理论上，蛮力法可以解决可计算领域的各种问 题。题。 （2）蛮力法经常用来解决一些较小规模的问题。）蛮力法经常用来解决一些较小规模的问题。 （3）对于一些重要的问题蛮力法可以产生一些合理

7、）对于一些重要的问题蛮力法可以产生一些合理 的算法，他们具备一些实用价值，而且不受问题规模的算法，他们具备一些实用价值，而且不受问题规模 的限制。的限制。 （4）蛮力法可以作为某类问题时间性能的底限，来）蛮力法可以作为某类问题时间性能的底限，来 衡量同样问题的更高效算法。衡量同样问题的更高效算法。 算法设计与分析算法设计与分析 11 3.2 查找问题中的蛮力法查找问题中的蛮力法 3.2.1 顺序查找顺序查找 3.2.2 串匹配问题串匹配问题 算法设计与分析算法设计与分析 12 顺序查找从表的一端向另一端顺序查找从表的一端向另一端逐个逐个将元素与给定值将元素与给定值 进行比较，若相等，则查找成功

8、，给出该元素在表中的进行比较，若相等，则查找成功，给出该元素在表中的 位置；若整个表检测完仍未找到与给定值相等的元素，位置；若整个表检测完仍未找到与给定值相等的元素， 则查找失败，给出失败信息。则查找失败，给出失败信息。 3.2.1 顺序查找顺序查找 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 查找方向查找方向 算法设计与分析算法设计与分析 13 算法算法3.1顺序查找顺序查找 int SeqSearch1( (int r , int n, int k) ) /数组数组r1 rn存放查找存放查找 集合集合 i=n; while ( (i0 r

9、eturn i; 算法算法3.1的的基本语句基本语句是是i0和和ri!=k，其执行次数为，其执行次数为: Pi为查找成功的概率，为查找成功的概率，ci和和bi为比较次数。为比较次数。 n i n i n i n i iiii nOnin n in n cpbp 1111 )(1) 1( 1 ) 1( 1 基本语句基本语句 ？ 算法设计与分析算法设计与分析 14 将将待查值待查值放在查找方向的放在查找方向的尽头尽头处，免去了在查找过处，免去了在查找过 程中每一次比较后都要判断查找位置是否程中每一次比较后都要判断查找位置是否越界越界，从，从 而提高了查找速度。而提高了查找速度。 k 10 15 2

10、4 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 查找方向查找方向 哨兵哨兵 改进的顺序查找改进的顺序查找 算法设计与分析算法设计与分析 15 算法算法3.2改进的顺序查找改进的顺序查找 int SeqSearch2(int r , int n, int k) /数组数组r1 rn存放查找集合存放查找集合 r0=k; i=n; while (ri!=k) i -; return i; 算法算法3.2的的基本语句基本语句是是ri!=k，其执行次数为，其执行次数为: n i n i ii nO n in n cp 11 )( 2 1 ) 1( 1 数量级相同，数量级

11、相同， 系数相差一半系数相差一半 算法设计与分析算法设计与分析 16 用蛮力法设计的算法，一般来说，经过适度的用蛮力法设计的算法，一般来说，经过适度的 努力后，都可以对算法的第一个版本进行一定程度努力后，都可以对算法的第一个版本进行一定程度 的改良，改进其时间性能，但的改良，改进其时间性能，但只能减少系数，而数只能减少系数，而数 量级不会改变。量级不会改变。 v 一般观点：一般观点： 算法设计与分析算法设计与分析 17 3.2.2 串匹配问题串匹配问题 串匹配问题属于易解问题。串匹配问题属于易解问题。 串匹配问题的特征：串匹配问题的特征： （1）算法的一次执行时间不容忽视：问题规模）算法的一次

12、执行时间不容忽视：问题规模 n 很大，常常需要在大量信息中进行匹配；很大，常常需要在大量信息中进行匹配； （2）算法改进所取得的积累效益不容忽视：串匹配）算法改进所取得的积累效益不容忽视：串匹配 操作经常被调用，执行频率高。操作经常被调用，执行频率高。 串匹配问题串匹配问题给定两个串给定两个串S=“s1s2sn” 和和 T=“t1t2tm”，在主串，在主串S中查找子串中查找子串T的过程称为的过程称为串匹配串匹配， 也称也称模式匹配模式匹配。 算法设计与分析算法设计与分析 18 基本思想：从主串基本思想：从主串S的第一个字符开始和模式的第一个字符开始和模式T的第的第 一个字符进行比较，若相等，则

13、继续比较两者的后续字一个字符进行比较，若相等，则继续比较两者的后续字 符；若不相等，则从主串符；若不相等，则从主串S的第二个字符开始和模式的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，若的第一个字符进行比较，重复上述过程，若T中的字符中的字符 全部比较完毕，则说明本趟匹配成功；若最后一轮匹配全部比较完毕，则说明本趟匹配成功；若最后一轮匹配 的起始位置是的起始位置是n-m？，则主串则主串S中剩下的字符不足够匹中剩下的字符不足够匹 配整个模式配整个模式T，匹配失败。这个算法称为，匹配失败。这个算法称为朴素的模式匹朴素的模式匹 配算法配算法，简称，简称BF算法算法。 蛮力法解决串匹配

14、问题蛮力法解决串匹配问题BF算法算法 算法设计与分析算法设计与分析 19 本趟匹配开始位置本趟匹配开始位置 si 主串主串S 模式模式T tj j 回溯回溯 回溯回溯 i 算法设计与分析算法设计与分析 20 设主串设主串s=“ababcabcacbab”，模式，模式t=“abcac a b a b c a b c a c b a b a b c i=3，j=3失败；失败； i回溯到回溯到2，j回溯到回溯到1 第第1趟趟 i j i j i j i j 算法设计与分析算法设计与分析 21 a b a b c a b c a c b a b a i j i j 第第2趟趟 i=2，j=1失败失败

15、i回溯到回溯到3，j回溯到回溯到1 第第3趟趟 a b a b c a b c a c b a b a b c a c i=7，j=5失败失败 i回溯到回溯到4，j回溯到回溯到1 i j i j i j i j i jj i 算法设计与分析算法设计与分析 22 第第4趟趟 a b a b c a b c a c b a b a i j i=4，j=1失败失败 i回溯到回溯到5，j回溯到回溯到1 j i 第第5趟趟 a b a b c a b c a c b a b i j a j i i=5，j=1失败失败 i回溯到回溯到6，j回溯到回溯到1 算法设计与分析算法设计与分析 23 第第6趟趟 a

16、 b a b c a b c a c b a b a b c a c i=11，j=6，t中全部中全部 字符都比较完毕，匹字符都比较完毕，匹 配成功。配成功。 i j i j i j i j i j i j 算法设计与分析算法设计与分析 24 设设S=s1,s2,sn(主串主串)T=t1,t2,tm(模式串模式串) i为指向为指向S中字符的指针，中字符的指针，j为指向为指向T中字中字 符的指针符的指针 匹配失败：匹配失败：sitj时，时， (si-j+1 si-1)=(t1 tj-1) 回溯：回溯： i=i-j+2 ; j=1 算法设计与分析算法设计与分析 25 int BF( (char S

17、 , char T ) ) i=1; j=1; while ( (i=S0 / else return 0; BF C+算法 算法 算法设计与分析算法设计与分析 26 设串设串S长度为长度为n，串，串T长度为长度为m，在匹配成功的情况下，在匹配成功的情况下， 考虑最坏情况，即每趟不成功的匹配都发生在串考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一的最后一 个字符。个字符。 例如：例如：S=aaaaaaaaaaab T=aaab 设匹配成功发生在设匹配成功发生在si处，则在处，则在i- -1趟不成功的匹配中共趟不成功的匹配中共 比较了比较了( (i- -1) )m次，第次，第i趟成功的匹配

18、共比较了趟成功的匹配共比较了m次，所次，所 以总共比较了以总共比较了im次，因此平均比较次数是：次，因此平均比较次数是： 1 1 1 1 2 ) 2( )( 1 1 )( mn i mn i i mnm mi mn mip 一般情况下，一般情况下，mn，因此最坏情况下的时间复杂性是，因此最坏情况下的时间复杂性是O( (n*m) )。 BP算法简单但效率低，主要原因是重复回溯太多。算法简单但效率低，主要原因是重复回溯太多。 算法设计与分析算法设计与分析 27 改进的串匹配算法改进的串匹配算法KMP算法算法 由由D.E.Knuth, J.H.Morris D.E.Knuth, J.H.Morris

19、 ，V.R.PrattV.R.Pratt同时设同时设 计计KMPKMP算法。算法。 设计思想设计思想：尽量利用已经尽量利用已经部分匹配部分匹配的结果信的结果信 息，尽量让息，尽量让 i i 不回溯，加快模式串的滑动速度。不回溯，加快模式串的滑动速度。 算法设计与分析算法设计与分析 28 a b a b c a b c a c b a b a b c i=3，j=3失败；失败； 第第1趟趟 iii j a b a b c a b c a c b a b a i j 第第2趟趟 s2=t2;t1t2 t1s2 jj 算法设计与分析算法设计与分析 29 3.3 3.3 排序问题中的蛮力法排序问题中的

20、蛮力法 3.3.1 选择排序选择排序 3.3.2 起泡排序起泡排序 算法设计与分析算法设计与分析 30 3.3.1 选择排序选择排序 选择排序第选择排序第i趟排序从第趟排序从第i个记录开始扫描序列，在个记录开始扫描序列，在n-i+1 （1in-1）个记录中找到关键码最小的记录，并和第）个记录中找到关键码最小的记录，并和第i个记个记 录交换作为有序序列的第录交换作为有序序列的第i个记录。个记录。(第i趟选择排序是指通过 n-i次关键字的比较) r1 r2 ri- -1 ri ri+1 rmin rn 有序区有序区 无序区无序区 已经位于最终位置已经位于最终位置 rmin为无序区的最小记录为无序区

21、的最小记录 例如：进行第例如：进行第i趟选择时，从当前候选记录中趟选择时，从当前候选记录中 选出关键字最小的选出关键字最小的k号记录，并与第号记录，并与第i个记录进个记录进 行交换。行交换。 交换交换 算法设计与分析算法设计与分析 31 图 选择排序示例 4862357755143598 ik 1462357755483598 ik 1435627755483598 ik 1435357755486298 ik 算法设计与分析算法设计与分析 32 算法算法3.6选择排序选择排序 void SelectSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 for

22、( (i=1; i=n- -1; i+) ) /对对n个记录进行个记录进行n- -1趟简单选择排序趟简单选择排序 index=i; for ( (j=i+1; j=n; j+) ) /在无序区中找最小记录在无序区中找最小记录 if ( (rjrindex) ) index=j; if ( (index!=i) ) ririndex; /若最小记录不在最终位置若最小记录不在最终位置 则交换则交换 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句 rjrindex，其执行次数为：，其执行次数为： 1 1 2 1 11 )( 2 ) 1( )(1 n i n i n

23、ij nO nn in 算法设计与分析算法设计与分析 33 起泡排序在扫描过程中两两比较相邻记录，如果反序则交起泡排序在扫描过程中两两比较相邻记录，如果反序则交 换，最终，最大记录就被换，最终，最大记录就被“沉到沉到”了序列的最后一个位置，了序列的最后一个位置， 第二遍扫描将第二大记录第二遍扫描将第二大记录“沉到沉到”了倒数第二个位置，重了倒数第二个位置，重 复上述操作，直到复上述操作，直到n-1 遍扫描后，整个序列就排好序了。遍扫描后，整个序列就排好序了。 3.3.2 起泡排序起泡排序 rj rj+1 ri+1 rn- -1 rn 无序区无序区 有序区有序区 1ji- -1 位于最终位置位于

24、最终位置 反序则交换反序则交换 算法设计与分析算法设计与分析 34 【例例】已知序列（已知序列（17，18，60，40，7，32，73，65，85），请给出采），请给出采 用冒泡排序法对该序列作升序排序时的每一趟的结果。用冒泡排序法对该序列作升序排序时的每一趟的结果。 解：解： 初始初始 1趟趟 2趟趟 3趟趟 4趟趟 5趟趟 17 17 17 17 7 7 18 18 18 7 17 17 60 40 7 18 18 18 40 7 32 32 32 32 7 32 40 40 40 40 32 60 60 60 60 60 73 65 65 65 65 65 65 73 73 73 73

25、73 85 85 85 85 85 85 （ 红色字表示有序区）红色字表示有序区） 算法设计与分析算法设计与分析 35 算法算法3.7起泡排序起泡排序 void BubbleSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 for (i=1; i=n- -1; i+) /共共n-1趟趟 for (j=1; jrj+1) rjrj+1；/如果反序，则交换元素如果反序，则交换元素 该算法的基本语句是内层循环体中的比较语句该算法的基本语句是内层循环体中的比较语句 rjrj+1，其执行次数为：，其执行次数为： 1 1 2 1 11 )( 2 ) 1( )(1 n i

26、 n i in j nO nn in 算法设计与分析算法设计与分析 36 注意到，在一趟起泡排序过程中，如果有多个记录交换到注意到，在一趟起泡排序过程中，如果有多个记录交换到 最终位置，则下一趟起泡排序将不处理这些记录；另外，最终位置，则下一趟起泡排序将不处理这些记录；另外， 在一趟起泡排序过程中，如果没有记录相交换，那么表明在一趟起泡排序过程中，如果没有记录相交换，那么表明 这个数组已经有序，算法将终止。这个数组已经有序，算法将终止。 算法算法3.8改进的起泡排序改进的起泡排序 void BubbleSort( (int r , int n) ) /数组下标从数组下标从1 1开始开始 exc

27、hange=n; /第一趟起泡排序的范围是第一趟起泡排序的范围是r1到到rn while ( (exchange) ) /仅当上一趟排序有记录交换才进行本趟仅当上一趟排序有记录交换才进行本趟 排序排序 bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1； exchange=j； /记录每一次发生记录交换的位置记录每一次发生记录交换的位置 算法设计与分析算法设计与分析 37 冒泡排序算法如下：冒泡排序算法如下： void BubbleSort(RecordType r, int length ) /*对记录数组对记录数组r做冒泡排序，做

28、冒泡排序， length为数组的长度为数组的长度*/ n=length; change=TRUE； for ( i=1 ; i= n-1 +i ) change=FALSE； for ( j=1 ; j rj+1.key ) x= rj; rj= rj+1; rj+1= z; change=TRUE； /* BubbleSort */ 算法设计与分析算法设计与分析 38 在最好情况下，在最好情况下，待排序记录序列为正序，算法只执行一趟，待排序记录序列为正序，算法只执行一趟， 进行了进行了n- -1次关键码的比较，不需要移动记录，时间复杂性为次关键码的比较，不需要移动记录，时间复杂性为 O( (

29、n) )； 在最坏情况下，在最坏情况下，待排序记录序列为反序，每趟排序在无序序待排序记录序列为反序，每趟排序在无序序 列中只有一个最大的记录被交换到最终位置，故算法执行列中只有一个最大的记录被交换到最终位置，故算法执行n- -1 趟，第趟，第i（1in）趟排序执行了）趟排序执行了n- -i次关键码的比较和次关键码的比较和n- -i次记次记 录的交换，这样，关键码的比较次数为录的交换，这样，关键码的比较次数为 ，记录，记录 的移动次数为的移动次数为 ，因此，时间复杂性为，因此，时间复杂性为O( (n2) )； 注意：注意：最坏情况下，待排序记录按关键字的逆序进行排列，最坏情况下，待排序记录按关键

30、字的逆序进行排列， 此时，每一趟冒泡排序需进行此时，每一趟冒泡排序需进行k 次比较，则有次比较，则有3k次移动。次移动。 在平均情况下在平均情况下，其时间复杂性与最坏情况同数量级。，其时间复杂性与最坏情况同数量级。 2 )1( 1 1 nn in n i ）（ 2 )1(3 3 1 1 nn in n i ）（ 算法设计与分析算法设计与分析 39 3.4 3.4 组合问题中的蛮力法组合问题中的蛮力法 3.4.1 生成排列对象生成排列对象 3.4.2 生成子集生成子集 3.4.3 0/1背包问题背包问题 3.4.4 任务分配问题任务分配问题 算法设计与分析算法设计与分析 40 3.4.1 生成排

31、列对象生成排列对象 假设已经生成了所有假设已经生成了所有(n-1)!个排列，可以把个排列，可以把n插入到插入到n-1个个 元素的每一种排列中的元素的每一种排列中的n个位置中去，来得到问题规模为个位置中去，来得到问题规模为n 的所有排列。按照这种方式生成的所有排列都是独一无二的所有排列。按照这种方式生成的所有排列都是独一无二 的，并且他们的总数应该是的，并且他们的总数应该是n(n-1)!=n!。 开始开始 1 插入插入2 12 21 插入插入3 123 132 312 213 231 321 生成排列的过程生成排列的过程 算法设计与分析算法设计与分析 41 算法算法3.9生成排列对象生成排列对象

32、 1生成初始排列生成初始排列1； 2for (i=2; i=n; i+) /i为插入元素为插入元素 for (j=1; j=1; k-) /插入位置插入位置 将将i插入到第插入到第j个排列中的第个排列中的第k个位置；个位置； 显然，算法显然，算法3.9的时间复杂性为的时间复杂性为O(n!)，也就是说和排，也就是说和排 列对象的数量成正比。列对象的数量成正比。 算法设计与分析算法设计与分析 42 3.4.2 生成子集生成子集 n个元素的集合个元素的集合A=a1, a2, an的所有的所有2n个子集和长度个子集和长度 为为n的所有的所有2n个个比特串比特串之间的一一对应关系。之间的一一对应关系。

33、建立对应关系：为每一个子集指定一个比特串建立对应关系：为每一个子集指定一个比特串b1b2bn， 如果如果ai属于该子集，则属于该子集，则bi1；如果；如果ai不属于该子集，则不属于该子集，则bi0 （1in）。）。 比特串比特串 000 001 010 011 100 101 110 111 子集子集 a3 a2 a2,a3 a1 a1,a3 a1, a2 a1,a2,a2 算法设计与分析算法设计与分析 43 生成生成n个元素子集的算法如下：个元素子集的算法如下： 算法算法3.10生成子集生成子集 1初始化一个长度为初始化一个长度为n的比特串的比特串s=000并将对应的子并将对应的子 集输出；

34、集输出； 2for (i=1; i2n; i+) 2.1 s+； 2.2 将将s对应的子集输出；对应的子集输出； 显然，算法显然，算法3.10的时间复杂性为的时间复杂性为O(2n)，也就是说和子，也就是说和子 集的数量成正比。集的数量成正比。 算法设计与分析算法设计与分析 44 3.4.3 0/1背包问题背包问题 0/1背包问题是给定背包问题是给定n个重量为个重量为w1, w2, ,wn、 价值为价值为v1, v2, ,vn的物品和一个容量为的物品和一个容量为C的背包，的背包， 求这些物品中的一个最有价值的子集，并且要能够求这些物品中的一个最有价值的子集，并且要能够 装到背包中。装到背包中。

35、用蛮力法用蛮力法解决解决0/1背包问题，需要考虑给定背包问题，需要考虑给定n个个 物品集合的所有子集，找出所有可能的子集（总重物品集合的所有子集，找出所有可能的子集（总重 量不超过背包容量的子集），计算每个子集的总价量不超过背包容量的子集），计算每个子集的总价 值，然后在他们中找到价值最大的子集。值，然后在他们中找到价值最大的子集。 算法设计与分析算法设计与分析 45 10 w1=7 v1=42 w2=3 v2=12 w3=4 v3=40 w4=5 v4=25 背包背包 物品物品1 物品物品2 物品物品3 物品物品4 81,412161,2,3,419 序号序号子集子集总重量总重量总价值总价值

36、序号序号子集子集总重量总重量总价值总价值 100 92,3752 21742102,4837 32312113,4965 43440121,2,314不可行不可行 54525131,2,415 61,21054141,3,416 71,311不可行不可行152,3,412 不可行不可行 不可行不可行 不可行不可行 不可行不可行 不可行不可行 算法设计与分析算法设计与分析 46 对于一个具有对于一个具有n个元素的集合，其子集个元素的集合，其子集 数量是数量是2n，所以，不论生成子集的算法，所以，不论生成子集的算法 效率有多高，蛮力法都会导致一个效率有多高，蛮力法都会导致一个(2n) 的算法。的算

37、法。(描述增长率的下限）描述增长率的下限） 算法设计与分析算法设计与分析 47 3.4.4 任务分配问题任务分配问题 假设有假设有n个任务需要分配给个任务需要分配给n个人执行，个人执行， 每个任务只分配给一个人，每个人只分配一每个任务只分配给一个人，每个人只分配一 个任务，且第个任务，且第j个任务分配给第个任务分配给第i个人的成本个人的成本 是是Ci, j（1i , jn），任务分配问题要求），任务分配问题要求 找出总成本最小的分配方案。找出总成本最小的分配方案。 算法设计与分析算法设计与分析 48 下图是一个任务分配问题的成本矩阵，矩阵元下图是一个任务分配问题的成本矩阵，矩阵元 素素Ci,

38、j代表将任务代表将任务j分配给人员分配给人员i的成本。的成本。 C= 9 2 7 6 4 3 5 8 1 任务任务1 任务任务2 任务任务3 人员人员1 人员人员2 人员人员3 任务分配问题就是在分配成本矩阵中的每一行任务分配问题就是在分配成本矩阵中的每一行 选取一个元素，这些元素分别属于不同的列，并且选取一个元素，这些元素分别属于不同的列，并且 元素之和最小。元素之和最小。 算法设计与分析算法设计与分析 49 可以用一个可以用一个n元组元组(j1, j2, , jn)来描述任务分配问题的一个可能来描述任务分配问题的一个可能 解，其中第解，其中第i个分量个分量ji（1in）表示在）表示在第第i

39、行行中选择的列号，中选择的列号， 因此用蛮力法解决任务分配问题因此用蛮力法解决任务分配问题要求生成整数要求生成整数1n的全排列的全排列， 然后把成本矩阵中的相应元素相加来求得每种分配方案的总然后把成本矩阵中的相应元素相加来求得每种分配方案的总 成本，最后选出具有最小和的方案。成本，最后选出具有最小和的方案。 序号序号分配方案分配方案 总成本总成本 11, 2, 39+4+1=14 21, 3, 29+3+8=20 32, 1, 32+6+1=9 42, 3, 12+3+5=10 53, 1, 27+6+8=21 63, 2, 17+4+5=16 算法设计与分析算法设计与分析 50 由于任务分配

40、问题需要考虑的排列数由于任务分配问题需要考虑的排列数 量是量是n!，所以，除了该问题的一些规模非，所以，除了该问题的一些规模非 常小的实例，蛮力法几乎是不实用的。常小的实例，蛮力法几乎是不实用的。 算法设计与分析算法设计与分析 51 3.5 图问题中的蛮力法图问题中的蛮力法 3.5.1 哈密顿回路问题哈密顿回路问题 3.5.2 TSP问题问题 算法设计与分析算法设计与分析 52 3.5.1 哈密顿回路问题哈密顿回路问题 著名的爱尔兰数学家著名的爱尔兰数学家哈密顿哈密顿（William Hamilton， 18051865）提出了著名的周游世界问题。他用正十二）提出了著名的周游世界问题。他用正十

41、二 面体的面体的20个顶点代表个顶点代表20个城市，要求从一个城市出发，个城市，要求从一个城市出发， 经过每个城市恰好一次，然后回到出发城市。经过每个城市恰好一次，然后回到出发城市。 19 8 3 14 1 202 13 15 4 5 67 9 10 11 12 16 17 18 正十二面体的展开图，正十二面体的展开图， 按照图中的顶点编号所按照图中的顶点编号所 构成的回路，就是哈密构成的回路，就是哈密 顿回路的一个解。顿回路的一个解。 算法设计与分析算法设计与分析 53 使用蛮力法寻找哈密顿回路的基本思想是：对使用蛮力法寻找哈密顿回路的基本思想是：对 于给定的无向图于给定的无向图G=(V,

42、E)，首先生成图中所有顶点，首先生成图中所有顶点 的排列对象的排列对象(vi1, vi2, , vin)，然后依次考察每个排列，然后依次考察每个排列 对象是否满足以下对象是否满足以下两个条件：两个条件： （1）相邻顶点之间存在边，即）相邻顶点之间存在边，即 (vij, vij+1)E（1jn-1） （2）最后一个顶点和第一个顶点之间存在边，即）最后一个顶点和第一个顶点之间存在边，即 (vin, vi1)E 满足这两个条件的回路就是哈密顿回路。满足这两个条件的回路就是哈密顿回路。 算法设计与分析算法设计与分析 54 1 2 4 5 3 路径路径(vij, vij+1)E 1234512345（是

43、）（是） 12354123 54 （否）（否） 1243512 43 5 （否）（否） 否否 否否 1245312 45 3 （否）（否） 12534125 34 （否）（否） 1254312543（是）（是） (vin, vi1)E 是是 是是 是是 是是 (a) 一个无向图一个无向图 (b) 哈密顿回路求解过程哈密顿回路求解过程 显然，蛮力法求解哈密顿回路在最坏情况下需要考察显然，蛮力法求解哈密顿回路在最坏情况下需要考察 所有顶点的排列对象，其所有顶点的排列对象，其时间复杂性为时间复杂性为O(n!)。 算法设计与分析算法设计与分析 55 3.5.2 TSP问题问题 TSP(旅行商）旅行商）

44、问题是问题是指旅行家要旅行指旅行家要旅行n个城市然后回个城市然后回 到出发城市，要求各个城市经历且仅经历一次，并要求到出发城市，要求各个城市经历且仅经历一次，并要求 所走的路程最短。该问题又称为所走的路程最短。该问题又称为货郎担问题货郎担问题、邮递员问邮递员问 题、售货员问题，题、售货员问题，是图问题中最广为人知的问题。是图问题中最广为人知的问题。 用蛮力法解决用蛮力法解决TSP问题，可以找出所有可能的旅行问题，可以找出所有可能的旅行 路线，从中选取路径长度最短的简单回路。路线，从中选取路径长度最短的简单回路。 算法设计与分析算法设计与分析 56 8 ab d c 2 35 7 1 序号序号路

45、径路径路径长度路径长度是否最短是否最短 1abcda 18 否否 2abdca 11 是是 3acbda 23 否否 4acdba 11 是是 5adbca 23 否否 6adcba 18 否否 注意到，在图注意到，在图3.16中有中有3对不同对不同的路径，对每对路径来的路径，对每对路径来 说，不同的只是路径的方向，因此，可以将这个数量减半，说，不同的只是路径的方向，因此，可以将这个数量减半， 则可能的解有则可能的解有( (n- -1) )!/ /2个。这是一个非常大的数，随着个。这是一个非常大的数，随着n的的 增长，增长，TSP问题的可能解也在迅速地增长，例如：问题的可能解也在迅速地增长，例如： 算法设计与分析算法设计与分析 57 l 一个一个10城市的城市的TSP问题有大约有问题有大约有180,000个可能解。个可能解。 l 一个一个20城市的城市的TSP问题有大约有问题有大约有 60,000,000,000,000,000个可能解。个可能解。 l 一个一个50城市的城市的TSP问题有大约问题有大约1062个可能解，而一个个可能解，而一个 行星上也只有行星上也只有1021升水。升水。 v 用蛮力法求解用蛮力法求解TSP问题，只能解决问题规模很小的问题，只能解决问题规模很小的 实例。实例。 算法设计与分析算法设计与分析 58 3.6 几何问题中的蛮力法几何问题中的