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

递归与迭代的区别,关于递归的回顾,一般定义程序调用自身的编程思想称为递归（recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。注意：(1)递归就是在过程或函数里调用自身；(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。,什么是迭代,迭代法是一种常用的算法设计方法,迭代是一个不断用新值取代变量的旧值,或由旧值递推出变量的新值的过程.,当一个问题的求解过程能够由一个初值使用一个迭代表达式进行反复迭代的时候,便可以用效率极高的重复程序描述迭代也是用循环结构实现的.只不过重复的操作是不断的从一个变量的旧值出发计算它的新值.其基本格式如下;迭代变量赋予初值;循环语句计算迭代式;新值取代旧值,例子:斐波那契序列;以兔子繁殖为例用月份n作为参数,表示计算第几个月后兔子的总数,i循环变量,迭代条件为:3=In)输出当前布局；Elsefor(j=1;j=n;+j)在第i行第j列放置一个棋子；If(当前布局合法)trial(i+1,n);移走第i行第j列的棋子；,贪心算法,所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。,贪婪算法（Greedyalgorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。,例子,假定有n个物体和一个背包，物体i有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（10,1=i=n.这个问题称为背包问（Knapsackproblem）。,其他,动态规划随机化思想概率分析摊销分析竞争分析还有很多愿意深入了解的同学可以看一些算法方面的书籍。但是需要注意，常用的算法了解即可，先把编程语言和高级编程等基础学好，算法暂时不可深入钻研。,有穷状态机（有限状态机）,有穷状态机很简单，在生活中可以找出很多这样的例子。但是教科书里讲得太复杂了，一会儿证明确定性有穷状态机和非确定性有穷状态机的等价性，一会儿证明正则表达式的这些理论的证明于编程没有太大用处，不过状态机本身却是文本处理利器，由于程序员在很多场合下都是在与文本数据打交道，所以状态机是程序员必备的工具之一。教科书上是这样定义有穷自动机的（略去可以百度）这个形式定义精确的描述了有穷状态机的含义。但是大部分人第一次看到它时，反复的读上几遍，仍然不知道它在说什么。幸好通过一些实例，我们可以很容易明白有穷状态机的原理。,自动门刚安装好的时候，我们可以认为它是关上的，所以关闭状态是自动门的初始状态。在理想情况下，自动门会一直运行，所以它没有接受状态，接受状态集F是空集。,例子,密码锁：以四位密码校验作为状态机的例子，连续输入2479就可以通过密码测试,统计一篇英文文章里的单词个数。有多种方法可以解这道题，这里我们选择用有穷状态机来解，做法如下：先把这篇英文文章读入到一个缓冲区里，让一个指针从缓冲区的头部一直移到缓冲区的尾部，指针会处于两种状态：“单词内”或“单词外”，加上后面提到的初始状态和接受状态，就是有穷状态机的状态集。缓冲区中的字符集合就是有穷状态机的字母表。如果当前状态为“单词内”，移到指针时，指针指向的字符是非单词字符(如标点和空格)，那状态会从“单词内”转换到“单词外”。如果当前状态为“单词外”，移到指针时，指针指向的字符是单词字符(如字母)，那状态会从“单词外”转换到“单词内”。这些转换规则就是状态转换函数。指针指向缓冲区的头部时是初始状态。指针指向缓冲区的尾部时是接受状态。每次当状态从“单词内”转换到“单词外”时，单词计数增加一。这个有穷状态机的图形表示如下：,Hashtable简介,哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法,散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：计算哈希函数所需时间关键字的长度哈希表的大小关键字的分布情况记录的查找频率1.直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=akey+b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。2.数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。3.平方取中法：取关键字平方后的中间几位作为散列地址。4.折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。5.随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。6.除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=keyMODp,p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。,7.4哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法定义哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2,以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突：key1key2，但H(key1)=H(key2)的现象叫同义词：具有相同函数值的两个关键字，叫该哈希函数的哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法哈希函数的构造方法直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=akey+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少,数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,平方取中法构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况,例关键字为：0442205864，哈希地址位数为4,除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)适于关键字长度不等的情况选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率,处理冲突的方法开放定址法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MODm，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)伪随机探测再散列：di=伪随机数序列,例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中,(1)H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3=(5+3)MOD11=8不冲突,38,(2)H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5-1)MOD11=4不冲突,38,(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：H1=(5+9)MOD11=3不冲突,38,再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,k其中：Rhi不同的哈希函数特点：计算时间增加链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,用链地址法处理冲突,哈希查找过程及分析哈希查找过程,哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度,例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等,(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODm,H(55)=3冲突，H1=(3+1)MOD16=4冲突，H2=(3+2)MOD16=5,H(79)=1冲突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD1