算法设计的与分析第3章蛮力法.pptVIP

蛮 力 法 1 2 3 4 概述 查找问题中的蛮力法 排序问题中的蛮力法 组合问题中的蛮力法 5 图问题中的蛮力法 几何问题中的蛮力法 6 1 蛮力法的设计思想 蛮力法是指采用遍历（扫描）技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解。 依次处理所有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。 蛮力法（枚举法、穷举法，暴力法）要求设计者找出所有可能的情况，然后选择其中一种情况，若该情况不可行（或不是最优解）则试探下一种可能的情况。 蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所设计的概念定义。 “力”——指计算机的能力，而不是人的智力。 蛮力法常常是最容易应用的方法。 求an（n为非负整数） 用连续整数检测算法计算GCD(m, n) 关于蛮力法思考 蛮力法不是一个最好的算法（巧妙和高效的算法很少出自蛮力）,但当我们想不出更好的办法时,它也是一种有效的解决问题的方法。 它可能是惟一一种几乎什么问题都能解决的一般性方法，常用于一些非常基本、但又十分重要的算法。 关于蛮力法思考 蛮力法的优点 逻辑清晰，编写程序简洁 对于一些重要的问题（比如：排序、查找、矩阵乘法和字符串匹配），可以产生一些合理的算法 解决问题的实例很少时，可以花费较少的代价 可以解决一些小规模的问题（使用优化的算法没有必要，而且某些优化算法本身较复杂） 可以作为其他高效算法的衡量标准 使用蛮力法的几种情况 有哪些信誉好的足球投注网站所有的解空间 有哪些信誉好的足球投注网站所有的路径 直接计算 模拟和仿真 一个简单的例子——百元买百鸡问题 根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。 用蛮力法解决问题，通常可以从两个方面进行算法设计： 1）找出枚举范围：分析问题所涉及的各种情况。 2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。 蛮力法解题步骤 思考下面问题：找出枚举范围和约束条件 思路： 枚举范围：100—999，共900个。 约束条件：设三位数的百位、十位、个位的数字分别为x，y，z。则有x2+y2+z2≤10,进而1≤x≤3, 0≤y≤3, 0≤z≤3。 求所有的三位数,它除以11所得的余数等于它的三个数字的平方和. 解：所求三位数必在以下数中： 　　100，101，102，103，110，111，112， 　　120，121，122，130，200，201，202， 　　211，212，220，221，300，301，310。 　　不难验证只有100，101两个数符合要求。 2 查找问题中的蛮力法—顺序查找 思路：顺序查找从表的一端向另一端逐个将元素与给定值进行比较，若相等，则查找成功，给出该元素在表中的位置；若整个表检测完仍未找到与给定值相等的元素，则查找失败，给出失败信息。 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 查找方向 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 查找方向 哨兵 K 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 查找方向 2 查找问题中的蛮力法—顺序查找 int SeqSearch1(int r[ ], int n, int k) { i=n; while (i0 r[i]!=k) i--; return i; } int SeqSearch2(int r[ ], int n, int k) { r[0]=k; i=n; while (r[i]!=k) i--; return i; } 2 查找问题中的蛮力法—顺序查找 2 查找问题中的蛮力法—串的匹配 BF算法 KMP算法 本趟开始位置 S 模式T tj j 回溯 si …… 回溯 i …