算法设计与分析

出版时间：2011-7  出版社：北京航空航天大学出版社  作者：任建华，王伟　主编  页数：260  

内容概要

本书系统地介绍了算法设计与分析的概念和方法，将计算机经典问题和算法设计技术很好地结合起来，系统地介绍了算法设计技术及其在经典问题中的应用。全书共11章，第1章介绍了算法的基本概念和基本理论，第2章从算法设计的角度介绍了算法设计与分析所用到的Java基础知识和数学方法，第3章～第9章分别介绍了递归与分治、动态规划、贪心法、回溯法、分支限界法、线性规划与网络流问题、概率算法等算法基本设计方法，第10章介绍了NP完全性理论，第11章讲述了近似算法。
书中对所有算法思想做了详细说明，给出了伪代码，大部分算法还给出了Java描述。本书内容丰富，深入浅出，结合实践，循序渐进，互相衔接，可作为高等院校计算机专业本科和研究生学习算法设计与分析的教材，也可供工程技术人员和自学读者学习参考。

书籍目录

第1章　算法基本概念
第2章　常用的Java基础和数学方法
第3章　递归与分治
第4章　动态规划
第5章　贪心算法
第6章　回溯法
第7章　分支限界法
第8章　线性规划与网络流问题
第9章　概率算法
第10章　NP完全性理论
第11章　近似算法
参考文献

章节摘录

　　完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。　　人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想：是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的“NP-P”的猜想。　　解决这个猜想，无非有两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为它们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的，那么就要从数学理论上证明它为什么不存在。　　前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好像是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。　　可以想到，人们思考问题时，有两种方法：一种是精确搜索，就是试验所有的可能性，找出最精确的一个方案。但它在搜索过程中不改变搜索策略，不利用搜索获得的中间信息，盲目性大，效率差，用于小型问题还可以，用于大型问题根本不可能；另一种叫做启发式搜索，它在搜索过程中加入了与问题有关的启发性信息，用以指导搜索向着一个比较小的范围内进行，加速获得结果。　　NP完全性问题属于“计算复杂性”研究的课题。所谓计算复杂性，就是用计算机求解问题的难易程度。　　……