迭代分治穷举回溯等算法概念的引入

《迭代分治穷举回溯等算法概念的引入》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与迭代的区别关于递归的回顾一般定义程序调用自身的编程思想称为递归（recursion）。　　一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。　　注意：(1)递归就是在过程或函数里调用自身；(2)在使用递归策略时，必须有

2、一个明确的递归结束条件，称为递归出口。什么是迭代迭代法是一种常用的算法设计方法,迭代是一个不断用新值取代变量的旧值,或由旧值递推出变量的新值的过程.当一个问题的求解过程能够由一个初值使用一个迭代表达式进行反复迭代的时候,便可以用效率极高的重复程序描述迭代也是用循环结构实现的.只不过重复的操作是不断的从一个变量的旧值出发计算它的新值.其基本格式如下;迭代变量赋予初值;循环语句{计算迭代式;新值取代旧值}例子:斐波那契序列;以兔子繁殖为例用月份n作为参数,表示计算第几个月后兔子的总数,i循环变量,迭代条件为:3<=I<=n程序中迭代变量为fibfib1.fi

3、b2由递归引出的分治一、求解大规模问题的复杂性二、化整为零、分而治之Pnp1n1p2n2pknks0s1skS分解分治合并递归与分治紧密相连第二个例子简单介绍算法穷举法穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。通常程序设计入门都是从穷举设计开始的。今天，计算机的运算速度非常快，应用穷举设计程序可快捷地解决一般数量的许多实际应用问题。穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。穷举法常用

4、于解决“是否存在”或“有多少种可能”等问题。其中许多实际应用问题靠人工推算求解是不可想象的，而应用计算机来求解，充分发挥计算机运算速度快、擅长重复操作的特点，穷举判断，快速简便。应用穷举时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。重复列举直接引发增解，影响解的准确性；而列举的遗漏可能导致问题解的遗漏。例子1.设计一个算法求解4排列问题，即输出4个数字1234所有的排列；2回溯法回溯法也称为试探法，该方法首先暂时放弃关于规模的大小的限制，并将问题的候选解按某种顺序逐一枚举和检验，当发现当前候选解不可能是解时，就选择下一个候选解，倘若

5、当前的候选解除了还不满足问题的规模的要求外，还满足其他所有要求，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求的时候，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模称为试探。回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题

6、是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。可以简化为四皇后问题伪代码的实现《数据结构》一书Voidtrial(intI,intn){If(i>n)输出当前布局；Elsefor(j=1;j<=n;++j){在第i行第j列放置一个棋子；If(当前布局合法)trial(i+1,n);移走第i行第j列的棋子；}}贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义

7、上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。贪婪算法（Greedyalgorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭

8、代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问