电子教案7-2常见算法

大学计算机,第7章：算法与数据结构基础,常见算法,7.2,7.2.1穷举法,穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。穷举法常用于解决“是否存在”或“有多少种可能”等问题。穷举算法特点是算法简单，但运行时所花费的时间量大。例如：有一把锁和一串钥匙（共有10把钥匙），怎样找出所有开这把锁的钥匙？在QQ上，OicqPassOver这个工具穷举用户的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。,7.2.1穷举法,1、百钱百鸡问题中国古代算书张丘建的算经中有一道著名的百鸡问题：公鸡每只值5文钱，母鸡每只值3文钱，而3只小鸡值1文钱。现在用100文钱买100只鸡，问：这100只鸡中，公鸡、母鸡和小鸡各有多少只？解法如下：设公鸡、母鸡、小鸡分别为x、y、z只，由题意得：用穷举法求解，对每组求得满足等式方程组的值，从而找到百钱百鸡的解。,7.2.1穷举法,2、逻辑推断有四位学生中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。现在并不知道是谁做得好事，但知道做好事的人是A,B,C,D四个人中的某一个。因此，可以一个一个地试探。这也是通过穷举法来解决问题。,7.2.1穷举法,3、韩信点兵秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布:“我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。”汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。“韩信点兵”它形成了一类问题，这个问题计算机解决起来也是用的穷举法，用从1开始逐个自然数的试着寻找满足上述题意要求的值，直到找到这个数x为止。,7.2.1穷举法,用穷举算法解决问题，通常可以从两个方面进行分析：1、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。2、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案，把这些条件描述出来。穷举法穷举的数据量过大，效率较低，对于小规模的问题还是适用的但是问题规模一旦扩大，穷举法就没有什么可取性了。一般巧妙和高效算法很少来自穷举法。,7.2.2回溯法,迷宫游戏,7.2.2回溯法,回溯算法也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的指导思想：走不通，就掉头回溯法在搜索过程中通过对约束条件的判定，排除错误答案，提高了搜索效率。,7.2.2回溯法,1、八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。,7.2.2回溯法,回溯法解八皇后问题思路：逐行摆放皇后。初始第1行皇后放第1列；摆放第i行皇后时，从第1列开始，逐列判定是否与前i-1行皇后攻击，直到找到一个不攻击的位置，继续第i+1行的摆放；若第i行无摆放位置，则拿掉该行皇后，回溯至第i-1行，第i-1行皇后从当前位置的下一列开始判定，继续搜索。当第1行皇后的摆放位置超出棋盘时，全部求解过程结束，可找到92种摆法。,7.2.2回溯法,网络爬虫是一个功能强大的自动提取网页的程序，它为搜索引擎从万维网下载网页，是搜索引擎的重要组成部分。它可以完全不依赖用户干预实现网络上的自动“爬行”和搜索。网络爬虫是通过网页的链接地址来寻找网页在抓取网页的时候，网络爬虫采用了深度优先策略。深度优先是指网络爬虫会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络爬虫在设计的时候比较容易。这是一种典型的回溯算法。,7.2.2回溯法,回溯法的本质也是一种穷举法，但与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。,7.2.3递归法,人们都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说。所谓递归就是一个函数或过程可以直接或间接地调用自己。,7.2.3递归法,递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。,7.2.3递归法,1.n！问题阶乘可以这样递归地定义成函数：这样，所有自然数的阶乘就可以通过上面的两句话表示了。2的阶乘就是12；3的阶乘就是2的阶乘乘3，即123不仅如此，人们还可以知道0的阶乘是多少，1的阶乘应该等于0的阶乘乘以1，显然0的阶乘必须是1才行。,7.2.3递归法,1.n！问题每个递归函数必须至少有一个基线条件一般情况必须最终能简化为基线条件,7.2.3递归法,2、汉诺塔（Hanoi）问题相传印度有座大寺庙，它曾被认为是宇宙的中心。神庙中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，由上至下放了64片直径由小至大的圆环形金属片。古印度教的天神指示他的僧侣们将64片金属片全部移至另一根木钉上。移动规则只有两个：（1）在每次的移动中，只能移动一片金属片；（2）过程中任意时刻必须保证金属片小的在上，大的在下。,7.2.3递归法,使用递归时必须符合以下三个条件：（1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。（2）可以通过转化过程使问题回到对原问题的求解。（3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。递归对某些问题而言存在重复调用，导致算法效率不高。,7.2.4分治法,分治法的设计思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,7.2.4分治法,1、找出伪币一个装有16枚硬币的袋子，16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。,7.2.4分治法,1、找出伪币方法1：任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。,7.2.4分治法,1、找出伪币方法2：将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。,7.2.4分治法,1、找出伪币方法3：,7.2.4分治法,上述三种方法,分别需要比较18次,8次,4次,那么形成比较次数差异的根据原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。,7.2.4分治法,根据以上比较，第三种方法就是分治法，可以得到以下的采用分治方法的结论：1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；2、解决方法关键在于能将大问题分割成若干小问题；3、小问题与原有问题是完全类似的。,7.2.4分治法,2、二分法二分查找又称为折半查找，是一种可在有序顺序表上实现的效率比较高的查找算法。是一个典型的分治算法。,7.2.4分治法,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,7.2.5贪心法,贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。只顾眼前利益，每次都选最好的,7.2.5贪心法,1、商场找零假设只有3种面额的币值，它们的面值分别为20元、10元、5元、和1元。现要找给某顾客37元，这时，售货员几乎不假思索地拿出1个20元、1个l0元、1个5元和2个1元的钱币交给顾客。人们不仅能很快决定要拿哪些钱币，而且与其它找法相比这时拿出的钱币的个数肯定是最少的。在这里，收货员实际使用了这样的算法：首先选出一个面值不超过37元的最大面额钱币（20元），然后从37元中减去20元，剩下17元中再选出一个不超过17元的最大面额钱币（10元），如此做下去，直到找足37元。这就是所谓的贪心法。,7.2.5贪心法,2、最短路径顶点为城市，边上的代价为两城市问的里程。在图中找一条经过所有结点一次的回路，并使里程的总和为最小。可以按这样一个想法去做：首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：1)不会有三条边(候选边及已入选边)与同一顶点相关联。2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。最后求得的回路是125341，代价是14。图中最小代价的回路是12543一1，代价是10。这也是典型的贪心策略。,7.2.5贪心法,2、最短路径可以按这样一个想法去做：首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：1)不会有三条边(候选边及已入选边)与同一顶点相关联。2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。最后求得的回路是125341，代价是14。图中最小代价的回路是12543一1，代价是10。这也是典型的贪心策略。,7.2.5贪心法,贪心法主要有以下两个特点：（1）贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。（2）最优子结构性质：算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解。,7.2.6动态规划,动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代美国数学家贝尔曼（RechardBellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解决多阶段过程优化问题的新方法动态规划,7.2.6动态规划,例如，要生产一批雪糕。在这个过程中要分好多环节。购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售这样各个环节就可以看做是一个阶段，产品在不同的时候有不同的状态刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕，由液态变成固态。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。这就是所谓的动态规划。,7.2.6动态规划,多阶段决策问题，人们很容易举出下面这个例子。多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AB、BC、CD）。我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。,7.2.6动态规划,多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。动态规划思想实质是分治思想和冗余解决方法的结合。动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出