第3章枚举算法 算法设计技术是求解问题的有效策略，也是算法解题的一般性方法，用于解决不同计算领域的多种问题。常用算法设计技术有枚举算法、递推算法、贪心算法、分治算法、动态规划算法、网络流算法、随机算法、近似算法、启发式算法。枚举算法从所有候选答案中搜索正确解，是一种暴力求解算法，也是最常想到和使用的算法。本章介绍蛮力算法和枚举算法，枚举算法的优化方法，排列和子集的生成方法。 视频讲解 3.1枚举与优化 3.1.1蛮力算法 蛮力算法是基于问题描述和定义，简单直接地解决问题的方法，又称暴力求解。这里的“力”指的是计算机的计算能力，而不是人的智力。蛮力算法是任何问题都有的简单算法，枚举算法、模拟算法和仿真算法是其常用的方法。例如，计算an(a>0，n为非负整数)的蛮力算法是直接做乘法n-1次，时间复杂度是O(n)，但本书第2章学过时间复杂度为O(logn)的快速幂算法。顺序查找是查找问题的蛮力算法，更好的算法是折半查找和分块查找。矩阵相乘的时间复杂度为O(n3)的算法是蛮力算法，本书后面会学到时间复杂度为O(nlog7)的算法。 例1： 给定n个元素的序列A，将A排序为{a1,a2,…,an}，使i i ) then Swap (A［i］,A［k］) //对换到第i个位置 6.return A 直接选择排序的比较次数为∑n-2i=0(n-i-1)=((1+n-1)/2)·(n-1)=(n(n-1))/2，交换次数最多为n-1次，因此时间复杂度为Θ(n2)。不管序列是正序还是反序，时间复杂度都为Θ(n2)。 冒泡排序算法BubbleSort： 输入： 数组A，n。 输出： 数组A，使i a［j］ ) then Swap ( a［j］,a［j-1］ )//交换 4.return a 冒泡排序的比较次数为∑n-1i=1(n-i)=((1+n-1)/2）·(n-1)=(n(n-1))/2，交换次数最多为∑n-1i=1(n-i)=((1+n-1)/2)·(n-1)=(n(n-1))/2，因此时间复杂度为Θ(n2)。但如果序列为正序，实际上不需要交换。据此进行改进，设置exchange变量，如果没有交换，则说明已经排好序，算法终止。 改进的冒泡排序算法： 输入： 数组A，n。 输出： 数组A，使i A［j］) then 7.Swap (A［j］,A［j-1］) //元素交换 8.exchange=1 9.i=i+1 10.return A 当序列为正序时，需进行1次循环，n-1次比较，不用交换，算法结束，因此时间复杂度为Ω(n)。当序列为反序时，算法的时间复杂度为O(n2)。 例2： 给定长度为n的字符串A，在其中查找是否有长度为m的字符串B。 字符串匹配算法： 输入： 字符串A和B。 输出： true or false。 1.for s =0 to n-m do 2.if (B［1:m］ == A［s+1:s+m］) //子串相等，B［1:m］=B 3.then return true 4.return false 算法循环n-m+1次，每次循环需要比较m次，因此蛮力算法的时间复杂度为(n-m+1)m=O(nm)。而字符串匹配的KMP(由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现，因此以其名字首字母命名)算法的时间复杂度为O(n+m)。 蛮力算法的优点是： 简单、应用广泛； 对于一些重要问题具有实用性，且不必限制实例规模； 对于规模较小的实例，比实现复杂算法的代价低； 一般用于解决小规模实例。其缺点是： 很少有高效的算法，不像其他算法设计得那么巧妙、有效。 3.1.2枚举算法概述 枚举(穷举)算法属于简单的蛮力方法，从问题所有可能的解集中一一枚举各元素，用题目中给定的约束条件判断是否符合条件，查找具有特殊属性(目标函数最优)的元素。满足约束条件的解称为问题的可行解，所有可行解构成问题的解空间，使目标函数最优的可行解称为问题的最优解。枚举算法一般涉及排列、组合或子集等对象。 枚举算法的一般步骤如下。 (1) 找出解的表示形式，构造问题的所有可能解(解空间)。 (2) 逐个评价解，选出满足约束条件的元素。 (3) 查找具有特殊属性的元素。 例3： 旅行商问题，给定n个城市相互间的距离，设置一条经过所有城市一次且仅有一次，然后回到起始城市的最短路径。 问题分析： 如图31所示，从城市a出发，经过b、c、d这3个城市再回到a的回路，如表31所示。n=4，枚举6条路径， 图31旅行商问题实例 得到最短路程为a→b→c→d→a 和a→d→c→b→a，路径长度为17。 实际上每条回路，除了起点和终点，刚好是b、c、d这3个城市的一个排列。因此，n个城市的解空间有(n-1)!条回路。算法首先找出(n-1)!条回路，然后计算每条回路的长度和，从这些长度和中选取具有最小长度和的路径。 表31旅行商问题求解示例 回路路程回路路程 a→b→c→d→a2+3+7+5=17a→c→d→b→a8+7+4+2=21 a→b→d→c→a2+4+7+8=21a→d→b→c→a5+4+3+8=20 a→c→b→d→a8+3+4+5=20a→d→c→b→a5+7+3+2=17 旅行商问题枚举算法： 输入： 图G的权值矩阵，n。 输出： 最短路径长度。 1.L=0 2.for 每条回路 do 3.计算回路的长度和p 4.if (pV) then V=v 5.return V 算法计算每个子集的总重量和总价值的时间复杂度为O(n)，共有2n个子集，因此算法的时间复杂度为O(n2n)。 3.1.3枚举优化 常用的枚举优化方法如下。 (1) 减少枚举变量。使用枚举算法前，首先考虑解元素之间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。 (2) 减少枚举变量的值域(取值范围)。 (3) 优化算法的模型和数据结构。 例5： 巧妙填数。将1~9这9个数字填入9个空格中，每一横行的3个数字组成一个三位数。如果要使第2行的三位数是第1行的2倍，第3行的三位数是第1行的3倍，应怎样填数？算法实例如表34所示。 表34巧妙填数实例 192 384 576 问题分析： 问题的解是每格1个数字，可以设置9个变量： A1~A9，第1个格有9个数字可选，|A1|=9； 第2格有8个数字可选，|A2|=8； …； 第9格只有1个数字可选，|A9|=1。共有9！=362880种方案，在这些方案中符合条件的即为问题的解。 考虑最后一行最大为987，显然第1行的三位数不会超过987/3，因此第1格只有{1,2,3}3个数字可选。实际上只要确定第1行的数就可以根据倍数条件计算出其他两行的数，然后检查是否9个数字都不重复，如果满足则得到问题的解。这样仅需设置3个枚举变量，|A1|=3、|A2|=8、|A2|=7，共有168个方案。算法通过减少枚举变量和枚举变量的值域，减少了计算量。 例6： 中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”。鸡翁一，值钱五； 鸡母一，值钱三； 鸡雏三，值钱一； 百钱买百鸡，翁、母、雏各几何? 问题分析： 设x，y，z分别为公鸡、母鸡、小鸡的数量，则x+y+z=100 且 5x+3y+z/3=100。x的取值范围为1~20； y的取值范围为1~34，z的取值范围为1~100，因此，最多共有20×34×100种方案。 实际上，公鸡x和母鸡y确定后，小鸡z=100-x-y，则共有20×34=680种方案。约束条件为： 5x+3y+z/3=100，z mod 3=0。这样，算法通过减少枚举变量，减少了计算量。 百钱百鸡问题枚举算法： 1.for x=1 to 20 do 2.for y=1 to 34 do 3.z=100-x-y 4.if (z mod 3==0 and 100==5*x+3*y+z/3) then 5.print x,y,z 例7： 输入正整数n，顺序输出形如abcde/fghij=n的表达式。a~j为0~9的一个排列。例如，79546/01283=62。 问题分析： 设置10个变量a~j，a~j为0~9的一个排列，所有排列数为 10！=3628800。 实际上，n是给定的，通过枚举分母 fghij，可以算出abcde，然后判断所有数字是否不同，这样减少了枚举变量，方案数减少为10×9×8×7×6。另外，还可以减少枚举变量取值范围，如果62×fghij>100000(超出5位数)，可以直接删除，减少计算。 例8: 分数拆分。输入正整数k，找所有正整数x≥y，使1/k=1/x+1/y。例如，1/2=1/6+1/3，1/2=1/4+1/4。 问题分析： 因为x≥y，所以1/k=1/x+1/y≤2/y，y≤2k。在2k范围内枚举y，通过1/k=1/x+1/y，可以计算x，这样减少了枚举变量x和y的取值范围。 例9： 约瑟夫问题。现在有2k个人围坐成一个圈，其中前k个人是好人，后k个人是坏人。从第1个人开始循环报数，报数为m的人被处决，之后的人接着从1开始报数。设计一个最小的m，使k轮处决之后留下的k个人都是好人。 问题分析： 第1种方法可以使用模拟法，根据问题的描述进行求解。使用now+m-1模拟每次报数为m被处决人的编号。now+m-1 mod bad 通过模运算，保证编号≤总人数。如果报数m的编号>k，则是坏人，算法继续运行； 否则是好人，算法终止，开始m+1的测试。最终bad=k，处决了k个坏人，得到问题的解。 约瑟夫问题模拟算法： 输入： k。 输出： m。 1.m=0 2.while (1) do 3.m ++//枚举m 4.bad=2*k //总人数 5.now=0 //起始编号 6.while(1) do 7.now=(now+m-1)% bad+1 //编号 8.if(now > k) then bad--now-- //坏人报数为m被处决，总人数减少 9.else break 10.if(bad == k) then 11.sign［k］=m 12.break 图32约瑟夫问题 第1个while循环m次，第2个while最多循环k次，且n=2k，因此算法的时间复杂度为O(nm)。问题还可以通过循环链表模拟实现。 第2种方法使用枚举算法。考虑最后处决的坏人，如果倒数第2个处决的坏人在其后面，则m=x(k+1) 报数为最后处决的坏人; 如果倒数第2个处决的坏人在其前面，则m=1+x(k+1)报数为最后处决的坏人。x表示转过x圈回到最后删除的坏人，如图32所示。这样操作优化了枚举变量的取值范围，枚举次数大大减少。 枚举算法虽然简单、容易编程、容易分析复杂度和证明正确性，但速度慢，仅对很小的实例有合理的运行时间，在许多规模较大的实例中有更好的替代算法。枚举算法要求所解问题的可能解是有限的、固定的，不会产生组合爆炸、容易枚举的。在某些实例中，枚举算法是唯一的解决方法。枚举算法多用于决策类问题，因为这类问题不易进行问题的分解，只能整体来求解。 本节思考题 计算an mod m，正整数a>1，正整数n>0。当n很大时，如何处理an的巨大的数量级问题？ 视频讲解 3.2组合与排列 枚举算法一般涉及排列、组合或子集等对象。本节主要讲述子集与排列的生成方法。 3.2.1排列 给定n个元素的数组P，生成P的全排列，可以按字典序、最小变化等要求输出全排列。 1. 按字典序输出全排列 字典序输出全排列算法： 输入： P，n。 输出： 按字典序输出P的所有排列。 call permutation (n,A,0,P) permutation (n,A,cur,P) { 1.if(cur==n) then//递归边界，输出排列 2.print A 3.else for i=0 to n-1 do 4. ok=1 //初值未使用过 5. for j=0 to cur-1 do //选择前面没有使用过的元素 6. if (A［j］==P［i］) then ok=0 //i在前面使用过，不能再使用 7. if(ok) then 8. A［cur］=P［i］ 9. permutation (n,A,cur+1,P) 10.} 按字典序输出全排列的示例如图33所示。首先cur=0，A［0］=P［0］=1，然后cur=1进入第1层。因为A［0］=P［0］=1，1已经被使用过，所以这里选择A［1］=P［1］=3，然后cur=2进入第2层。因为1和3已经被使用过，所以这里选择A［2］=P［2］=5，然后cur=3进入第3层。因为1、3和5已经被使用过，所以选择A［3］=P［3］=9，然后cur=4进入第4层。因为cur=n，所以输出排列1359。 回到第2层，选择A［2］=P［3］=9，然后cur=3进入第3层。因为1、3和9已经被使用过，所以选择A［3］=P［2］=5，然后cur=4进入第4层。因为cur=n，所以输出排列1395。 回到第1层，选择A［1］=P［2］=5，然后cur=2进入第2层。因为1和5已经被使用过，所以选择A［2］=P［1］=3，然后cur=3进入第3层。因为1、3和5已经被使用过，所以选择A［3］=P［3］=9，然后cur=4进入第4层。因为cur=n，输出排列1539。回到第2层，选择A［2］=P［3］=9，第3层选择A［3］=P［1］=3，第4层输出1593。同理输出1935和1953。 回到第0层，cur=0，选择A［0］=P［1］=3，进入第1层选择A［1］=P［0］=1，进入第2层选择A［2］=P［2］=5，进入第3层选择A［3］=P［3］=9，进入第4层输出3159…… 图33排列示例 计算排列的每位元素时，需要检查该元素是否已经被使用过，因此每个排列的检查量是1+2+…+n-1=O(n2)。n个元素的排列数为n!，因此算法的时间复杂度为O((n+2)！)。 2. 按照最小变化输出全排列 JohnsonTrotter算法引入可移动元素的概念，按照最小变化输出全排列。设排列p=p1 p2 p3 …pn，元素pk的箭头指向的相邻元素小于pk，则pk是可移动元素。 JohnsonTrotter算法： 输入： n。 输出： 按最小变化输出{1,2,…,n}的所有排列。 1.初始化排列 p=1 2 3…n 2.while 存在移动元素k do 3.求p中最大的可移动元素k 4.p=p中元素k和箭头指向的相邻元素互换 5.p=p中调转所有大于k的元素的方向 6.print p 当n=3时，从初始排列 p=1 2 3开始，查找到可移动元素2和3，选择最大可移动元素3和箭头指向的相邻元素2互换，得到1 3 2。同理，下一步得到3 1 2。然后选择可移动元素2和1互换，并将3反向，得到3 2 1 ……最后输出的全排列为{1 2 3，1 3 2，3 1 2，3 2 1，2 3 1，2 1 3}。 语句3、4和5的时间复杂度为O(n)，n个元素的排列数为n!，需要循环n！次，因此算法的时间复杂度为O((n+1)！)。 3. 库函数输出全排列 C++的STL中提供库函数next_permutation，可以使用下面代码实现全排列。 1.int a［n］; 2./*输入数组a*/ 3.sort(a,a+n); //必须先排序 4.do 5.{//在这里进行相应操作} 6.while(next_permutation(a,a+n)); 3.2.2子集 给定一个集合，枚举其所有子集，常用的方法有增量构造法、位向量法和二进制法。 1. 增量构造法 增量构造法一次选出一个元素放到集合中。A={1,5,9}，其子集构造过程如图34所示。增量构造前需要定序，使集合中元素编号从小到大排序，避免同一集合输出两次。例如，{1,2}和{2,1}。增量构造法伪代码如下。 图34增量构造法示例 输入： A，n。 输出： A的所有子集。 call subset (n,B,0) subset(n,B,cur) { 1.for i=0 to cur-1 do 2.printA［B［i］］ //打印当前集合 3.if (cur>0) then s=B［cur-1］+1 4.else s=0 5.for i=s to n-1 do //向下递归 6.B［cur］=i 7.subset(n,B,cur+1) 8.} n个元素的集合有2n个子集，每次调用的时间为O(n)，因此算法的时间复杂度为O(n2n)。 2. 位向量法 位向量法构造一个位向量b，而不是直接构造子集A本身。向量b有0和1两种选择，代表子集中是否选择该元素，当所有元素是否被选择确定后构成一个子集。位向量法伪代码如下。 输入： A，n。 输出： A的所有子集。 call subset(n,B,0)A={1,5,9} B={0，0, 0) subset(n,B,cur) { 1.if(cur==n) then 2.for i=0 to cur-1 do 3.if(B［i］) then print A［i］ //打印当前集合 4.else B［cur］=1//选第cur个元素 5. subset(n,B,cur+1) 6. B［cur］=0 //不选第cur个元素 7. subset(n,B,cur+1) 8.} 位向量法的判定树是一棵完全二叉树，在判定树中叶子节点为一个子集，中间节点不构成子集。生成节点数为O(2n+1)，输出每个子集的时间为O(n)，因此时间复杂度为O(n2n+1)。位向量法的任何节点都是一个子集，因此位向量法生成的节点多，效率低。 3. 二进制法 二进制法用二进制表示一个子集，从右向左，第i位表示元素i是否在集合中。例如，给定数组A={1,5,9}，二进制011表示选择低位的1和5，未选择高位的9，因此对应子集为{1，5}。 输入： A，n。 输出： A的所有子集。 1.for j=0 to (1<