新编计算机导论 课件 5-问题求解- 常用算法

问题求解新编计算机导论常用算法穷举法01回溯法02本节CAPACITY内容1迭代法03递归法04分治法05智能算法062穷举法列举问题所有的可能解根据需满足的约束条件筛选解穷举法实例，如国王的婚姻问题中国王采用的方法TSP问题中逐条线路测试的方法也称枚举法、蛮力法、暴力破解法，是一种简单且直接的解决问题的方法基本思想是逐一列举问题的所有情形，并根据问题提出的条件逐个检验哪些是问题的解，主要步骤如下6.常用算法巧妙和高效的算法很少来自于穷举法，但基于下述因素，是一种常用的基础算法理论上可以解决可计算领域中的各种问题，在计算机运算速度非常快时，应用领域广阔对于小规模问题，穷举法求解的速度可以接受，无需耗费时间去设计效率更高的算法穷举可以作为某类问题时间性能的底限，用来衡量同样问题的高效率算法存在什么特例3回溯法又称试探法，是一种有着“通用解题法”美称的、比枚举的暴力破解“聪明”的搜索算法回溯法的核心思想是“向前走，碰壁回头”，通过对问题的归纳分析，找出求解问题的一条线索并沿着这一线索进行试探，若试探成功，则得到解；若试探失败就逐步往回退，然后换其他路线继续试探6.常用算法回溯法本质上是一种穷举性质的算法，但因其在搜索过程中通过约束条件的判定，排除错误答案，从而提高了搜索效率，是比穷举法效率更高的算法。回溯法求解四皇后问题的全部过程4迭代法确定迭代变量，指在迭代过程中可以直接或间接地不断由旧值推出新值的变量建立迭代关系式，指能够由变量的旧值推出新值的式子,可以采用或逆推的形式完成。顺推-从已知初始条件出发，从前往后逐步推算出问题结果逆推-从问题的结果出发，从后往前推，即顺推的逆过程迭代过程的控制，即确定迭代过程的执行和结束条件，不能无休止的执行。可明确计算出所需的执行次数时采用固定次数的循环实现无法确定迭代次数时需根据实际问题归纳迭代终止条件迭代法也称辗转法，是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或步骤)时，都从变量的原值推出它的一个新值。6.常用算法5例：用辗转相除法求两个正整数m和n的最大公约数(1)输入m和n；(2)计算m除以n的余数r；(3)如果r不为0，则执行步骤(4)，否则n即为最大公约数，输出n，算法结束；(4)m=n，n=r，并计算m和n的余数赋给r；(5)返回步骤(3)。辗转相除法，又名欧几里德算法(Euclideanalgorithm)，是求两个数的最大公约数的方法，其具体流程是：6.常用算法步数m值n值r值112421224212631260假设m=12，n=42，用辗转相除法求解的流程如图可知当r=0时，n=6，因此12和42的最大公约数为6。6递归法为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解构造出大问题的解这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解，特别地，当n=1时，能直接得解递归是直接或间接地调用自身的算法，是设计和描述算法的一种有力的工具，在复杂算法的描述中经常采用，能采用递归描述的算法通常有这样的特征：执行过程分递推和回归两个阶段6.常用算法汉诺塔问题是经典的只能用递归方式求解的实例，计算机中文件夹的复制也是一个递归问题递推阶段，把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解；回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解7例：Fibonacci数列十三世纪初，意大利数学家斐波那契（Fibonacci）在其所著《算盘书》中提出关于兔子繁殖的有趣问题：假设兔子出生后的第三个月就能生小兔，并且每月一次，每次恰好一对儿（一雌一雄）。若开始有一对儿初生的小兔，假定没有死亡的情况发生，问一年后共有多少对兔子？6.常用算法第一、第二个月的兔子对数只有1对，从第三个月开始，每个月的兔子对数为前两个月的兔子对数之和。即1,1,2,3,5,8,13,21，…，这组数字可以形成一个有规律的数列，称为斐波那契数列若令fn表示第n个月的兔子对数，则可导出如下计算斐波那契数列的递归公式f1=f2=1fn=fn-1+fn-2n>2由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。但对一些特殊问题，用递归实现比非递归实现简单，更易于理解8分治法分治法（Divide-and-conquer）就是分而治之，其基本原理就是把一个复杂的问题分解为若干同类型的较小子问题，再把子问题分解为更小的子问题，直至可以对子问题进行简单求解，然后对子问题的结果进行合并，从而得到原问题的解快速排序、归并排序等高效的算法以及国王的婚姻问题中宰相的解题方法都是基于分治策略的方法6.常用算法当前流行的云计算要解决的关键问题之一如何把一个非常大的计算问题自动分解到许多计算能力不是很强大的计算机上共同完成？Google的解决方案是称为MapReduce的程序，其基本原理就是常见的分治算法将一个大任务拆分为小的子任务，并完成子任务的计算过程称为Map将中间结果合并为最终结果的过程称为Reduce9智能算法智能算法是受人类智能、生物群体社会性或自然规律等启发而产生的一种新型算法6.常用算法自适应的结构、随机产生或指定的初始状态、适应度的评测函数、修改结构的操作、终止计算的条件、控制过程的参数等具有自学习、自组织、自适应的特征以及简单、通用、鲁棒性强、适于并行处理的优点，已在并行搜索、联想记忆、模式识别、知识自动获取等方