37986-00钟晴江-大学计算机大学计算机4 3-4 4

4.3算法策略,计算机科学家在算法研究过程中总结出了一些具有普遍意义的策略，为我们提供了一些有章可循的规律，本节介绍几种典型的算法策略，如回溯策略、分治策略、并行策略等。严格来说算法策略和算法是有区别的，它们是算法设计中的两个方面，算法策略是面向问题的，算法是面向实现的，但二者又密不可分，因为通过算法策略才能找出解决问题的算法。这些算法策略却体现了计算机科学发展中沉淀下来的智慧与一般性问题处理的优化原则。,4.3.1枚举算法：百钱买百鸡,【例410】“百钱买百鸡”：公鸡每只5元，母鸡每只3元，小鸡3只1元。问100元钱买100只鸡，有多少种买法？,【解】这是一个求解不定方程问题，设x，y，z分别为公鸡、母鸡和小鸡的只数，可列出下面的代数方程：x+y+z=1005x+3y+z/3=100,按题目再也写不出其它方程了，那么两个方程怎么解三个未知数呢？这类问题放在计算机科学中就是典型的枚举法问题了。,枚举算法的基本思想是：首先依据题目的部分条件确定答案的大致范围，然后在这范围内对所有可能的情况逐一验证，直到全部情况验证完为止。若某个情况验证符合题目的条件，则为该问题的一个答案，若全部情况验证完后均不符合题目的条件，则该问题无解。,这里x，y，z为正整数，由于鸡的总数是100，可以确定x，y，z的取值范围：（1）x的取值范围为0100（2）y的取值范围为0100（3）z的取值范围为0100,遍历x，y，z的所有可能组合，因为解必在其中，而且不止一个解，只要某种组合符合上述两个方程就是我们要找的解，遍历完所有可能的组合，也就找到了问题的所有解。,算法描述：/把x，y，z可能的取值(0100)一一列举循环（令x从0到100）循环（令y从0到100）循环（令z从0到100）/下面判断x，y，z的取值是否满足两个约束条件若（x+y+z=100且5x+3y+z/3=100）则输出x，y，z的值/找到一个解，即一种买法,使用枚举法时要注意两点：解空间的划定必须保证问题的全部解。如果解空间集合用H表示，问题的解集合用h表示，那么只有当hH时，才能使用枚举法求解。解空间及问题的解集一定是离散的集合，也就是说集合中的元素是可列的，有限的。,枚举算法能解决许多实际问题，是一种最为直接，实现最为简单的算法，但同时也是最为耗时的一种算法，它用时间上的牺牲换来解的全面性保证。因此，枚举法也叫穷举法或强力法。,在枚举算法中枚举对象的选择也非常重要，选择适当的枚举对象可以获得更高的效率本题中由于三种鸡的和是固定的，总价也是固定的，因此只要枚举公鸡x和母鸡y，小鸡根据约束条件求得，这样就缩小了枚举范围，优化了算法过程。,（1）x的取值范围为020（2）y的取值范围为033（3）当x和y确定后，z=100-x-y,【课堂练习】用优化的枚举法解决百钱买百鸡问题，请描述其算法过程。,4.3.2递归算法：汉诺塔问题,先给大家讲一个故事：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：。这个故事没完没了地重复着，直到讲故事的人累了，这就是一个递归的思想，故事中直接调用了故事本身。下面看一个具体的例子。,有一户人家，生养了6个活泼，调皮的孩子。一天，家里来客人，见了这一群孩子，很是喜爱，于是就问老大：“你今年几岁了？”，老大故意说：“我不告诉你，但我比老二大2岁。”客人问老二：“你今年几岁了？”，老二也调皮地说：“我也不告诉你，我比老三大2岁。”客人挨个问下去，孩子们的回答都一样，轮到最小的老六回答时，他诚实地回答：“3岁了。”客人马上就推算知道了老五的年龄，再往回就轻易地推算出了老四，老三，老二和老大的年龄了。庆幸老六诚实地告诉了客人真实年龄，要不这个问题就难解了。,【例411】猜猜我几岁,【解】设老大到老六的年龄为age(1)age(6)。客人的推算过程如下图所示：,【例412】用递归法求N阶乘。,【解】解题思路如下：问我n！，我不知道，但我知道n！是n(n-1)！问我(n-1)！，我不知道，但我知道(n-1)!是(n-1)(n-2)！问我2！，我不知道，但我知道2！是21！问我1！，我知道1！是1,这是递归的思维方式，每次重复问题本身，但又比上一次简单一些，直到问题简单到直接可以说出答案，如1！=1。所以说递归算法就是直接或间接地调用原算法本身的一种算法。,上述过程是回推。接下去就是递推了：知道了1！=1，就知道了2！是2知道了2！=2，就知道了3！是6最终知道了n!,所以说递归就是回推加上递推的过程。递归必须具备两个条件：问题本身具有递归性质；递归必需有结束条件，即递归出口。,其实，上述两个例子完全可以用非递归方法求解，而且更容易。但有些问题就不这样，如Hanoi塔问题就是递归思想的典型例子。,相传在印度有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下往上穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。,请问64片金片按规则从A针移到C针需要移多少次？若每秒移1个金片，多长时间内能移完？,【例413】Hanoi塔,【分析】注意问题的关键是要求把64个圆盘从第一根针移到第三根针上，必须满足如下三个条件：（1）一次只能移动一个盘子（2）不允许把大盘放在小盘上面（3）盘子只能放在三根针上,（1）盘1移动到丙针（2）盘2移动到乙针（3）盘1移动到乙针（4）盘3移动到丙针,（5）盘1移动到甲针（6）盘2移动到丙针（7）盘3移动到丙针共计移动7次完成任务。,先设3个圆盘从小到大依次称呼为1，2，3号盘，移动方法如下：,【思考】,4个圆盘怎么移，移动几次？假如有10个圆盘呢?,结论是4个圆盘要移15次10个圆盘就要移1023次！,我们把这个问题抽象出来，就是把n个盘子借助B针从A针移到C针。解决的方法如下：,【解】移动的过程可分解为三个步骤：第1步：把A上的n-1个圆盘移到B上；第2步：把A上的一个圆盘移到C上；第3步：把B上的n-1个圆盘移到C上；,至于第1步（或第3步）中如何把A上的n-1个圆盘移到B上，那就回到问题本身了，同样也要三个步骤：（1）把A上的n-2个圆盘移到C上；（2）把A上的一个圆盘移到B上；（3）把C上的n-2个圆盘移到B上。如此继续，n值不断减少，直到n=2，则：（1）将A上的1个圆盘移到B上；（2）再将A上的一个圆盘移到C上；（3）最后将B上的1个圆盘移到C上。而移动一个圆盘简直易如反掌，任务就此解析完毕。,Hanoi算法可用递归函数实现，具体描述如下：Hanoi(n,A,B,C):/n个盘子从A移到C，借助B若(n=1)则输出A“移到”C否则Hanoi(n-1,A,C,B)/n-1个盘子从A移到B，借助C输出A“移到”CHanoi(n-1,B,A,C)/n-1个盘子从B移到C，借助A,不管这个起源于印度的古老传说的可信度有多大，如果考虑把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。需要移动多少次呢?,当n=64时:h(64)=264-1=18446744073709551615,假如每秒钟移动一个盘子，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31556952秒，计算一下是：1844674407370955161531556952=584554049253.855年,这表明僧侣们一刻不停地来回搬盘子，移完这些金片需要5845亿年以上。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭了！,递归作为一种算法在程序设计中被广泛应用，它常常把一个大型的复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。但凡事总有两面性，用递归算法解决一些复杂问题时，往往在形式上更加简洁，易于理解，但是递归方法的运行效率较低，时间和空间复杂度都比较高。因此，在解决具体问题时还需要综合平衡，折衷处理。,【课堂练习】小猴吃桃,有一天小猴子摘下若干个桃子，当即吃了一半还觉得不过瘾，又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子的一半多一个。到第5天早上，小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?请用递归算法表示。,4.3.3回溯算法：八皇后问题,孩子们在游乐园里喜欢玩“走迷宫”游戏，如图。这类问题难以归纳出简单的数学模型，只能靠枚举和试探。先选出一条试着走走看。如果此路不通，便退回来另寻他途，就是“走不通就调头”的策略。直到最终找到适当的出路（有解）或证明无路可走（无解）为止。,这种“枚举试探失败返回再枚举试探”的求解方法，称为回溯。回溯算法也叫试探算法，它是一种系统地搜索问题的解的方法。许多复杂问题或规模较大的问题都可以使用回溯法求解，因此，回溯法又有“通用解题方法”的美称。八皇后问题是回溯算法的经典实例。下面就以“八皇后问题”为例，说明怎样用回溯法求解问题。,求解如何在一个8*8的棋盘上无冲突地摆放8个皇后棋子。在国际象棋里，皇后的移动方式为横竖交叉的，即任意一个皇后所在位置的水平、竖直，以及45度角斜线上均不能出现皇后的棋子。,【例414】八皇后问题,为了书写的方便，下面以四皇后问题为例用图解的方法介绍回溯算法。首先构建出一棵解空间树，通过探索这棵解空间树，可以得到四皇后问题的一种或几种解。这样的解空间树共有4棵。,上图所示根结点派生出4个子结点，每个子结点都示意出前两个皇后的可能摆放的位置。每个子结点又可以派生出4个子结点，每个结点都示意出前3个皇后可能摆放的位置整个解空间树为一棵四叉的满树，包含85个结点。应用回溯法求解四皇后问题的思路是：从根结点出发，深度优先搜索整个解空间树。当访问根结点的第一个孩子时，发现该结点不包含问题的解，也就是说，该结点所示的皇后的摆法不符合四皇后问题的要求，于是停止向下探索，回溯到根结点，继续探索根结点的下一个孩子结点，这就是所谓的剪枝操作，这样可以减少搜索的步数，以尽快找到问题的答案。,最终可以搜索出四皇后问题的一个解，它的搜索路径在图中用粗实线表示。四皇后问题很容易扩展成为八皇后问题或N皇后问题。回溯法在诸多方面都有应用，如计算机中的典型问题：0-1背包问题，装载问题等，而这些都是非常难解的问题。,4.3.4分治算法：找出伪币,一个国王要赏赐给一个大臣30枚金币，但是其中有一枚是假币。国王提出要求：只能用一个天平作为测量工具，并用尽量少的比较次数找出这枚假币，那么余下的29枚金币就赏赐给这个大臣；否则这个大臣将得不到赏赐。已知假币要比真币的分量略轻一些。聪明的大臣思考片刻，很快用天平找出了这枚假币，于是得到了剩下的29枚金币。你知道这位大臣是如何找到假币的吗？注意用尽量少的比较次数找出这枚假币。,【例415】找出伪币,【解】算法思想如下：一种最简单的办法是应用天平进行两两比较。首先给硬币编上序号（130），然后按照下面的步骤进行两两比较：第1步：用天平比较第1枚和第2枚硬币的重量，如果天平两边平衡，则进行第2步操作，否则较轻的一边的硬币为假币。第2步：用天平比较第3枚和第4枚硬币的重量，如果天平两边平衡，则进行第3步操作，否则较轻的一边的硬币为假币。最坏的情况是当比较到第29枚和第30枚硬币时才得出结果，也就是说第29枚或第30枚硬币是假币的情况。,应用这种方法进行硬币的两两比较，最终筛选出假币的序号虽然实施起来简单，易于理解，但是效率较低，没有达到国王提出的“用尽量少的比较次数”的要求。,其实有一种更高效的找假币的方法利用分治的策略找出假币。先将所有的硬币等分为两份，放在天平的两边。因为假币的分量较轻，因此天平的一侧中一定包含假币。再将较轻的一侧中的硬币分为两份，重复上述的做法。直到剩下2枚硬币，可用天平直接找出假币来。思考：在这个比较的过程中，若出现硬币无法等分的情况怎么办呢？,分治算法，即“分而治之”，就是把一个复杂的问题分解成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即为子问题的解的合并。因此，分治法解题的一般步骤为：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题逐层合并构成原问题的解；,由于分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。因此，分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。分治法是很多高效算法的基础，如前面提到的排序算法中的快速排序、归并排序，二分搜索都用到了分治的思想。,4.3.5并行算法：国王的婚姻,很久以前，有一个年轻的国王，他酷爱数学，聘请了当时最有名的数学家当宰相。邻国有一位聪明美丽的公主，国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48770428433377171的一个真因子，一天之内交卷。”国王听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？,【例416】国王的婚姻,但是这个国王从早一直算到晚，共算了30000多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223092827是它的一个真因子。国王很快验证了这个数确能除尽48770428433377171。公主说：“我再给你一次机会，再求一个17位数的真因子，如果还是求不出，将来您只好做我的证婚人了。”国王回国，并向宰相请教，大数学家仔细思考后认为一个17位数最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后，国王用这个办法求婚成功。,【分析】这个童话故事中，国王最先使用的是顺序算法，也就是串行计算，依靠个人的能力逐个数进行演算，即便最终能找到答案，也是一个十分漫长的过程。传统的计算机都是这样求解问题的。宰相提出的是并行算法，也就是并行计算，它依靠大量的人力资源，在短时间内就能获得想要的计算结果。,【分析】并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它基于一个简单的想法用多个处理器来协同求解同一个问题，即将问题分解成若干部分，各部分均由一个独立的处理器并行计算。总的来说，并行操作能让有些事情做得更快，关键是如何分解成若干个尽量相互独立的子问题，即寻找分解问题的最佳方案，从而使计算机能够以并行的方式高效处理它们。,【分析】但是，并不是所有的问题都能并行处理的。因为有些问题需要先完成一部分然后才能完成下一部分的工作。例如一个人需要9天时间来挖一个9米长的水渠，那么9个人同时挖就能在一天内完成了，但是如果是挖9米深的洞，事情就没那么简单了。因为一个女人可以九月怀胎生下一个小孩，但并不意味着9个女人一起努力，就能让小孩在一个月之内生出来的。,在过去的50年间，计算机技术飞速发展，芯片的处理速度以大约每18个月翻一翻的速度增长，然而现在已经接近了一个极限，要让计算机变得更快的梦想变得越来越困难了。在此情况下，人类萌发出一个很棒的点子，即采用多个处理器，让每个处理器同时处理问题的不同部分，这一方法就是并行计算。如一台计算机中安置多个处理器的多核处理器现已经被普遍用于个人计算机；由多台计算机通过网格连接在一起的网格计算可用于解决大型科研课题；另外，还有把数千台计算机紧密连接在一起的大规模并行超级计算机，它们都用到了并行的思想。在日常生活中也处处有并行的影子，如我们可以一边听演讲一边记笔记，一边上网一边听音乐等等。,【提示】,算法是计算机的灵魂，是计算思维的集中体现，本节介绍的典型算法都是前人智慧的结晶，运用这些算法使得计算机的处理能力有了极大的提高，学习并掌握这些算法，对于我们深入地理解计算机，培养计算思维非常有意义。算法所体现的思想和方法正是计算思维的重要组成部分。本节所介绍的递归、并行、分治等典型算法其设计思想本身就是计算思维，这些思想方法均能够为其他领域中问题的求解提供方法指导，从而也印证了计算思维的普适性。,4.4可计算性与计算的复杂性,计算机能做的事情越来越多，甚至超越了它们的制造者。上个世纪末，“深蓝”凭借前所未有的搜索和判断棋局的能力，成为第一台战胜人类国际象棋世界冠军的计算机，那场人机大战曾让世界震撼了许久，但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识。然而仅仅十余年后，“沃森”却已经能凭借自己的算法，先“理解”问题，然后有的放矢地在海量的数据库中寻找关联的答案，“沃森”已经可以理解人的自然语言，并可以通过人类的方式来和人类在广泛的知识领域进行沟通！长此以往，工具必将在更多的方面超越它的制造者，人类开始担心自己是否有被取代的可能。而这一切，都来源于越来越精巧的计算，计算机似乎无所不能，宛如新的上帝。,果真如此吗？当然不是，事实上，不是所有问题计算机都能处理的。如“为我烹制一个汉堡”这样的问题是无法用计算机来解决的，至少在目前是这样。因此，有些问题计算机能计算；有些问题虽然能计算，但算起来很“困难”；有些问题也许根本就没有办法计算。这就产生了可计算理论，专门研究一个实际问题是否可以用计算机来解决的学科。一个可以使用计算机解决的问题是指“可以在有限步骤内”被计算机解决。分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上，因而可以尽早转而使用除计算机以外的其它的有效手段，以便集中资源在可以解决的问题上。,4.4.1计算机处理的局限性,计算机不是万能的，即使在它擅长的数值计算领域也有许多无可奈何的困难。请看下面的例子：有一个商人从城市C1出发，到其他10个城市去签定合同，每个城市必须至少去一次。这11个城市之间有的有直航班机，有的没有，其票价如图4.22所示。请为他选择一条旅行路线，使总票价尽量低。,【分析】这个问题有一个特定的称呼叫旅行商问题。是计算机领域中典型的难解问题。画出相应的连通图如下：,上图中结点代表各个城市，连线代表两个城市间有交通工具可直达，每条边的数字代表票价。包含所有顶点的闭合途径称为图的哈密顿环游，简称H环游。,在这个连通赋权图中权最小的H环游称为最小H环游。因此旅行商问题即为求上图的一个最小H环游。这个问题最早于19世纪初提出，多年来全球数学家绞尽脑汁，试图找到一个高效的算法，但至今还没有一个有效的好方法。这是为什么呢？最直观的解决办法就是找出图的所有H环游，比较它们的权重，权重最小的就是商人的最优旅行路线。我们尝试用穷举法求具有n个顶点的完全图的旅行商问题的最优解。若用一台每秒可运算108次的计算机来计算，下表提供了一个大约的运算时间。,当城市数为n时，组合路径数是n!，它的增长方式按照一种可怕的指数形式急剧增长。当n为20时，需要800年，当n为50时，需要1049年！,很显然，当城市数目不多时要找到最优解并不难，但随着城市数目的不断增大，组合数目将按指数方式增长，一直达到无法计算的地步，这就是所谓的“组合爆炸问题”。因此，这类问题不可计算是因为计算太复杂，不能在有效的时间内给出答案，也就是理论上可行，但实际上无法实现。,类似问题还有很多，如：装箱问题：有有限多个容量为1的箱子，以及N个货物（每个货物的重量均小于1），需要最少的箱子把所有的N个货物完全装完。背包问题：背包的容量为C，有N个物体，体积分别为s1,sn以及价值分别为p1,pn，寻找一个最大价值的装背包的方案。,尽管不少学者就此类问题提出了更多的解决思路，如用动态规划法、回溯法、分支限界法、贪心法等等，但至今还没有一个有效的好方法。但是人们离这个目标似乎越来越近了，国际上专门有一个“世界旅行商问题”的论坛，用于寻找世界上1904711座不同城市的最佳访问路径其中两个数据库包含世界上全部注册的城市或小镇，甚至还包括一些南极的研究基地，每个城市用小点来表示，把这些点描在地图上，它们的数量巨大到几乎拼出了一幅世界地图。,在这个问题被提出的2002年，算出的最短方案为7524170.430千米；到了2007年，一些数学家证明路径最短应为7512218.268千米（这也被称为“下界证明”，这是另外一个难解的课题）；2008年11月，有人写了一个计算机程序，找到了7515947.511千米的路径解决方案，比下界仅多出了0.0497%。最短路径应该介于这两个值之间，但是直到现在还没有人知道正确答案！“旅行商问题”的应用领域包括：如何规划最合理高效的道路交通，以减少拥堵；如何更好地规划物流，以减少运营成本；在互联网环境中如何更好地设置节点，以更好地让信息流动等。正因为这个问题的应用范围广泛，才吸引着科学家们孜孜不倦地研究着最优解决方案。,4.4.2计算复杂性与可计算性,1.计算的复杂性旅行商问题以及汉诺塔问题都属于理论上可解，但实际并不能行，这属于算法复杂性问题。算法复杂性包括算法的空间以及时间两方面的复杂性问题。旅行商问题以及汉诺塔问题关注的是算法的时间复杂性。关于汉诺塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示，旅行商问题的时间复杂度可以用O(n!)来表示，显然算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题有时也不能求解出来。相反，当算法的时间复杂度的表示是一个多项式，如O(n2)时，则计算机可以轻松处理，如各种排序的问题。因此，当一个问题的求解算法的时间复杂度大于多项式，譬如是个指数函数时，称为难解型问题。,在计算理论中，把多项式时间算法可求解的问题类称为P类，不确定性多项式时间算法可求解的问题类称为NP类，目前许多还不知道是否属于P类的现实问题都是属于NP类的。如果NP类的所有问题都能有效地归约到NP类中的某一个问题，则称这个问题是NP完全的。这样，如果某一个NP完全问题确实存在于P类中，那么P类和NP类重合，即有P=NP。这一命题的巨大的意义在于现已证明像装箱、路径、调度等许多组合问题以及其他科学领域中的一大批问题都是NP完全的。NP完全问题是NP类中最难的问题，如果对于NP完全问题中任意一个问题存在有多项式时间算法，则整个NP类问题都存在多项式时间算法，从而也就证明了PNP的命题。,然而，计算科学家们大都认为NP完全问题不存在有效的多项式算法，即有PNP，同样这一命题也未能得到证明。P？NP问题成了计算机科学带有根本性的一个重大难题。但现实生活中大多数有意义的问题又恰恰是NP问题，需要找到有效的算法，怎么办呢？一种思路是寻求问题的近似解，以期得到一个可接受的，是多项式时间的算法。,还记得国王的婚姻这个故事吗？国王最先使用的是一种顺序算法，其复杂性体现在时间方面；后面由宰相提出的是一种并行算法，其复杂性体现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。因为，当将一个问题分解