算法设计与分析

章节摘录

版权页：插图：学习目标：理解动态规划算法的概念；掌握动态规划算法的使用条件；掌握动态规划算法的步骤；理解备忘录方法与动态规划的差异。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都要作出决策，从而使整个过程达到最好的活动效果。因此，各个阶段决策确定后，组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程，就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是和时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，希望找到具有最优值的解。在比较基本的算法设计思想里，动态规划是比较难于理解的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。具体的动态规划算法多种多样，但它们具有相同的填表格式。

书籍目录

第1章  算法概述1.1 算法的概念1.1.1 算法与程序1.1.2 算法与数据结构1.1.3 算法表示的基本方法1.1.4 算法设计1.2 算法复杂性分析的方法1.2.1 两个算法的效率对比1.2.2 算法复杂性的度量1.2.3 复杂性的渐近性态及其阶1.2.4 复杂性渐近阶的重要性1.2.5 递归方程解的渐近阶的求法小结习题第2章  分治与递归2.1 递归概述2.2 分治法概述2.3 分治法的应用2.3.1 排队购票问题2.3.2 整数划分问题2.3.3 "放苹果问题2.3.4 第后选择问题2.4 典型问题分析2.4.1 红与黑2.4.2 循环赛日程表2.4.3 0／1背包问题2.5 递归和递推2.5.1 递归和递推的比较2.5.2 "最少汽油过沙漠问题2.5.3 整数划分递推设计2.6 递归的消除小结习题第3章  贪心算法3.1 贪心算法概述3.2 活动安排问题3.3 背包问题3.4 贪心算法的两个基本要素3.4.1 贪心选择性质3.4.2 最优子结构性质3.5 典型问题分析3.5.1 最优装载问题3.5.2 删数问题3.5.3 均分纸牌3.5.4 拦截导弹问题小结习题第4章  动态规划4.1 矩阵连乘问题4.2 凸多边形最优三角剖分4.3 最长公共子序列4.4 DNA序列比对4.5 0／1背包问题4.6 多段图问题4.7 数字三角形问题4.8 备忘录方法4.9 典型问题分析4.9.1 游船费问题4.9.2 航线设置4.9.3 复制书稿4.9.4 括号序列小结习题第5章  搜索算法5.1 问题解空间的分析5.1.1 两种常见的树形问题解空间5.1.2 解空间的两种搜索方式5.2 回溯法概述5.3 分支限界法概述5.4 装载问题5.4.1 回溯法解装载问题5.4.2 分支限界法解装载问题5.5 0／1背包问题5.5.1 回溯法解0／1背包问题5.5.2 分支限界法解0／1背包问题5.6 旅行售货员问题5.6.1 回溯法解旅行售货员问题5.6.2 分支限界法解旅行售货员问题5.7 典型问题分析5.7.1 子集和问题5.7.2 油田勘探问题小结习题第6章  网络流和匹配6.1 最大流问题6.1.1 概念6.1.2 基本定理6.1.3 求最大流的标号法6.2 最小费用流问题6.3 匹配6.3.1 二部图6.3.2 匹配6.4 典型问题分析6.4.1 物流运输6.4.2 电力网络6.4.3 选择课程6.4.4 小行星小结习题第7章  线性规划7.1 线性规划问题及其表示7.2 线性规划问题的数学形式7.3 一般问题转化为约束标准型7.4 线性规划的基、基础可行解7.5 单纯形法算法7.5.1 用消元法描述单纯形法算法7.5.2 单纯形算法的框架7.6 线性规划应用小结习题参考文献

编辑推荐

《算法设计与分析》采用面向对象的c++语言作为算法描述手段，在保持c++优点的同时，尽量使算法描述简明、清晰。在《算法设计与分析》各章的论述中，首先分析一种算法设计策略的基本思想，然后从解决实际问题人手，由易到难地描述几个经典的实例，使读者既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本思想，以便收到融会贯通之效。同时，《算法设计与分析》特别注重对解同一个问题的不同算法的比较，使读者更容易体会到每一种具体算法的设计要点和各自的优缺点。

作者简介

《算法设计与分析》为大学计算机相关专业核心课程——“算法设计与分析”教材。全书以算法设计策略为知识单元，系统介绍算法设计方法与分析技巧，主要内容包括：算法概述、分治与递归、贪心算法、动态规划、搜索算法、网络流和匹配、线性规划。在介绍每一种方法时，阐述了它的应用背景，并注意与其他方法的比较。

《算法设计与分析》结构简明、内容丰富，为突出教材的可读性和可用性，章内设有典型例题分析，章末配有难易适度的习题，有利于读者对相关内容的理解。《算法设计与分析》适合于作为大学计算机科学与技术专业、软件工程专业及相关专业本科生和研究生教材，也适合广大工程技术人员学习参考。

图书封面

---

 算法设计与分析下载

---