大学计算机实践教程：第4章 算法与复杂性

大学计算机__计算思维导论南京航空航天大学2014版第4章算法与复杂性本章要点：典型的计算思维—算法思维：4.1排序问题及其算法

完成不同环境下查找和统计问题求解及算法问题；4.2递归及递归算法构造，用有限的语句来定义对象的无限集合；4.3遗传算法:计算复杂性与仿生学算法示例

生物系统的问题求解及其对难解性计算问题求解的启示示例。第4章算法与复杂性4.1排序问题及其算法4.1.1

排序问题4.1.2

基本排序算法4.1.3PageRank排序：排序问题的不同思考方法4.2递归及递归算法4.2.1递归:用有限的语句定义对象的无限集合4.2.2递归算法：自身调用自身，高阶调用低阶4.3遗传算法:计算复杂性与仿生学算法示例4.3.1

可求解与难求解问题4.3.2遗传算法:仿生学算法的简单示例3.3.3遗传算法暨问题求解算法的进一步探讨(不讲)4.1排序问题及其算法

4.1.1排序问题4.1.2基本排序算法4.1.3PageRank排序：排序问题的不同思考方法排序(Sort)：

对一组对象按照“关键字”递增(或递减)的排列的过程。“关键字”：是指对象的一个用于排序的特性。例如：对一组“人”进行排序：可按“年龄”/“身高”进行排序，“人”即为对象，而“年龄”、“身高”等则为“关键字”。在计算科学中,排序对象是多种多样的。排序--许多复杂问题求解的基础，如数据库查询、数据挖掘、搜索引擎等大规模数据处理算法实现的基础。通过排序可有效降低问题求解算法的执行时间。4.1.1排序问题1）结构化数据表的查找与统计需要排序下图为学生成绩表，以“记录”为元素，将大量数据组织成一张表。在数据表中，类似如下的查找或统计是使用频率非常高的操作：

(1)“查找80分以上的同学?”(2)“查找姓名为江海的同学及其相关信息?”(3)“查找学号为120300106同学的相关信息?”学号姓名成绩120300101李鹏88120300102王刚79120300103李宁94120300104赵凯69120300105张伟66120300106徐月85120300107闫宁95120300108杜岩44120300109江海77120300110周峰73学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44学号姓名成绩120300108杜岩44120300109江海77120300103李宁94120300101李鹏88120300102王刚79120300106徐月85120300107闫宁95120300105张伟66120300104赵凯69120300110周峰73(b)按关键字“学号”递增排序(c)按关键字“成绩”递减排序(d)按关键字“姓名”递增排序学号

姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73(a)未进行任何排序的表4.1.1排序问题1）结构化数据表的查找与统计需要排序怎样完成查找和统计呢？未排序的数据查寻，需要检索整个数据表才能正确回答上面的问题。需要访问n条记录。已按“关键字”排序的数据进行查询，则仅需访问一半甚至更少的记录便可得到正确的结果。当数据表的记录数非常庞大时，显而易见，数据排序则是节省时间提高查找效率的有效手段。4.1.1排序问题1）结构化数据表的查找与统计需要排序怎样对结构化的数据进行排序呢？内排序问题:待排序的数据可一次性地装入内存中，即可以完整地看到和操纵所有数据，使用数组或其他数据结构便可进行统一的排序处理的排序问题；外排序问题:待排序的数据保存在磁盘上，不能一次性装入内存，即不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；4.1.1排序问题1）结构化数据表的查找与统计需要排序怎样实现内排序和外排序呢？问题：某教师要对学生按身高排序。教师只能在容纳100人房间(相当于内存)中对学生进行排序。对于小于100人的学生排序问题属于内排序问题。对于大于100人的学生排序问题，学生并不能都进入房间，而只能在操场(相当于磁盘)等候，轮流进入房间，这样的排序便属于外排序问题。4.1.1排序问题2）非结构化数据(文档)的查找与搜索也需要排序针对图书馆/网上大量的文献/文档如何快速地查找一份文档？如何确定一份文档是否包含给定的一个或多个“关键词”？哪些词汇是一份文档的关键词？当用户输入一个关键词查询的时候，是否要扫描这几十几百几千万册文档呢？这些问题的解决需要倒排索引文件的技术4.1.1排序问题2）非结构化数据(文档)的查找与搜索也需要排序

倒排索引文件的技术对一份文档，去掉标点符号和一些辅助词汇，将所有出现的单词无重复地按照出现的频次由多到少排列出来。将频次排序在前面的若干个词汇，或者频次超过一定阈[yù]

值的若干个词汇作为本文档的关键词。对于所有的文档，建立一个“索引表”(类似于一般纸质图书后面都有的索引表)，通常称为倒排索引文件4.1.1排序问题4.1.1排序问题(a)Google的搜索结果排序示意(b)百度的搜索结果排序示意3）网上搜索的结果展现也需要排序

（PageRank：Google搜索引擎的网页排序算法）4.1.1排序问题1）内排序插入排序

基本思想：类似于打扑克牌时，一边抓牌，一边理牌的过程，每抓一张牌就把它插入到适当的位置，牌抓完了，也理完了这种策略被称为插入排序。4.1.2基本排序算法1）内排序--插入排序（后插算法）4.1.2基本排序算法1）内排序--插入排序（后插算法）4.1.2基本排序算法程序见文件夹第4章

算法与复杂性内排序--插入排序(后插算法).rap1）内排序选择排序基本思想：一个轮次一个轮次的处理。首先在所有数组元素中找出最小值的元素，放在A[1]中；接着在不包含A[1]的余下的数组元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一个元素。这一排序策略被称为选择排序。4.1.2基本排序算法1）内排序--选择排序4.1.2基本排序算法a[1]a[2]a[3]a[4]a[5]

36194

16394

1

3694

1

3

496

1

3

4

69选择法从小到大排序n个数从小到大选择法排序的算法1.n个数选择排序，要做n-1次选择；2.

每一次选择都是在尚未排好序的数中找最小数，交换到尚未排好序数的第一个位置上。for(i=1;i<=n-1;i++)//i控制选择的次数，共选择n-1次{第i趟扫描：将最小数从a[i]~a[n]中选择出来，交换到元素a[i]中。}4.1.2基本排序算法1）内排序--选择排序4.1.2基本排序算法程序见文件夹第4章算法与复杂性内排序—选择排序.rap1）内排序冒泡排序基本思想：一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较，将小的放前，大的放后--递增排序(或者是将大的放前，小的放后--递减排序)。4.1.2基本排序算法985420895420859420854920854290854209大数沉淀，小数起泡a[1]a[2]a[3]a[4]a[5]a[6]4.1.2基本排序算法第一趟扫描1）内排序—冒泡排序8542095842095482095428095420894.1.2基本排序算法a[1]a[2]a[3]a[4]a[5]a[6]第二趟扫描1）内排序—冒泡排序5420894520894250894205894.1.2基本排序算法a[1]a[2]a[3]a[4]a[5]a[6]第三趟扫描1）内排序—冒泡排序4205892405892045894.1.2基本排序算法a[1]a[2]a[3]a[4]a[5]a[6]第四趟扫描1）内排序—冒泡排序2045890245894.1.2基本排序算法a[1]a[2]a[3]a[4]a[5]a[6]第五趟扫描1）内排序—冒泡排序N个数从小到大冒泡法排序的算法：1.N个数排序，要进行N-1

趟扫描。2.第i趟扫描时，要做N-i次两两比较

第几趟扫描未排序数个数两两比较的次数

1NN-12N-1N-2

………………iN-(i-1)N-i3.具体记忆（假定N个数）

for(i=1;i<=N-1;i++)for(j=1;j<=N-i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}4.1.2基本排序算法4.1.2基本排序算法程序见文件夹第4章算法与复杂性内排序—冒泡排序.rap1）内排序—冒泡排序1）内排序三种基本排序算法的比较算法名称时间复杂度空间复杂度稳定性插入排序O(N2)O(1)稳定选择排序O(N2)O(1)不稳定冒泡排序O(N2)O(1)稳定算法稳定性：当有两个数据元素R和S，其用作排序依据的关键字值相等，且在原始数据中R出现在S之前，那么在排序后的数据中，R也将会在S之前。4.1.2基本排序算法1）内排序快速排序(只讲思想)基本思想：划分，从待排序列中任取一个元素(例如取第一个)作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子序列；然后再对各子序列重新选择中心元素并依此规则调整，直到每个子序列的元素只剩一个，此时便为有序序列了。如数的序列(5,1,7,3,6,9,4,2,8,10）,第一次划分后序列(2,1,4,3,5,9,6,7,8,10)。其它排序算法：希尔排序、归并排序、基数排序、堆排序等。4.1.2基本排序算法2）外排序（Externalsorting）4.1.2基本排序算法外排序问题:待排序的数据保存在磁盘上，不能一次性装入内存，即不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；2）外排序（Externalsorting）直观求解策略：1.将大的数据集切分为很多个子集合，如N个子集合;2.将每一个子集合装载到内存中，应用内排序算法对其进行排序，排好后再存储到外存（硬盘）上。这样就获得了N个已排好顺序的数据集;3.将（排好序的）N个数据集合并，并使合并后的数据集仍然保持有序，即可实现对整个数据集的排序；当然，在合并的过程中仍面临着内存空间的约束，所以不得不边排序、边存储（到硬盘）；外排序通常采用的是一种“排序-归并”的策略；外排序例子(不讲)。4.1.2基本排序算法2）外排序（Externalsorting）外排序环境：为充分利用存储空间，操作系统将外存和内存均划分为若干相等大小的子空间，被称为块(Block)。由外存向内存的数据移动被称为读磁盘而由内存向外存的数据移动被称为写磁盘操作系统通常按块读写磁盘并提供了相应的读磁盘函数简记为ReadBlock，和写磁盘函数简记为WriteBlock。4.1.2基本排序算法

一块可存放Rblock个数据元素待排序数据元素有

Rproblem个需磁盘块数

Bproblem=Rproblem/Rblock图中示意

Rblock=5Rproblem=60，

Bproblem=12图中示意内存块数Bmemory=64.1.2基本排序算法

已知：Sproblem为待排序元素集合，Rproblem—待排序集合中的元素个数，Rblock-磁盘块或内存块能存储的元素个数,Bmemory-可用内存块的个数,R(S)为求集合S的元素个数的函数，Mi为内存的第i块，Poutput为输出块内存中当前元素的指针。1.将待排序集合Sproblem划分为m个子集合S1,S2,...,Sm,其中Sproblem=

i=1,...,mSi，且Rproblem=

i=1,...,mR(Si),R(Si)<=Bmemory*Rblock,i=1,...,m(注:每个Si的元素个数小于内存所能装载的元素个数).2.fori=1tom3.{将Si,装入内存,并采用一种内排序算法进行排序,排序后再存回相应的外存中}/*步骤2和3完成子集合的排序。接下来要进行归并，M1,...,Mm用于分别装载S1,...,Sm的一块*/;4.fori=1tom5.{调用readblock函数，读Si的第一块存入Mi中,同时将其第一个元素存入Mcompare的第ith个位置;}6.设置Poutput为输出内存块的起始位置;7.求Mcompare中m个元素的最小值及其位置i。8．If(找到最小值及其位置i)then4.1.2基本排序算法

9．{将第ith个位置的元素存入Moutput中的Poutput位置,Poutput指针按次序指向下一位置；10. If(Poutput指向结束位置)then11. {调用WriteBlock按次序将Moutput写回磁盘；置Poutput为输出内存块的起始位置；继续进行;}12．

获取Mi的下一个元素.13. If(Mi有下一个元素)14. {

将Mi下一个元素存入Mcompare的第ith个位置。转步骤7继续执行。}15. Else

{

调用readblock按次序读Si的下一块并存入Mi；16. If(Si有下一块)17. {

将其第一个元素存入Mcompare的第ith个位置。转步骤7继续执行。}18. ELSE{返回一个特殊值如Finished，以示Si子集合处理完毕，Mi为空，且使Mcompare中的第ith位置为该特殊值，表明该元素不参与Mcompare的比较操作。转步骤7继续执行。}19.} 20.}/*若Mcompare的所有元素都是特殊值Finished，即没有最小值，则算法结束*/4.1.2基本排序算法

PageRank的基本概念PageRank是基于“从许多优质的网页链接过来的网页，必定还是优质网页”这一基本想法来判定所有网页的重要性，也是PageRank网页排序算法的精髓。网页的两种链接：正向链接和反向链接。正向链接:该页面指向其他页面的链接，它将对指向页面的重要度评价产生贡献，反向链接:其他页面指向该页面的链接，将对本页面的重要度评价产生贡献。4.1.3PageRank排序:排序问题的不同思考方法PageRank的基本概念网页的重要度指标：即PageRank值，被平均地分配到其每一个正向链接上面，作为对其他网页的贡献度；而由反向链接获得的贡献度被加入到本网页的重要度指标上。如下图所示：4.1.3PageRank排序:排序问题的不同思考方法PageRank的基本概念提高一个页面PageRank的要点，大致有3个方面：

(1)反向链接数(单纯意义上的受欢迎度指标)；

(2)反向链接是否来自推荐度高的页面(有根据的受欢迎指标)；(3)反向链接源页面的链接数(被选中的几率指标)。4.1.3PageRank排序:排序问题的不同思考方法PageRank的基本概念

PageRank自身是由Google计算的，而与用户检索内容的条件表达式完全无关。当用户的检索条件表达式被执行并查询出网页后，搜索引擎会按照网页的PageRank值对这些查询出的结果网页排序并呈现给用户。4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例可将网页超链接结构抽象为矩阵，用线性代数方法进行求解网页数为N，则矩阵为N×N的方阵，表达网页i(行)与网页j(列)的链接关系，矩阵的每个元素aij按如下方式取值。4.1.3PageRank排序:排序问题的不同思考方法右图用位图方式可视化地表示了Apache(web服务器软件)在线手册(共128页)的邻接矩阵。当黑点呈横向排列时，表示这个页面有很多正向链接；反之，当黑点呈纵向排列时，表示这个页面有很多反向链接。4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例转移概率矩阵设上述邻接矩阵记为A，将此邻接矩阵转置，记为AT。对AT进行归一化处理，即将AT的每个值除以其所在列的非零值的总个数，此即一概率形式，各列的概率之和为1。这样形成的矩阵在PageRank被称为“转移概率矩阵”，各个行向量含有N个概率变量，表示状态之间的转移概率。4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例PageRank的计算就是求转移概率矩阵最大特征值的特征向量网页i的重要度为Ri，各网页重要度的向量R，记为，即R=(R1,R2…,Rn)T，需要迭代计算，第j次迭代计算得到的R的结果记为R(j)。R的初始可设置为任意的值，记为R(0)=(R1(0),R2(0)…,Rn(0))T；按照转移概率计算一轮后，可得到R(1)=cMR(0)，再进一步计算R(2)=cMR(1)

，依次计算下去，可以通过c值调整，使得R(n)=R(n-1)，即R的值不再随迭代次数增加而发生变化，即R=cMR，此时的R被称为特征向量，即为所求各网页的PageRank。4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子(教材P178)4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子识别其邻接关系链接源页面ID链接目标页面

ID12,3,4,5,72131,242,3,551,3,4,661,5754.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子基于邻接关系构造邻接矩阵

A4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子构造PageRank的转移概率矩阵M4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子计算表示PageRank

的向量R(各个页面的等级数构成的向量)，存在着R=cMR的关系(c为定量)。为求R，可对矩阵

M

作特征值分解4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子分析PageRank的名次和反向链接的数目是基本一致的4.1.3PageRank排序:排序问题的不同思考方法PageRank算法及实例由问题到数学的典型示例简单例子分析4.1.3PageRank排序:排序问题的不同思考方法算法的复杂性及分析Google搜索引擎所能检索到的网页的数量以及网页之间的链接数量是巨大的，而且整个互联网和Internet在不停地变化。例如，当2013年3月14日在Google搜索引擎中输入computer关键词之后，反馈结果是“找到约2,450,000,000条结果”，而这仅仅是与computer相关的网页。对于这些天文数字网页的存储、网页之间的链接关系及PageRank的计算，普通的计算机和服务器完全无法胜任，而必须使用并行计算/分布式计算技术，利用大批的服务器（服务器农场）来完成。4.1.3PageRank排序:排序问题的不同思考方法算法的复杂性及分析实际搜索引擎中所使用的PageRank算法，应该也必须是一个可由多台计算机并行执行或分布式执行的算法，这是PageRank算法的一大特点和复杂之处。那么，这样的算法如何来实现？感兴趣的同学请进一步学习并行计算、分布式计算相关的知识。PageRank算法也面临其他一些具体实现所必须考虑的问题，例如danglingpage问题、收敛问题等，感兴趣的同学请自行学习和分析。4.1.3PageRank排序:排序问题的不同思考方法4.2递归及递归算法4.2.1递归:用有限的语句定义对象的无限集合4.2.2递归算法举例：自身调用自身，高阶调用低阶1）递归的感性认识--具有自相似性重复的事物4.2.1递归:用有限的语句定义对象的无限集合

1）递归的感性认识--具有自相似性重复的事物4.2.1递归:用有限的语句定义对象的无限集合

2）递归的概念递归(Recursion)在数学与计算机科学中，是指用函数自身来直接或间接地调用自身函数的方法，也常用于描述以自相似方法重复事物的过程，它可以用有限的语句来定义对象的无限集合。递归语言的例子：“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？(从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？(从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？(从前……)))”。4.2.1递归:用有限的语句定义对象的无限集合

递归的例子例1年龄问题：有5个人坐在一起，问第5个人的年龄，他说他比第4个人大2岁；问第4个人的年龄，他说他比第3个人大2岁；问第3个人的年龄，他说他比第2个人大2岁；问第2个人的年龄，他说他比第1个人大2岁；问第5个人的年龄，他说他10岁；问第5个人的年龄。例2阶乘问题：求n!n!=n*(n-1)!例3Fibonacci数列问题:

无穷数列

1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。1n=1,n=2f(n)=f(n-2)+f(n-1)n>24.2.1递归:用有限的语句定义对象的无限集合

递归的例子例4

汉诺塔问题：汉诺塔（也称梵天塔）是印度的一个古老传说。据说开天辟地之神勃拉玛在一个庙里留下了三根金刚石柱，并在第一根上从上到下依次串着由小到大不同的64片中空的圆型金盘，神要庙里的僧人把这64片金盘全部搬到第三根上，而且搬完后，第三根柱子上的金盘仍保持原来由小到大的顺序。同时要求每次只能搬一个，可利用中间的一根石柱作为中转，并且要求在搬运的过程中，不论在哪个石柱上，大的金盘都不能放在小的金盘上面。神说，当所有的金盘都从事先穿好的那根石柱上移到另外一根石柱上时，世界就将在一声霹雳中消灭了。4.2.1递归:用有限的语句定义对象的无限集合

3）递归问题的求解过程要求解递归问题p(n)，可以将问题一步步简化(递归步骤)；要求p(n)应先求p(n-1)

要求p(n-1)应先求p(n-2)要求p(n-2)应先求p(n-3)……

逐步递归，但问题的性质没有改变。

大事化小

当问题简化到递归基础(回推点)时，便开始回推，直到推出问题p(n)。小事化了

过程：逐步递归→递归基础→回推，最终使递归问题p(n)得到解决。4.2.1递归:用有限的语句定义对象的无限集合

3）递归算法的求解特点（程序的书写特点）如果是递归基础（回递点），回推。不是递归基础（回推点），进一步递归。逐步递归回推过程递归基础（回推点）4.2.1递归:用有限的语句定义对象的无限集合

例1年龄问题有5个人坐在一起，问第5个人的年龄，他说他比第4个人大2岁；问第4个人的年龄，他说他比第3个人大2岁；问第3个人的年龄，他说他比第2个人大2岁；问第2个人的年龄，他说他比第1个人大2岁；问第5个人的年龄，他说他10岁；问第5个人的年龄。递归公式（数学模型）

10n=1递归基础age(n)=age(n-1)+2n>1递归步骤4.2.2递归算法举例：自身调用自身，高阶调用低阶例1年龄问题—递归算法Raptor流程图4.2.2递归算法举例：自身调用自身，高阶调用低阶例2阶乘问题：求n!

递归公式（数学模型）

1n=0或n=1

fac(n)=n×fac(n-1)n>14.2.2递归算法举例：自身调用自身，高阶调用低阶例2阶乘问题—递归算法Raptor流程图4.2.2递归算法举例：自身调用自身，高阶调用低阶例3Fibonacci数列问题:无穷数列1，1，2，3，5，8，13，21，34，55，…，称为Fibonacci数列。它可以递归地定义如下：递归公式4.2.2递归算法举例：自身调用自身，高阶调用低阶例3Fibonacci数列问题—递归算法Raptor流程图4.2.2递归算法举例：自身调用自身，高阶调用低阶例4

汉诺塔问题汉诺塔（也称梵天塔）是印度的一个古老传说。据说开天辟地之神勃拉玛在一个庙里留下了三根金刚石柱，并在第一根上从上到下依次串着由小到大不同的64片中空的圆型金盘，神要庙里的僧人把这64片金盘全部搬到第三根上，而且搬完后，第三根柱子上的金盘仍保持原来由小到大的顺序。同时要求每次只能搬一个，可利用中间的一根石柱作为中转，并且要求在搬运的过程中，不论在哪个石柱上，大的金盘都不能放在小的金盘上面。神说，当所有的金盘都从事先穿好的那根石柱上移到另外一根石柱上时，世界就将在一声霹雳中消灭了。4.2.2递归算法举例：自身调用自身，高阶调用低阶例4汉诺塔问题递归算法（n个盘子从A柱通过B柱移动到C柱）

if(n==1)//如果是回推点将A柱上最大的盘子移动到C柱上else//不是回推点{将n-1个盘子从X柱通过Z柱移动到Y柱上然后把X上最下面的盘子放到Z上把n-1个盘子从Y柱通过X柱移动到Z柱上}

4.2.2递归算法举例：自身调用自身，高阶调用低阶4.2.2递归算法举例：自身调用自身，高阶调用低阶4.2.2递归算法举例：自身调用自身，高阶调用低阶例4

汉诺塔问题—递归算法Raptor流程图4.2.2递归算法举例：自身调用自身，高阶调用低阶例4汉诺塔问题（程序实现）#include<iostream.h>voidHanoi(intn,charx,chary,charz)//将n个盘子从X柱通过Y柱移动到Z柱上{if(n>1){Hanoi(n-1,x,z,y);//将n-1个盘子从X柱通过Z柱移动到Y柱上

cout<<x<<"->"<<z<<'\n';//然后把X上最下面的盘子放到Z上

Hanoi(n-1,y,x,z);//把n-1个盘子从Y柱通过X柱移动到Z柱上

}elsecout<<x<<"->"<<z<<'\n';//只有一个盘子时，直接把它从X放到Z上}voidmain(){Hanoi(3,'A','B','C');}//3个盘子从A柱通过B柱移动到C柱上4.2.2递归算法举例：自身调用自身，高阶调用低阶4）小结递归方法的典型特征:

自身调用自身,高阶调用低阶来实现定义和求解!其最有价值之处是构造，即用有限的语句来定义或描述对象的无限集合，因此所谓构造性是计算机软硬件系统的最根本特征。20世纪30年代正是可计算的递归函数理论与图灵机理论等一起为计算理论的建立奠定了基础。复杂性评价：运行时间较长占用较多的存储空间优点：编程容易4.2.2递归算法举例：自身调用自身，高阶调用低阶4.3遗传算法:计算复杂性与仿生学算法示例4.3.1可求解与难求解问题4.3.2遗传算法—仿生学算法的简单示例4.3.3遗传算法暨问题求解算法的进一步探讨现实世界中的各种问题可计算问题：计算机在有限时间内能够求解的问题；难解性问题：计算机在有限时间内不能求解的问题；不可计算问题：计算机完全不能求解的问题。判断问题能不能计算计算复杂性：是问题规模的函数（例：旅行商问题），指问题的一种特性，即利用计算机求解问题的难易性或难易程度。

计算复杂性的衡量标准：一是计算所需的步数或指令条数，即时间复杂度；二是计算所需的存储空间大小，即空间复杂度。（问题的计算复杂性还涉及到求解算法）4.3.1可求解与难求解问题问题的计算复杂性还涉及到求解算法假设有求解同一个问题的两个算法，问题的规模记为n=60第一个算法的计算复杂性是n3（多项式函数表达）第二个算法的计算复杂性是3n（指数函数表达）用每秒百万次的计算机来计算第一个算法只要用时0.2秒；第二个算法就要用时4

1028秒，也就是1015年，相当于10亿台每秒百万次的计算机计算一百万年。当n很大时，这两个算法的效率差异是很大

4.3.1可求解与难求解问题问题的计算复杂性还涉及到求解算法一个问题如果存在多项式时间计算复杂性的算法，被认为是计算机能够求解的、能计算的或可计算的；一个问题如果没有多项式时间计算复杂性的算法，被认为是难解性问题

但是，要断定一个问题是否是难解性问题是很困难的。一个问题即使长期没有找到多项式时间计算复杂性算法，也不能保证以后就一定找不到，更不能依据此证明这个问题不存在多项式时间计算复杂性算法。4.3.1可求解与难求解问题1）P类问题和NP类问题

计算机理论界对计算问题有一个P类问题和NP类问题的划分

P类问题(PolynomialProblem)：计算机可以在有限时间内求解的问题，即在多项式表达的时间内能由算法求解的问题。换句话说，P类问题是总可以找到一个复杂性为O(na)算法求解的问题，其中a为整数。4.3.1可求解与难求解问题1）P类问题和NP类问题非确定性问题(Non-deterministicProblem)：有些问题，其答案无法由计算直接得到，只能通过间接猜算或试算来得到结果。NP类问题(Non-deterministicPolynomial)

：非确定性问题通常有个算法，它不能直接告知答案，但可以告知某个可能的结果是否正确，这种可以告知猜算或试算结果是否正确的算法，假如其复杂性为多项式时间，就叫做非确定性多项式问题，即NP类问题。如果NP类问题的所有可能答案都可以在多项式时间内进行正确与否的验算，则称之为完全非确定性多项式问题，即NP-Complete问题。4.3.1可求解与难求解问题2）NP类问题的一种典型求解思想NP-问题可用穷举法或称遍历法得到答案，即对解空间中每一个可能解进行验证，直到所有解都被验证是否正确，便能得到精确的结果。验证穷举法求解算法的计算复杂性则很可能是指数级别或阶乘级别，随问题规模增大很快便会变得不可计算。NP问题典型求解思想：

由于求精确解有可能变得不可计算，因此求取近似解(多项式时间的近似算法)的设计便成为解决这类问题一种可行的途径。4.3.1可求解与难求解问题2）NP类问题的一种典型求解思想近似算法所适应的问题是最优化问题，即要求在满足约束条件的前提下，使某个目标值达到最大或最小。对于一个规模为

n的问题，近似算法应满足以下两个基本要求：(1)算法的时间复杂性：要求算法能在

n阶多项式时间内完成。即通过“近似”而不是“精确”，来使复杂性为指数级别的计算问题化简为多项式级别的计算问题。(2)解的近似程度：算法的近似解应满足一定的精度，即达到“满意”（满足实际应用需求）的程度。4.3.1可求解与难求解问题3）仿生学算法自然界是人类各种技术思想、工程原理及重大发明的源泉。模仿鱼类的形体造船，以木桨仿鳍。模仿蝙蝠释放出一种超声波接收回声的特性发明了雷达。研究蚂蚁的群体行为，提出了蚁群算法。研究了蜂群行为，提出了蜂群算法等。这些算法可广泛用于

NP问题的求解，通称为仿生学算法，或称为进化算法(EvolutionaryAlgorithm)一种典型的进化算法是遗传算法(GeneticAlgorithm)，模仿生物在自然界中的遗传、繁衍以及优胜劣汰适者生存的规律而发明。4.3.1可求解与难求解问题1）生物学中的遗传与进化生物领域的遗传(Heredity)自然界的生物从其父代继承特性或性状，这种生命现象被称为遗传(Heredity)。通过遗传，生物可以一代代繁衍，而繁衍出的后代则随环境的变化，优胜劣汰，适者生存，实现进化。4.3.2遗传算法—仿生学算法的简单示例基因重组新个体的染色体繁衍后的种群种群新一代种群个体A的染色体个体B的染色体染色体B的基因片段染色体A的基因片段个体对环境的适应性:优胜劣汰两个个体新个体

染色体与基因基因重组方式？优胜劣汰依据？4.3.2遗传算法—仿生学算法的简单示例1）生物学中的遗传与进化生物领域的遗传(Heredity)个体:生物体,基本功能单位是细胞

；染色体:细胞中的一种微小的丝状化合物,生物体中遗传信息的载体，由DNA（脱氧核糖核酸）的物质所构成，DNA在染色体中有规则地排列着，形成一个链状且相互卷曲的双螺旋结构；基因：基本的遗传信息，是染色体的片段，基本的遗传单位。遗传基因在染色体中所占据的位置称为基因座(Locus)；同一基因座可能有的全部基因称为等位基因(Allele)；某种生物所特有的基因及其构成形式称为该生物的基因型而该生物在环境中呈现出的相应的性状称为该生物的表现型

4.3.2遗传算法—仿生学算法的简单示例1）生物学中的遗传与进化生物领域基本的遗传方式—基因重组方式复制(Reproduction)：遗传过程中，父代的遗传物质DNA被复制到子代。即细胞在分裂时，遗传物质DNA通过复制而转移到新生的细胞中，新细胞就继承了旧细胞的基因。交配/杂交(Crossover)：有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。上代染色体切断位置的随机性增加了下一代生物性状的多样性，例如同一父母的多个不同子女其特性是不同的。突变(Mutation)：在进行细胞复制时，虽然概率很小，有可能产生某些复制差错，但其却使DNA发生某种突变，产生出新的染色体。这些新的染色体表现出新的性状。4.3.2遗传算法—仿生学算法的简单示例1）生物学中的遗传与进化生物界的进化—优胜劣汰，适者生存生物的进化是以集团形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。组成群体的单个生物称为个体(Individual)，每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。依据个体适应度，淘汰劣质个体，保留优质个体的过程可被称为选择(Selection)。4.3.2遗传算法—仿生学算法的简单示例1）生物学中的遗传与进化生物界的进化—优胜劣汰，适者生存虽然还未完全揭开遗传与进化的奥秘，但几个特点却为人们所共识：(i)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状(ii)染色体由基因及其有规律的排列所构成，遗传和进化过程发生在染色体上；(iii)生物的繁殖过程是由其基因的复制过程来完成的；(iv)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(v)对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代。4.3.2遗传算法—仿生学算法的简单示例2）一个简单示例遗传算法的基本思想多项式函数求最小值此题不难求解其精确解，可以看出其精确解为X=9或者X=10。下面用遗传算法求解，以便理解遗传算法中的概念和基本思想。生物遗传中的重要概念，个体、染色体、基因、种群、适应度、选择、交叉、变异等在遗传算法中仍然被使用。MinF(X)=X2-19X+20,其中X=1,…,64之间的整数。4.3.2遗传算法—仿生学算法的简单示例2）一个简单示例遗传算法的基本思想染色体：可能解的基因型，是X的二进制编码，由于X取1…64之间的整数，因此用6个二进制位基因型，(X)10=(b6b5b4b3b2b1)2，

基因座的位置排序可从左到右编排，b6为位置1，b1为位置6。其中等位基因

bi=0or1,i=1…6。个体：一个可能解的表现型，本例中为十进制的X。种群：若干可能解的集合。交叉：交配/杂交，是新可能解的一种形成方法，是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作。变异：新可能解的一种形成方法，是通过随机地改变一个可能解的编码的某些片段(或基因)而使一个可能解变为一新的可能解的遗传操作。适应度：可能解接近最优解的一个度量，本例直接用F(X)作为其适应度的度量，其值越小越接近最优解。选择：从种群(解集)中依据适应度按某种条件选择某些个体(可能解)。4.3.2遗传算法—仿生学算法的简单示例图4.18遗传算法的简单示意4.3.2遗传算法—仿生学算法的简单示例图4.19遗传算法的简要描述及设计要点4.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用例1“会议室”租用问题设某机构一天内要组织m次讲座，需要租用会议室。有n个会议室可被租用，由于不同会议室条件不同，会议室所适合的讲座约束如表4.2示意(1为适合，0为不适合)；一个会议室只要可能，尽可举办多次讲座，并且其费用是固定的(暂不考虑诸如多个讲座租用同一会议室的冲突，以及会议室举办讲座次数最大约束等细致问题)。问怎样租用会议室既能完成这m次讲座，而且费用又最低。4.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用会议室/机组成员/测试用例讲座/航班/功能X1X2X3X4X5X6T1

T2

T3

T4

T5

T6

001001010110010010100100101001010100费用Cj5002502504006004004.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用例2“航班机组成员”选择问题设某航空公司一天内有m个航班要执行，需要机组成员进行服务。有n个机组成员可服务这些航班，由于不同机组成员能力和其他限制条件的影响，机组成员能够服务的航班约束亦可如表4.2示意(1为适合服务，0为不适合服务)；机组成员只要可能，尽可执行多个航班，并且其费用是固定的(暂不考虑机组成员服务多航班的冲突，以及服务航班数最大约束等细致问题)。问怎样选择机组成员既能完成这m个航班的执行又使得所支付的服务费用最低。4.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用例3“软件测试用例”选择问题设某软件公司有软件需要测试：一共有m个功能需要测试，测试就需要用测试用例。而专门提供测试用例的某测试公司，可提供n个测试用例，每个测试用例可支持不同功能的测试，测试用例与功能之间的关系亦可如表4.2示意(1为支持，0为不支持)，测试公司按照测试用例进行收费。问怎样购买测试用例既能完成m个功能的测试又使得所花费在购买测试用例的费用最低。4.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用本质上3个例题属同类问题，即集覆盖问题(set-coveringproblem)对于一个m行n列的0-1矩阵，用最小的费用选择一些矩阵的列，使其能够覆盖所有的行。设向量x的元素xj=1表示列j被选中（费用cj>0），xj=0则表示其未被选中，其中j=1,…,n。集覆盖问题数学模型可以表示为：约束(2)保证每行至少被一列覆盖，约束(3)是完整性约束。如果所有费用系数cj都相等，则问题称作单一费用集覆盖问题(unicostset-coveringproblem)；如果约束(2)为等式约束，问题则转化为集划分问题(setpartitioningproblem)。4.3.2遗传算法—仿生学算法的简单示例2.遗传算法3）组合优化问题遗传算法的应用前面例1，例2和例3都可以被抽象成上述的m行n列的集覆盖问题，第j列xj表示第j个资源，如会议室、机组成员或测试用例，而相应的第i行表示第i个任务，如讲座、航班或功能，问题的规模为m

n，即此为m

n规模的集覆盖问题。这种集覆盖问题是典型组合优化问题，Garey和Johnson在1979年证明了集覆盖问题属于NP-complete问题，可应用遗传算法进行求解。4.3.2遗传算法—仿生学算法的简单示例例4

“课程表”优化问题有8门课程需要安排教室，记为Li，i=1,…,8；有6个教室可被使用，记为Rj，j=1,…,6；不同教室大小不同，不同课程班人数也不同；要求每门课安排且只能安排一个教室，而每个教室安排最多只能安排两门课。以被利用教室利用率最高为原则，即假如教室的节次费用为k，则如该教室被占用，则其费用由k/课程班人数来衡量，所安排的课程班人数越多则费用越低，费用越低则教室利用率越高，k可依据教室最大容纳人数以及教室内的设施情况确定。教室与课程班之间的约束矩阵A如下表4.3给出，其中aij=1表示该课程班可以安排在该教室，aij=0则不可安排。4.3.3遗传算法暨问题求解算法的进一步探讨例4

“课程表”优化问题教室(最大人数)课程(选课人数)R1(100人)R2(50人)R3(多媒体)(50人)R4(80人)R5(多媒体)(100人)R6(多媒体)(80人)L1(85人)L2(40人)L3(95人)L4(60人)L5(45人)L6(90人)L7(76人)L8(56人)111111110100100001001000010110111111111101011011K100507080120100Cij=Kj/Li4.3.3遗传算法暨问题求解算法的进一步探讨例4

“课程表”优化问题本质上是8

6规模的集覆盖问题，其数学模型如下：式(2)表示每行要都被覆盖，说明为每门课程安排且只安排一个教室。式(3)表示能力限制，每个教室至多安排两门课程。4.3.3遗传算法暨问题求解算法的进一步探讨1）遗传算法为什么可以求解NP-Complete问题？理论上NP-Complete问题可通过枚举-验证的遍历算法来实现，即对解空间中的每个可能解都进行验证，直到所有解都被验证是否正确，便能得出精确解。但遍历整个解空间的计算量会随规模增大而迅速增长，被认为是不可行的。4.3.3遗传算法暨问题求解算法的进一步探讨1）遗传算法为什么可以求解NP-Complete问题？怎样不用遍历整个解空间，而搜索到满意的近似解呢？随机搜索方法利用随机数产生需要验证的若干个可能解，对其进行验证。这种方法是建立在概率论的基础上，所取随机点越多，则得到最优解的概率也就越大，然计算量也会增大。4.3.3遗传算法暨问题求解算法的进一步探讨1）遗传算法为什么可以求解NP-Complete问题？怎么改进“随机点”的选取方法呢？采取导向性随机搜索即对随机点的选取进行导向(导向到接近最优解的方向或路径)使随机点之间有了某种联系，或者说某种记忆，虽然随机但却是向接近最优解的方向在努力这可能比完全随机搜索得到的近似解的满意度要好。4.3.3遗传算法暨问题求解算法的进一步探讨1）遗传算法为什么可以求解NP-Complete问题？一条路径的导向性随机搜索VS.多条路径的导向性随机搜索并行

遗传算法可被认为是这样一种导向性群(体)随机搜索算法。它通过在初始种群上，随机地进行选择、交叉、变异，形成了多个搜索路径，而这样的搜索路径再通过计算个体解的适应度并进行评价选择使其导向到接近最优解的方向。4.3.3遗传算法暨问题求解算法的进一步探讨1）遗传算法为什么可以求解NP-Complete问题？对于NP问题，当没有其他更好算法可使用时，可选择遗传算法。只需要知道“解空间”，即可能解的表现型和基因型，以及关于可能解的“适应度”函数的计算方法(适应度用于判断一个可能解接近精确解的程度或方向)，就可以使用遗传算法。遗传算法提供了一种求解复杂系统问题的通用框架。4.3.3

遗传算法暨问题求解算法的进一步探讨2）可能解的染色体编码问题假设一个问题的解的形式为x，由x的取值空间或定义域给定的任何一个x值被称为可能解而一个问题通常有很多个关于可能解的约束，即不是任何一个x值都满足约束，我们可将满足问题约束的那些x值称为可行解而由一个算法在任何一组可行解中求出的最优解被称为是近似解而符合用户期望的近似解被称为是满意解所有可行解中的最优解是问题的最优解。“可能解集合”

“可行解集合”

“近似解集合”

“满意解集合”

“最优解集合”4.3.3

遗传算法暨问题求解算法的进一步探讨2）可能解的染色体编码问题可能解的染色体编码设计原则：尽可能利用问题的约束降低可能解集合或可能解空间的大小例1-例3可能解的表现形式是一n个元素构成的列向量x=<x1,x2,…,xn>例4

可能解的表现形式是二维矩阵x，需要给出每门课程和教室间的安排4.3.3

遗传算法暨问题求解算法的进一步探讨4.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题交叉操作是遗传算法产生可能解的主要手段，它通过把两个父代个体的部分结构加以替换重组而产生新的个体。不同的交叉策略两段交叉，一个染色体被分成两段，两个染色体的同位置段进行交叉重组多段交叉，一个染色体被分成多段，两个染色体的同位置段进行交叉重组4.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题交叉操作需要考虑的关键点：(1)种群中个体的配对分组问题，即哪两个个体进行配对交叉；(2)两段交叉中交叉点位置的选择；(3)多段交叉中的交叉点距离的变化与不变，即两个或多个交叉点间等距离和不等距离的多段选择问题。可以看出，交叉组合产生新可能解的方式是变化多样的。4.3.3

遗传算法暨问题求解算法的进一步探讨4.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题例4的染色体编码，不论是行优先编码或列优先编码，都可有行交叉、列交叉、块交叉和点交叉。行交叉是指对两个染色体同位置的两个课程段基因进行交叉重组列交叉是指对不同段的相同位置的两个染色体的基因进行交换块交叉则是对两个染色体的任何位置的两个块基因进行交换点交叉则是对两个染色体按某一概率交换其位基因4.3.3

遗传算法暨问题求解算法的进一步探讨图4.23课程表问题的染色体编码示例4.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题交叉操作本质上是一种组合，其组合所形成的可能解空间依然是庞大的，难以确定性的遍历每个组合。基于概率的随机处理方法也是遗传算法的核心处理机制交叉概率：在一个群体中，个体被选择出进行交叉的概率交叉点的选择：可通过随机方式产生4.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题交叉操作I：点交叉设P1和P2表示两个n位的父代染色体，f(P1)和f(P2)分别表示两个父代的适应值，

表示子代染色体。点交叉操作如下： step1:i=1 step2:如果P1[i]=P2[i]，则C[i]=P1[i]=P2[i] step3:如果P1[i]

P2[i]，则 step3.1:以概率p=f(P1)/(f(P1)+f(P2))让C[i]:=P1[i] step3.2:以概率1-p让C[i]:=P2[i] step4:如果i=n，停止；否则i=i+1，返回step14.3.3

遗传算法暨问题求解算法的进一步探讨3）交叉、变异与随机处理遗传规则问题交叉操作II：行交叉

设P1和P2表示两个k*h位的父代染色体，其中k为每一段的位数，h为染色体的分段数目，f(P1)和f(P2)分别表示两个父代的适应值，C表示子代染色体。 step1:产生一个0至h-1的随机数x；

step2:如果P1[x*k+i]=P2[x*k+i]foralli=1,…,k，则不产生后