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

《迭代分治穷举回溯等算法概念的引入.ppt》由会员分享，可在线阅读，更多相关《迭代分治穷举回溯等算法概念的引入.ppt（42页珍藏版）》请在三一办公上搜索。

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

2、是迭代,迭代法是一种常用的算法设计方法,迭代是一个不断用新值取代变量的旧值,或由旧值递推出变量的新值的过程.,当一个问题的求解过程能够由一个初值使用一个迭代表达式进行反复迭代的时候,便可以用效率极高的重复程序描述迭代也是用循环结构实现的.只不过重复的操作是不断的从一个变量的旧值出发计算它的新值.其基本格式如下;迭代变量赋予初值;循环语句计算迭代式;新值取代旧值,例子:斐波那契序列;以兔子繁殖为例用月份n作为参数,表示计算第几个月后兔子的总数,i循环变量,迭代条件为:3=I=n程序中迭代变量为fib fib1.fib2,由递归引出的分治,一、求解大规模问题的复杂性,二、化整为零、分而治之,Pn,

3、p1n1,p2n2,pknk,s0,s1,sk,S,分解,分治,合并,递归与分治紧密相连,第二个例子,简单介绍算法,穷举法,穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。通常程序设计入门都是从穷举设计开始的。今天，计算机的运算速度非常快，应用穷举设计程序可快捷地解决一般数量的许多实际应用问题。穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。穷举法常用于解决“是否存在”或“有多少种可能”等问题。其中许多实际应用问题靠人工推算求解是不可

4、想象的，而应用计算机来求解，充分发挥计算机运算速度快、擅长重复操作的特点，穷举判断，快速简便。应用穷举时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。重复列举直接引发增解，影响解的准确性；而列举的遗漏可能导致问题解的遗漏。,例子,1.设计一个算法求解4排列问题，即输出4个数字 1 2 3 4 所有的排列；2,回溯法,回溯法也称为试探法，该方法首先暂时放弃关于规模的大小的限制，并将问题的候选解按某种顺序逐一枚举和检验，当发现当前候选解不可能是解时，就选择下一个候选解，倘若当前的候选解除了还不满足问题的规模的要求外，还满足其他所有要求，则继续扩大当前候选解的规模，并继续试探。如

5、果当前候选解满足包括问题规模在内的所有要求的时候，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模称为试探。回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。,八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线

6、上，问有多少种摆法。可以简化为四皇后问题,伪代码的实现数据结构一书,Void trial(int I,int n)If(in)输出当前布局；Else for(j=1;j=n;+j)在第i行第j列放置一个棋子；If(当前布局合法)trial(i+1,n);移走第i行第j列的棋子；,贪心算法,所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不

7、会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。,贪婪算法（Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯

8、。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容

9、易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。,例子,假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（10,1=i=n.这个问题称为背包问（Knapsack problem）。,其他,动态规划 随机化思想 概率分析 摊销分析竞争分析还有很多愿意深入了解的同学可以看一些算法方面的书

10、籍。但是需要注意，常用的算法了解即可，先把编程语言和高级编程等基础学好，算法暂时不可深入钻研。,有穷状态机（有限状态机）,有穷状态机很简单，在生活中可以找出很多这样的例子。但是教科书里讲得太复杂了，一会儿证明确定性有穷状态机和非确定性有穷状态机的等价性，一会儿 证明正则表达式的这些理论的证明于编程没有太大用处，不过状态机本身却是文本处理利器，由于程序员在很多场合下都是在与文本数据 打交道，所以状态机是程序员必备的工具之一。教科书上是这样定义有穷自动机的（略去可以百度）这个形式定义精确的描述了有穷状态机的含义。但是大部分人 第一次看到它时，反复的读上几遍，仍然不知道它在说什么。幸好通过一些实例，

11、我们可以很容易明白有穷状态机的原理。,自动门刚安装好的时候，我们可以认为它是关上的，所以关闭状态是自动门的初始状态。在理想情况下，自动门会一直运行，所以它没有接受状态，接受状态集F是空集。,例子,密码锁：以四位密码校验作为状态机的例子，连续输入2479就可以通过密码测试,统计一篇英文文章里的单词个数。有多种方法可以解这道题，这里我们选择用有穷状态机来解，做法如下：先把这篇英文文章读入到一个缓冲区里，让一个指针从缓冲区的头部一直移到缓冲区的尾部，指针会处于两种状态：“单词内”或“单词外”，加上后面提到的初始状态和接受状态，就是有穷状态机的状态集。缓冲区中的字符集合就是有穷状态机的字母表。如果当前

12、状态为“单词内”，移到指针时，指针指向的字符是非单词字符(如标点和空格)，那状态会从“单词内”转换到“单词外”。如果当前状态为“单 词外”，移到指针时，指针指向的字符是单词字符(如字母)，那状态会从“单词外”转换到“单词内”。这些转换规则就是状态转换函数。指针指向缓冲区的头部时是初始状态。指针指向缓冲区的尾部时是接受状态。每次当状态从“单词内”转换到“单词外”时，单词计数增加一。这个有穷状态机的图形表示如下：,Hash table 简介,哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法,散列函数能使对一个数据序列的访

13、问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：计算哈希函数所需时间 关键字的长度 哈希表的大小 关键字的分布情况 记录的查找频率 1.直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=akey+b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。2.数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的

14、后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。3.平方取中法：取关键字平方后的中间几位作为散列地址。4.折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。5.随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。6.除留余数

15、法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key)=key MOD p,p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。,7.4 哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki

16、是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2,以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫同义词：具有相同函数值的两个关键字，叫该哈

17、希函数的哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少,数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：

18、取任意两位或两位 与另两位的叠加作哈希地址,平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为：0442205864，哈希地址位数为4,除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随

19、机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率,处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函数 m哈希表表长 di增量序列分类线性探测再散列：di=1,2,3,m-1二次探测再散列：di=1,-1,2,-2,3,k(km/2)伪随机

20、探测再散列：di=伪随机数序列,例 表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中,(1)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5+2)MOD 11=7 冲突 H3=(5+3)MOD 11=8 不冲突,38,(2)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5-1)MOD 11=4 不冲突,38,(3)H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则：H1=(5+9)M

21、OD 11=3 不冲突,38,再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,k其中：Rhi不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,用链地址法处理冲突,哈希查找过程及分析哈希查找过程,哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函

22、数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,哈希表长为m=16，设每个记录的查找概率相等,(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD m,H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5,H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+

23、5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9,ASL=(1*6+2+3*3+4+9)/12=2.5,14,1,68,27,55,19,20,84,79,23,11,10,H(19)=6,H(14)=1,H(23)=10,H(1)=1 冲突，H1=(1+1)MOD16=2,H(68)=3,H(20)=7,H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8,H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4,H(11)=11,H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12,(2)用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希查找算法实现用线性探测再散列法处理冲突实现查找过程：同前删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以插入算法描述：用外链表处理冲突算法,Ch7_4.cCh7_5.c,一个博客的推荐,百度搜索“结构之法，算法之道”,