算法设计、分析与实现从入门到精通 C、C++和JAVA

算法设计、分析与实现是一门学问，那就从入门到精通，拿 C、C++和JAVA练手算法设计、分析与实现从入门到精通c、C++和Java人民邮电出版社北京前言算法作为数学的一个分支已经存在几百年了。然而,算法真正焕发青春得到长足的发展,还是发生在20世纪电子计算机发明的时代。随着计算机技术的广泛应用,人们越来越清楚地认识到,作为计算机科学与工程最主要的技术—程序设计,其灵魂就是解决问题的算法。能否提供一本既能让广大读者清晰、轻松地理解算法思想,又能为读者提供算法的程序实现各种关键技术建议的书是作者一个很长时间的思考。现在摆在读者面前的这本书,就是这一思考的结果。作者希望本书在读者研习算法与程序设计时不仅是书桌前或是床头边的参考书,更多的是计算机旁的参考书。夲书先按算法设计技巧分类为漸增型算法、递归分治算法、动态规划算法、贪婪算法、回溯算法和图的搜索算法等前6章。每章对2~3个经典问题针对一种算法设计技巧,给出解决问题的算法,并分析算法的时间复杂度。笔者认为,对于初学者来说,按算法的设计方法划分章节,算法思想的阐述比较集中,有利于入门。一旦具备了算法设计的基本方法,按应用领域划分专题深入学习,读者可以应用已学的方法综合起来解决比较复杂的问题。第7章的线性规划和第8章的计算几何可以算作这部分内容。在此基础上,读者可以更进一步擦讨更前沿的随机算法、近似算法和并行算法等现代算法设计方法。本书之所以按照这样的8章编排,还有一个重要原因是它们之间有一定的前后逻輯关系:第1章渐增型算法和第2章分治算法是最基本的算法,并且在这两章内容展开的同时我们还介绍了后面各章所需要的数据结构,例如第2章介绍的优先队列就是第4章讨论贪婪算法时所需要的。建议读者以本书的章节顺序研读,特别是实现的程序中也有很多是前后呼应的代码段。算法理论对于程序设计实践的指导意义已经被大家所接受,但不管是在校学生还是已踏上职业征程的程序员,很多人对算法学习都有一种“枯燥繁难”的先入之见。如何有效地学习算法的设计与分析,是本书试图与读者一起探讨的最重要的目标之一。其实,算法都是针对具体问题的。对于要解决的问题进行深入理解与分析,是设计出正确有效的算法的前提。然而,“深入理解与分析”似乎是个模糊概念,怎样的“度”才能认为是对问題深入理解了呢?计算学科提出了一个非常重要的“标准”:简单地说.能够把一个问题输入与输出准确地提炼并表述出来,就可以认为是理解了这个问题。这样对问题的描述称为“问题的形式化描述”。一旦形式化地描述出了问题的输入与输出,也就能准确地把握住算法解决问题所需要的条件和所要达到的目标。换句话说,设计算法是要在间题的输入与输出之间架起一座通达的桥梁。本书以此为目标,无论是对正文中讨论的问题还是“动手做”题目中的问题或者是作为应用的CPC问题,我们都给出其形式化描述。有了问题的输入与输出的数据表示,运用人们的常识、数学知识和科学知识建立起从输人到输出之间的对应关系,这就是算法。算法可以用自然话言或是图形等工具加以描述,但要将算法作为计算机程厅的设计蓝图,则需要将其无歧义地表述出来。用伪代码表述算法是迄今为止人们所使用的最有效的方法。计算机程序设计语言当然也能做到无歧义地描述算法。事实上,市场上也有以某种具体的程序设计语言为描述工具的算法书籍,但这样的图书往往要面对一个两难问题:一方面,若要使具体语言描述的算法能直接运行,则必须做诸如变量声明、用该语言所提供的方式表示各种复杂的数学表达式以及其他操作等各种技术细节工作。这样就会大大降低算法描述的可读性,妨碍读者对算法思想本身的理解与接受。另一方面,如果为提高算法描述的可读性而省略上述的各种技术细节,则仍然回到伪代码描述的起点,让读者在实现程序时有隔靴抓痒的感觉。本书由 Thomas h, Cormen等编著的《算法导箅法设计、分析与实现从入门到精通:C、C++和Java论》介绍的伪代码规范来描述书中所论述的毎一个算法,使其清晰明了且易于转换成计算机程序。有了作为程序设计蓝图的算法为代码描述,本书对每一个经典算法,都给出了完整的CC++/Java的实现代码及测试程序。怎样把实现代码的一般性方法明明白白地告诉读者,让他们能从中得到一些写代码的方法论方面的启迪是笔者的孜孜以求。按笔者体会,根据算法写程序需要抓住3个重点:其一,根据算法所处理问题的输入输出以及语言本身的技术特点设计过程(函数或方法)的参数与返回值。包括参数个数、类型,返回值类型,等等。其二,需要考虑过程中所要用到的所有变量,包括局部量和全局量。其三,由于伪代码是在一个很高的抽象层面描述算法,所以在某些情形下要考虑充分利用语言的技术特性来实现关键的操作。本书中的所有程序源代码都已在 Java SDKI.6,2、gc344、g++344上调试并正确运行。读者只要建立相应的程序项目,并在项目中建立相应的文件,在文件中逐行输入代码,编译后一定能够运行应当说明的是,本书中所说的C代码,指的是纯粹的C代码,如 turbo C2.0这样的编译系统都能够编译的代码。建议读者自己创建项目、文件,录入代码,调试程序,体会算法思想,体验编程成功。本书虽然用3种语言分别实现每个算法,读者可独立地阅读其中一种语言的程序。如果读者阅读两种或两种以上语言的算法实现代码,那么从本书中还能体会出这3种语言各自的特点,也能悟出一些程序设计共通的基本方法和技术。本书收集了一些ICPC的题目(包括2007年中国赛区中几个分赛区一南京、北京、成都等的网赛题、场赛题和几个国际决赛题)来说明书中所介绍的经典算法的应用。有朋友建议我把这些题目翻译成中文,便于读者阅读理解。但是笔者非常赞同以下的观点:一个人接受科技教育得到的最大收获,是那些能够受用一生的一般性智能工具。而在这些工具中,最重要的是自然语言数学和计算机科学。英语作为自然语言,已成为 Internet语言。地球因为 nternet已成为一个“村”。用此“村言”阅读理解村中的问题(这些问题都凝结了各方文化习俗及拟题高人的智慧,读起来妙趣横生),设计出解决这些问题的算法,并将算法实现为能在计算机上运行的程序,得到问题的解,岂不是一大乐趣?著名的数学家华罗庚先生曾经说过,读数学书若不做习题似“人宝山而空返”。笔者以为先生的意思是说思想不经过实践检验,再好的理论和技能也难以掌握,难以应用。本书在每个经典问题算法的说明和实现后以及每个ICPC问题之后都留有“动手做”的题目,建议读者利用相关的算法及实现的方法来解决“动手做”中相似的问题。中国人将学习的过程分成4个境界:比、从、北、化。笔者理解“比”就是接受先辈留下的智慧,“从”就是跟随先辈的经验认识世界,“北”就是借鉴先辈的智慧和经验解决现在自己的问题,而“化”就是融合先辈和自己的经验产生新的知识,解决新的问题。我们把这4个境界缩小到算法学习的过程中:学习前人的算法设计思想,根据算法思想设计程序,利用程序解决问题,投身建设创新进取。源程序下载地址为www.ptpress.com.cn在本书写作的掩卷之时,我的内心充满了感激。感谢我的导师朱洪教授,早在5年前我在复且大学做国内访问学者时就为我提供了大量的资料,鼓励我写作,几年来给了我很多的指点和帮助,并不吝为本书撰写序言。感谢福建师范大学的陈志德博士、重庆工商大学的赖涵、韦一平杨艺、罗棼等老师对书稿的审阅。能够顺利出版成书还必须感谢人民邮电出版社的编辑对我的帮助和髙效率的编辑工作。最后,还要感谢我的夫人段泰然,没有她年复一年在生活中的关怀和容忍,不可能有这本书的顺利写作。笔者才疏学浅,算法书以这样的方式来写作是一种尝试,其中必有不当与错误,盼望学界同行与广大读者批评指正。联系邮箱为xuzishan@1630m或zhangtao@eptpress.com.cn作者2010年5月函数(方法)107第1章集腋成裘——渐增型算法-127,3应用—环法自行车赛。1081.1算法设计与分析-2.8小结--10912插人排序算法41.2.1算法描述与分析第3章记衰备查—动态规划122程序实现-·=“=.算法111123应用一一赢得舞伴.303.1矩阵链乘法--1213两个有序序列的合并算法323.1.1算法描述与分析1.3.1算法描述与分枥--323.1.2程序实现1.32程序实现--343.1.3应用——牛牛玩牌---12114序列的划分……-…-4532最长公共子序列----12314.1算法描述与分析-4532.1算法描述与分析1231.4.2程序实现-322程序实现一1265小结---52323算法的应用……132第2章化整为零—分治算法--53330-1背包问题1362.,1 Hanoi塔问题与递归算法53331算法描述与分析---136332程序实现-13821.1算法的描述与分析--53333算法的应用—1422.1,2程序实现5634带权有向图中任意两点间2.13应用—新Hano塔游戏.59的最短路径22归并排序算法144=========6234算法描述与分析1442,2,1算法描述与分析…-62342程序实现一--148222程序实现-------6334.3应用—牛牛聚会-153223应用—让舞伴更开心-693.5小结--1552.3快速排序算法2M算法描述与分析--70第4章高择一贪法1562.32程序实现4.1活动选择问题-----15624堆的实现-794.1.算法描述与分析---15241堆的概念及其创建--794.1.2程序实现-158242程序实现4.1.3贪婪算法与动态规划-1632.5堆排序84.14应用—一海岸雷达-1652.5.1算法描述与分析---8842 Huffman编码-----1662.52程序实现--42.』算法描述与分析1662.6基于二叉堆的优先队列--944.2.2程序实现-170261算法描述与分析--9442.3应用— Huffman树-1806,2程序实现-4.3最小生成树-1832.7关于排序算法-10543.算法描述与分析I83271比较型排序算法的时间4.32程序实现-187复杂度433应用——北方通信网-196272CC++/Java提供的排序44单源最短路径问题--197箅法设计、分析与实现从入门到精通:C、G++和Java44.1算法描述与分析-1976.5流网络与最大流问题---310442程序实现-6.5.l算法描述与分析--31044.3应用—西气东送--2076.52程序实现---3194.5小结2106.53应用--6小结324第5章艰苦卓绝一回溯算法-21151组合问题与回溯算法--211第7章集组合优化向题之大成一5.1.13-着色问题----211线性规划一3255.12n皇后问题21471标准形式与松弛形式--3285.13 Hamilton回路问题---2167.1.1线性规划的标准形式-3285.14子集和问题2187.1.2线性规划的松弛形式-3352解决组合问题的回溯算法72单纯形算法334框架219721单纯形算法的例子---33452.1算法框架722轴转操作33752.2程序实现72.3正规的单纯形算法-3405.3排列树和子集树--2357.3初始基本可行解……3473.1子集树问题74应用—将组合优化同题532排列树问题24l形式化为线性规划----35554用回溯算法解决组合优化7.5小结-世世世世世一一一出359问题24554.1算法框架245第8章图形学基础—计算54.2旅行商问题247几何3605.4.3应用2535.5P,NP和NP完全问题--26081线段的性质3605.6小结------2628.1.1叉积及其应用-3618.1,2程序实现364第6章田的搜索算法2648,2判断是否存在线段相交-3676.1广度优先搜索----265821算法描述与分析--3678,22程序实现-3706.1.1算法描述与分析26583求凸壳3742程序实现2686.1.3应用——攻城略地-27683.1 Graham扫描-----3756.2深度优先搜索832 Jarvis行进38127862.1算法描述与分析----27884求最邻近点对-----384622程序实现28084.1算法描述与分析385623有向无圈图的拓扑842程序实现排序85应用-----13892836.2.4应用—全排序-2908.51光导管一3896.3有向图的强连通分支--292852最小边界矩形63.1算法描述与分析8.53得克萨斯一日游39229263.2程序实现86小结m394--29563应用一亲情号30附录39564无向图的双连通分支3036算法描述与分析……303参考文献41064.2程序实现30664.3应用——離雄大盜08第章集腋成裘——渐增型算法11算法设计与分析1.什么是算法众所周知,算法是程序的灵魂。只有对需要解决的计算间题有一个正确的算法,才可能编写出解决此问题的程序。所谓算法就是解决一个计算问题的一系列计算步骤有序、合理的排列。对个具体问题(有确定的输入数据)依次执行一个正确的算法中的各操作步骤,最终将得到该问题的解。算法研究有着悠久的历史,内容极其丰富。人们对各种典型的问题研究出了很多经典的算法设计方法。例如,本书详细讨论的渐增型算法、分治算法、动态规划、贪婪策略和回溯算法等都是具有代表性的经典算法设计方法。对这些方法的学习,可以为我们在解决各种具体问题时设计出正确、高效的箅法提供有益的启示。2.算法分析基本概念解决一个问题,算法不必是唯一的。对表示问题的数据的不同组织方式〔数据结构),解决问题的不同策略(算法思想)将导致不同的算法。解决同一问题的不同算法,消耗的时间和空间资源量有所不同。算法运行所需要的计算机资源的量称为算法的复杂性。一般来说,解决同一问题的算法,需要的资源量越少,我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析,简称为算法分析。理论上,算法分析既要计算算法的时间复杂性,也要计算它的空间复杂性。然而,算法的运行时间都是消耗在数据处理上的,从这个意义上说,算法的空间复杂性不会超过时间复杂性。出于这个原因,人们多关注于算法的时间复杂性分析。本书中除非特别说明,所说的算法分析,仅局限于对算法的时间复杂性分析。为客观、科学地评估算法的时间复杂性,我们设置一台抽象的计算机,它只用一个处理机却有无限量的随机存储器。它的有限个基本操作——一算术运算、逻辑运算和数据的移动(比如对变量的赋值)均在有限固定时间内完成,我们进一步假定所有这些基本操作都消耗一个时间单位。算法设计、分析与实现从入门到精通:c、c++和Java称此抽象计算机为随机访问计算机,简记为RAM。算法在RAM上运行时所需的时间,显然就是执行基本操作的次数。不难看出,一个算法的时间复杂性与输入的规模相关,一般来说,规模越大,需要执行的基本操作就越多,当然运行时间就越长。此外,即使问题输入的规模一定,不同的输入,也会导致运行时间的不同。很多文献对一个算法的运行时间,研究如下的3种情形对固定的输入规模,使运算时间最长的输入所消耗的运行时间称为算法的最坏情形时间。对固定的输入规模,使运行时间最短的输人所消耗的时间,称为最好情形时间。●假定固定的输入规模为n,所有不同输入构成的集合为Dn,对问题的每一个输入为leDn若已知该输人发生的概率为P(D,对应的运行时间为T(D,运行时间的数学期望值∑ma.P(()称为算法的平均情形时间。3.实例我们用一个简单的实例来说明这些概念:考虑在输入的线性表A[中查找值为x的元素,若线性表中存在这样的元素,则輪出下标最小者,否则报告不存在信息。我们用下面的算法来解决这个问题:从A[]起逐一扫描线性表中元素,若表中存在这样的元素,返回第一个遇到的值等于x的元素A[的下标讠,否则,这个扫描过程将持续到表尾,报告无解信息,问题得以解决,如图1-1所示。A12345678910陌6104195128A12345678910x=-11360A12345678910x35604079523图1-1在线性表A中查找。(a)查找值为x=1的元素,从A[起依次要进行5次检测,第一次找到值为1的元素。(b)查找值为x=11的元素,从4起依次检测完所有元素(进行10次检测),没有找到值为11的元煮—最坏情形。(c)查找值为x-3的元素,从A[J起仅进行一次检测就找到值为3的元素—最好情形。这个算法对于无解输入(即输入的线性表A[1n中不存在值等于x的元素),所消耗的时间最长,因为它需要重复检测n次(也就是要做n次逻辑运算),所以最坏情形时间为n。当输入的线性表中第一个元素A[]值就等于x,则算法仅进行一次检测就可返回答案。这是最好的情形,所以该算法的最好情形时间为1。假定第一个值等于x的元素等概地分布在A[1.n中,也就是说第一个等于x的元素A[的下标i为1,2,…,n的概率均为1/。这样,我们的算法要进行i次检测的概率为1no所以算法的平均情形时间为:∑P(做改检测)i=∑=∑n(n+1)n+12显然,算法的最好情形时间是有“欺骗性”的,而平均情形时间的研究要用到概率统计的知集腋成裘——渐增型箅法第1章识。箅法最坏情形时间可视为算法对固定输入规模n的运行时间的上界,用它来表示算法的时间复杂性是合理的。本书若无特殊说明,就将算法的最坏情形时间称为算法的运行时阃。我们把算法的运行时间记为T,输入的规模记为n。则根据以上说明知T是n的递增函数,我们以T(n)来表示算法的运行时间。4.算法的渐进运行时间由于计算机技术不断地扩张其应用领域,所要解决的问题输入规模也越来越大,所以对固定的n来计算T(n)的意义并不大,我们更倾向于评估当n→∞时,T(n)趋于无穷大的快慢来分析算法的时间复杂性。我们往往用几个函数P(n):幂函数n4(k为正整数)、对数幂函数lghn(k为正整数,底数为2)和指数函数a”(a为大于1的常数)作为“标准”,研究极限:lim若非零常数,则称P(n)是T(n)的渐近表达式,或称T(n)渐近等于P(n),记为T(n)=e(P(n),这个记号称为算法运行时间的渐近1q-记号,简称为-记号。例如,T(n)=3n2+2n+1,由于lim=lim=1/3≠0n→nT(n)n→3n2+2n+1所以,有T(n)=e(n2),即此T(n)渐近等于n2。其实,在一个算法的运行时间r(n)中省略最高次项以外的所有项,且忽略最高次项的常数系数,就可得到它的渐近表达式回(F(n)用此方法也能得到3n2+2n+1=(n2)。5.有效算法如果两个算法运行时间的渐近表达式相同,则将它们视为具有相同时间复杂度的算法。显然,渐近时间为对数幂的算法优于渐近时间为幂函数的算法,而渐近时间为幂函数的算法则优于渐近时间为指数函数的算法。我们把渐近时间为幂函数的算法称为是具有多项式时间的算法,渐近时间不超过多项式的算法则称其为有效的算法。本书讨论的大多数问题都有解决它的有效算法,我们将在第5章讨论一些至今无法知道其是否有“有效的”算法的问题,并由此介绍算法研究的核心问题,也是计算机科学的核心问题—NP难问题一旦选择了算法,就需要运用一种合适的程序设计技术〔主要是程序设计语言)将算法实现为程序。利用计算机,运行这些程序帮助人们快速、正确地解决各种问题。本书旨在与读者一起分享从算法设计、分析到实现能运行的程序这一美妙的三部曲给我们带来的创造过程的快乐。6.渐增型算法我们从讨论一类最简单的算法设计技术—渐增型算法开始。所谓渐增型算法( incrementalalgorithms),指的是算法使得表示问题的解从较小的部分渐渐扩张,最终成长为完整解。渐增型算法有一个共同的特征:构成算法的主体是一个循环结构,它逐步将部分解扩张成一个完整解。该循环将遵循一个始终不变的原则:每次重复之初,总维持着问题的一个部分解。我们将此特征关于渐近记号的详细阐述请参见本书附录B