蛮力算法

内蒙古农业大学算法设计与分析闫凤蛮力法内蒙古农业大学职业技术学院2蛮力法一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。第一，可以应用蛮力法来解决广阔领域的各种问题。第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法。第三，如果要解决的问题实例不多，而且蛮力法可以用一种能够接受速度对实例求解。第四，即使效率通常很低，仍然可以用蛮力法解决一些小规模的问题实例。蛮力法内蒙古农业大学职业技术学院3穷举法选择排序和冒泡排序顺序查找和蛮力字符串匹配蛮力法内蒙古农业大学职业技术学院蛮力法穷举查找对于组合问题来说，穷举查找是一种简单的蛮力方法。它要求生成问题域中的每一个元素，选出其中满足问题约束的元素，然后再找出一个期望元素（例如，使目标函数达到最值的元素）。1旅行商问题按照非专业的说法，这个问题要求找出一条n个给定的城市间的最短路径，使我们在回到出发的城市之前，对每个城市都只访问一次。内蒙古农业大学职业技术学院蛮力法abcd152378路线旅程abcdaI=2+8+1+7=18abdcaI=2+3+1+5=11最佳acbdaI=5+8+3+7=23acdbaI=5+1+3+2=11最佳adbcaI=7+3+8+5=23adcbaI=7+1+8+2=18用穷举查找对一个小规模旅行商问题的求解过程内蒙古农业大学职业技术学院蛮力法2背包问题这是计算机科学中另一个著名的问题。给定n个重量为wi,…,wn、价值为vi,…,vn的物品和一承重为W的背包，求这些物品中一个最有价值的子集。W=7V=$42W=3V=$12W=4V=$40W=5V=$25背包物品1物品2物品3物品410(a)内蒙古农业大学职业技术学院蛮力法子集总重量总价值ø0$0{1}7$42{2}3$12{3}4$40{4}5$25{1,2}10$36{1,3}11不可行{1,4}12不可行{2,3}7$52{2,4}8$37{3,4}9$65{1,2,3}14不可行{1,2,4}15不可行{1,3,4}16不可行{2,3,4}12不可行{1,2,3,4}19不可行内蒙古农业大学职业技术学院蛮力法3分配问题有n个任务需要分配给n个人执行，一个任务一个人。（意思是说，每个任务只分配给一个人，每个人只分配一个任务。）对于每一对i,j=1,…,n来说，将第j个任务分配给i个人的成本是C[i,j]。该问题要找出总成本最小的分配方案。任务1任务2任务3任务4人员19278人员26437人员35818人员47694内蒙古农业大学职业技术学院蛮力法4967818573468729C1,2,3,4cost=9+4+1+4=181,2,4,3cost=9+4+8+9=301,3,2,4cost=9+3+8+4=241,3,4,2cost=9+3+8+6=261,4,2,3cost=9+7+8+9=331,4,3,2cost=9+7+1+6=23用穷举法查找解决一个小规模分配问题的最初几次循环内蒙古农业大学职业技术学院104百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，读者可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围1~20之间；同理，y的取值范围在1~33之间，z的取值范围在1~100之间。约束条件：x+y+z=100且5*x+3*y+z/3=100蛮力法内蒙古农业大学职业技术学院11算法1如下：main(){intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)if(100=x+y+zand100=5*x+3*y+z/3){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberisz);}}算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低蛮力法内蒙古农业大学职业技术学院蛮力法算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了此时约束条件只有一个：5*x+3*y+z/3=100内蒙古农业大学职业技术学院蛮力法算法2如下：main(){intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1){z=100-x-y;if(zmod3=0and5*x+3*y+z/3=100){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberisz);}}}算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。内蒙古农业大学职业技术学院蛮力法5狱吏问题某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1间转动一次；问通过n次后，那些牢房的锁仍然是打开的？内蒙古农业大学职业技术学院蛮力法算法设计1：1）用n个空间的一维数组a[n],每个元素记录一个锁的状态，1为被锁上，0为被打开。2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开关锁可以转化为算术运算：a[i]=1-a[i]。3）第一次转动的是1，2，3，……，n号牢房；第二次转动的是2，4，6，……号牢房；第三次转动的是3，6，9，……号牢房；……第i次转动的是i，2i，3i，4i，……号牢房，是起点为i，公差为i的等差数列。4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关锁过程，最后当第i号牢房对应的数组元素a[i]为0时，该牢房的囚犯得到大赦。算法1如下：内蒙古农业大学职业技术学院蛮力法main1(){int*a,i,j,n;input(n);a=calloc(n+1,sizeof(int));for(i=1;i=n;i++)a[i]=1;for(i=1;i=n;i++)for(j=i;j=n;j=j+i)a[i]=1-a[i];for(i=1;i=n;i++)if(a[i]=0)print(i,”isfree.”);}算法分析：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+……+1/n)=O(nlogn)。内蒙古农业大学职业技术学院蛮力法问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:表4-3编号与因数个数的关系n12345678910111213141516……d(n)1223242434262445……数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1——i之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。内蒙古农业大学职业技术学院蛮力法算法设计2:1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。2）一个数的因子是没有规律的，只能从1——n枚举尝试。算法2如下：main2(){ints,i,j,n;input(n);for(i=1;i=n;i++){s=1;for(j=2;j=i;j=j++)if（imodj=0）s=s+1;if（smod2=1）print(i,”isfree.”);}}内蒙古农业大学职业技术学院蛮力法算法分析：狱吏开关锁的主要操作是a[i]=1-a[i];共执行了n*(1+1/2+1/3+……+1/n)次，时间近似为复杂度为O（nlogn）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断imodj是否为0，共执行了n*(1+2+3+……+n)次，时间复杂度为O（n2）。数学模型2：仔细观察表4-3，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且a≠b时，必有两个因子a，b;只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。算法3如下：内蒙古农业大学职业技术学院蛮力法main3(){ints,i,j,n;input(n);for(i=1;i=n;i++)if（i*i=n）print(i,”isfree.”);elsebreak;}由此算法我们应当注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。内蒙古农业大学职业技术学院蛮力法算法SelectionSort(A[0..n-1])//该算法用选择排序对给定的数组排序//输入：一个可排序数组A[0..n-1]//输出：非降序排序的数组A[0..n-1]fori←0ton-2domin←Iforj←i+1ton-1doifA[j][min]min←jswapA[i]andA[min]A0≤A1≤…Ai-1|Ai,…,Amin,…,An-1已经位于最终的位置上了最后的n-1个元素1选择排序选择排序和冒泡排序内蒙古农业大学职业技术学院蛮力法|8945689029341717|4568902934891729|6890453489172934|9045688917293445|9068891729344568|9089172934456889|90内蒙古农业大学职业技术学院蛮力法2冒泡排序A0,…,Aj↔Aj+1,…,An-i-1|An-i≤…≤An-1?已经位于最终的位置上了算法BubbleSort(A[0..n-1])//该算法用冒泡排序对数组A[0..n-1]排序//输入：一个可排序数组A[0..n-1]//输出：非降序排列的数组A[0..n-1]fori←0ton-2doforj←0ton-2-idoifA[j+1]A[j]swapA[j]andA[j+1]内蒙古农业大学职业技术学院蛮力法89456890293417458968902934174568899029341745688929903417456889293490174568892934179045688929341790456829893417904568293489179045682934178990内蒙古农业大学职业技术学院蛮力法1顺序查找该算法只是简单地将给定列表中的连续元素和给定的查找键作比较，直到遇到一个匹配的元素（查找成功），或者在遇到元素前就遍历了整个列表（失败查找）算法SequentialSearch2(A[0..n],K)//顺序查找的算法实现，它用了查找键来做限位器//输入：一个n个元素的数组A和一个查找键K//输出：第一个值等于K的元素的位置，如果找不到这样的元素，返回-1顺序查找和蛮力字符串匹配内蒙古农业大学职业技术学院蛮力法A[n]