 书单推荐 新书推荐 |
算法设计与分析 
定 价：59.8 元
当前图书已被 2 所学校荐购过！
查看明细
9 7 2 8 9 7 8 3 0 0 1 3 3 
算法在计算机中扮演着重要角色，它对计算机科学的发展起着重要的推动作用。算法可以被看作解决问题的方法，尽管它不是问题的答案，但它是经过准确定义以获得答案的过程，因此特定的算法设计技术可以作为问题求解的有效策略，学习算法可以培养学生分析问题和解决问题的能力。本书主要内容包括算法效率的分析方法，算法工具STL的使用，蛮力法、递归法、分治法、贪心法、动态规划法、回溯法和分支限界法七个核心算法的原理与经典问题的解决对策，学生如果具备了本课程算法设计的基本方法，可进一步学习本课程的图的搜索算法、计算几何算法、随机算法三大专题深入学习。
《算法设计与分析》是一本集系统性、实用性、思想性于一体的优质书籍。无论你是初涉算法领域的新手，还是寻求突破的专业人士，都能从这本书中汲取知识的养分。希望大家能通过这本书开启算法学习的奇妙之旅，在计算机科学的天空中翱翔。
前言
教育是国之大计、党之大计。党的二十大报告明确提出， 坚待教育优先发展， 到
2035年建成教育强国， 首次将“实施科教兴国战略， 强化现代化建设人才支撑”作为一个
单独部分， 并把“教育、科技和人才”三者联系在一起加以论述、部署， 且有关教育的论
述出现在经济之后， 排在各项战略任务的第二位， 充分体现了教育的基础性、战略性地
位和作用。
随着大数据时代的到来， “ 数据挖掘”“人工智能”等与算法相关的词语已成为IT行业
流行的词汇。若想以最少的成本、最快的速度、最好的质量开发出适合各种应用需求的
软件， 就必须遵循软件工程的原则， 设计出高效率的程序。软件的效率和稳定性取决于
软件中所采用的算法， 然而， 程序设计的“灵魂”就是解决问题的算法。现阶段， 我国对
千算法方面的人才需求与H俱增， 为了满足这一需求， 培养出优秀的软件研究与设计人
才， 绝大多数高校的计算机及相关专业开设了＂算法设计与分析“课程， 它早已成为计算
机科学与技术、智能科学与技术、软件工程、人工智能等本科专业的核心课程。
为了适应“新工科“背泉下计算机相关专业算法类课程的教学模式及我国计算机各类
人才的需要， 本书以算法设计策略为主线， 系统地介绍了计算机算法的设计方法与分析
技巧， 以期为计算机学科的学生提供广泛而坚实的计算机算法基础知识， 提升学生的算
法设计能力、综合应用能力和创新能力， 立足培养学生跟上国际计算机科学技术的发展
水平。
本书对各类算法的介绍深入浅出、通俗易懂， 注重理论与实践相结合。为了适应高
等院校的人才培养模式， 本书各章均配套相关的实验内容， 以增强学生学有所得和学有
所用的体验， 激发学生学习算法设计相关知识的兴趣。在学习本书之前， 学生已经学习
了基本的数据结构知识， 能熟练运用一门或多门编程语言， 并具备了一定的编程经验。
让学生能够利用巳学过的知识针对不同的实际问题设计出有效的算法， 是本书所要达到
的目的。本书的特点是“问题模型化， 求解算法化， 设计最优化”。
1. 本书内容
全书共10章， 各章的内容如下。
第1章为算法设计与分析基础， 主要介绍算法、算法设计、算法分析的基本概念， 以
及常见重要问题的类型和常用算法的设计方法。
第2章为算法工具STL, 主要介绍标准模板库STL, STL是C+＋程序员必须掌握
的模板库， 掌握它对提升C+＋编程大有益处。
第3章为蛮力法， 介绍了蛮力法的概念与特点， 讨论了运用蛮力策略解决几类常见排
序问题的设计思想， 并介绍了与蛮力法相关的儿个经典问题。
第4章为递归与分治法， 介绍了递归技术和分治法的基本思想， 递归设计实例， 以及分治法在二分查找、归并排序、快速排序、堆排序、棋盘覆盖、最大子段和等问题中的应用。这是设计有效算法最常用的策略之一，是必须掌握的方法。
第5章为贪心法，介绍了贪心法的基本思想，以及贪心法在经典问题中的应用，这是一种非常重要的算法设计策略，其计算效率很高。按贪心法设计出的许多算法能得出最优解，其中有许多典型问题和典型算法可供学生学习和使用。
第6章为动态规划法，介绍了动态规划的原理和求解步骤，讨论了采用动态规划法求解斐波那契数列、排队买票问题、凑硬币问题、数字塔问题、最长公共子序列问题、流水作业调度问题、资源分配问题、最短路径问题等经典问题的算法设计。
第7章为回溯法与分支限界法，介绍了问题的解空间的概念和回溯法与分支限界法的基本思想，讨论了回溯法与分支限界法的异同，并对比了这两种算法在0/1背包问题、旅行商问题等经典问题中的应用。
第8章为图的搜索算法，在前7章讨论过的算法设计方法的基础上设计了有效的图的搜索算法，探讨了儿个基本应用问题，并介绍了网络流的相关概念以及求最大流、割集与割量、求最小费用最大流的算法。
第9章为计算几何算法，介绍了计算几何中常用的向量运算以及求解凸包问题、最近点对问题和最远点对问题的典型算法。
第10章为随机算法，主要讨论了蒙特卡罗算法、舍伍德算法和拉斯维加斯算法3类随机算法的应用。
2.本书特色
(1)课程思政融入教学
本课程要求学生具备算法设计与分析技能的同时，更关注大学生的心理健康问题。
本书配套的电子资料包含大量教学案例，引导学生树立正确的价值观和人生观，激发学
生科技报国的历史担当，自觉抵制外界的一些负面影响和诱惑，帮助学生把精力集中到
学习科学知识的主业中，培养学生具备精益求精的工匠精神、科技报国的使命担当，以
及坚定“ 四个自信＂的爱国主义精神。本课程的主讲教师应秉承创新精神、匠心精神，与
时俱进地不断完善和提升课程质屈，力争为祖国培养更多德才兼备的青年才俊，为教学
改革贡献自己的力量。
(2)编程语言之间的共性与个性的比较
本书的核心语言是C 语言，第3～第7章中核心算法的经典问题的代码采用了C、
C+ ＋语言同时实现(Java的完整实现代码扫二维码可以查阅），同一个算法使用多种语言
进行编写、对比和分析，能提高学生的综合能力。本书是一本既能让学生清晰、轻松地
理解算法思想，又能让学生编程实现算法的实用书籍。
(3)由浅入深，循序渐进
每种算法策略从设计思想、算法框架入手，巾易到难地讲解经典问题的求解过程，
使读者既能学到求解问题的方法，又能通过对算法策略的反复应用掌握其核心原理，以
达到融会贯通之效。
，． 急尸··`·
＇ ， ! 2 ;
鱼
． ....,
}，
(4)注重问题导向的学习内容设计
本书将各种算法应用于多个有趣的现实问题的解决过程中，以问题为导向来促进学生思考并体会算法的精妙之处与用途， 进而提升其学习效果。
(5)注重求解问题的多维性
同一个问题可采用多种算法策略实现， 如0/1背包问题分别采用回溯法、分支限界法
和动态规划法求解。通过不同算法策略的比较， 使学生更容易体会到每一种算法策略的
设计特点和优缺点， 以提高其算法设计的效率。
(6)配套资源丰富
为了加深学生对知识的理解， 各章配有难易适当的习题、实验题， 以适应不同程度
的学生练习的需要。本书还配套有教学计划、教学大纲、PPT课件、教材源代码、实验
源代码等丰富的教学资源供教师授课使用。
3. 结束语
本书由兰州财经大学高丽伟、杨海军， 贵州大学薛现斌共同编著而成。其中， 高丽
伟编写了第4、第5、第6、第7、第10章；杨海军编写了第2、第9章， 并完成了本书图
片的绘制和校正工作；薛现斌编写了第1、第3、第8章， 并负责全书代码的测试和校正
工作。
本书是课程组全休教师多年教学经验的总结和体现， 在编写过程中， 编者参考了很
多同行的教材和网络博客。由千编者水平有限， 书中疏漏在所难免， 故殷切希望广大读
者及同行专家、教师能够批评指正， 以便修改完善。编者E-mail为glwdz324@163.com 。
编者
2024年9月
.......
高丽伟，本硕毕业于贵州大学计算机专业，已有8年教龄，一直为计算机科学与技术、智能科学与技术、电子商务等本科专业讲授算法设计与分析课程，对于该教材积累了一定的教学和编写经验。
目录
第1 章算法设计与分析基础．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1
1. 1 算法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． l
1. 1. 1 什么是算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 1
1. 1. 2 学习算法的重要性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7
1.2 问题的求解过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8
1. 2. 1 问题及问题的求解过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8
1. 2. 2 算法设计与算法表示．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9
1. 2. 3 算法确认和算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 10
1. 3 数学基础．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 13
1. 3. 1 函数的渐近的界．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 14
1. 3. 2 利用极限求函数的渐近的界．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．．17
1. 3. 3 常用的求和级数及推导方法…………………………………………… 19
1. 3. 4 基本渐近效率类型．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 21
1. 4 算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2 2
1. 4. 1 算法的时间复杂度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 22
1. 4. 2 算法的空间复杂度分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 28
1. 4. 3 非递归算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 29
1. 4. 4 递归算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 30
1.5 关千P类、NP类和NPC类问题……………………………………… ……… 33
1. 6 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 34
1. 7 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 35
1.8 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 36
第2章算法工具STL ················································································· 38
2. 1 STL概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 38
2. 1. 1 什么是STL容器.................................................................. 39
2. 1. 2 什么是STL算法.................................................................. 39
2. 1. 3 什么是STL迭代器............................................................... 40
2. 2 常用的STL容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41
2. 2. 1 顺序容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 41
2.2. 2 关联容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 49
2. 2. 3 适配器容器．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 52
2. 3 STL在算法设计中的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 55
2.4 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 67
2. 5 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 68
2. 6 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 69
第3章蛮力法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1 蛮力法概述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1. 1 蛮力法的基本思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 72
3. 1. 2 蛮力法解题格式．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 75
3. 2 蛮力法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 83
3. 2. 1 百钱百鸡问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 84
3. 2. 2 狱吏问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 85
3. 2. 3 顺序查找．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 88
3.2.4 简单排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 89
3. 2. 5 求解幕集问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 95
3. 2. 6 求解0/1 背包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 98
3. 2. 7 求解最大连续子序列和问题………………………………………… 102
3. 3 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 104
3. 4 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105
3. 5 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 105
第4章递归与分治法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108
，． 急尸··`·
＇ ， ! 2 ; 鱼
． ....,
}，
4. 1 递归算法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 108
4. 1. 1 递归算法的特性．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 109
4. 1. 2 递归算法的执行过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 110
4. 1. 3 递归适用场合．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 112
4. 2 递归设计实例．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117
4. 2. 1 几个简单的递归程序．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 117
4.2.2 排序问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 119
4.2.3 斐波那契数列问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 121
4. 2. 4 n皇后问题........................................................................ 123
4. 2. 5 汉诺塔问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 125
4. 3 分治法的思想化整为零．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 127
4. 4 分治法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129
4. 4. 1 二分查找算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 129
4. 4. 2 归并排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 131
4. 4. 3 快速排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 134
4. 4. 4 堆排序算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 136
4. 4. 5 棋盘覆盖问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 139
4. 4. 6 最大子段和问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 142
4. 5 本章小结．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 144
4. 6 习题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 145
4. 7 实验题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 145
第5 章贪心法．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148
5. 1 贪心法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 148
5. 1. 1 问题的提出．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 148
5. 1. 2 贪心法设计思想．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 150
5. 1. 3 贪心法的基本要素．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 150
5. 1. 4 贪心法的求解过程．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 151
5. 2 贪心法的应用．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．． 152
5. 2. 1 活动安排问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 152
5. 2. 2 币种统计问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 159
5. 2. 3 背包问题．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 160
5. 2. 4 多机调度问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 163
5. 2. 5 哈夫曼编码．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 165
5. 2. 6 最小生成树．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 172
5. 2. 7 求解流水作业调度问题．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 178
5. 2. 8 求解川忌赛马问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 182
5. 3 本章小结．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 185
5. 4 习题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．． ．．．．．．．．．．．． ．．．．．．．．．．．．．．． 186
5. 5 实验题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 187
第6 章动态规划法．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190
6. 1 动态规划法概述．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 190
6. 1. 1 动态规划法的基本思想．．． ．．．．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． 190
6. 1. 2 动态规划的设计技术．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 192
6. 2 最优决策表．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．．．．．．．．．．． 195
6.2. 1 0/1 背包问题．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 196
6.2. 2 0/1 背包的相关问题．．．．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 200
6. 3 动态规划法的应用．．． ．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．． ．．．．．．．．． 202
6. 3. 1 斐波那契数列．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 202
6. 3. 2 排队买票问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 203
6. 3. 3 凑硬币问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 204
6. 3. 4 数字塔问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．． ．．．．．． ．．．．．．．．．．．． ．．． ．．．．．． ．．． 207
6. 3. 5 最长公共子序列问题．．． ．．． ．．．．．．．．．．．．．．．．．．．．． ．．． ．．．．．． ．．．．．． ．．． ．．． ．．．．．． ．．． 211
6. 3. 6 流水作业调度问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．． ．．． ．．．．．． ．．．．．． ．．．．．．．．．．．． ．．． 214
6. 3. 7 资源分配问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 217
6. 3. 8 最短路径问题．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．． ．．．．．． ．．． ．．． ．．．．．． ．．．．．．．．． ．．． 220
6. 4 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225
6. 5 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 225
6. 6 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 227
第7 章回溯法与分支限界法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233
7. 1 回溯法的设计技术．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 233
7. 1. 1 回溯法的算法思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 234
7. 1. 2 回溯法的算法框架．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 236
7. 1. 3 回溯法的适用条件．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 239
7. 2 回溯法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 243
7. 2. 1 0/1 背包问题..................................................................... 243
7. 2. 2 n皇后问题........................................................................ 248
7.2.3 旅行商问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 250
7.2.4 图的m着色问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 253
7. 2. 5 求解子集和问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 255
7. 3 分支限界法的设计技术．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258
7. 3. 1 分支限界法的思想．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 258
7. 3. 2 分支限界法与回溯法对比．．．．．． ．．． ．．． ．．．．．．．．．．．．．．．．．． ．．．．．． ．．．．．． ．．．．．．．．． 258
7. 3. 3 分支限界法解决的关键问题………………………………………… 259
7. 3.4 分支限界法的时间性能．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4 分支限界法的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4. 1 0/1 背包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 262
7. 4. 2 旅行商问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 269
7. 5 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 282
7. 6 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 283
7. 7 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 284
第8 章图的搜索算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
，． 急尸··`·
＇ ， ! 4 ;
鱼
． ....,
}，
8. 1 广度优先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
8. 1. 1 算法描述与分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 288
8. 1. 2 程序实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 292
8. 2 深度优先搜索．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297
8. 2. 1 算法描述与分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 297
8.2.2 程序实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 299
8. 3 有向图的强连通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 303
8. 4 无向图的双连通分支．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 307
8. 5 网络流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310
8. 5. 1 相关概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 310
8. 5. 2 求最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 312
8. 5. 3 割集与割量．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 316
8. 5. 4 求最小费用最大流．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 317
8. 6 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2
8. 7 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 32 2
8. 8 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 323
第9 章计算几何算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327
9. 1 线段的性质．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 327
9. 2 向量运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 328
9. 2. 1 向扯加减运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 329
9. 2. 2 向批点积运算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 330
9. 3 叉积．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331
9. 3. 1 叉积的计算．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 331
9. 3. 2 判断相继两直线段左转或右转……………………………………… 332
9. 3. 3 两个点的距离．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333
9. 3. 4 点到线段的距离．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 333
9. 4 线段的应用．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 334
9.4. 1 判断一个点是否在一个矩形内……………………………………… 334
9.4. 2 判断一个点是否在一条线段上……………………………………… 335
9.4. 3 判断两条线段是否平行．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 335
9.4. 4 判断两条线段是否相交．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 336
9.4. 5 判断一个点是否在多边形内………………………………………… 336
9.4. 6 求3 个点构成的三角形面积………………………………………… 338
9.4. 7 求一个多边形的面积．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 338
9. 5 求解凸包问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 340
9. 5. 1 卷包裹算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 341
9. 5. 2 葛立恒扫描法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 342
9. 6 求解最近点对问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 344
9. 7 求解最远点对问题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 349
9. 8 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 352
9. 9 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353
9. 10 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 353
第10 章随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356
10.] 同余的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 356
10. 2 随机数．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 358
10. 3 随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10. 3. 1 随机算法的概念．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10. 3. 2 随机算法的分类．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 360
10.4 经典随机算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361
10. 4. 1 蒙特卡罗算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 361
10. 4. 2 舍伍德算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 362
10. 4. 3 拉斯维加斯算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 364
10. 5 本章小结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366
10. 6 习题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 366
10. 7 实验题．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 367
参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 368
，． 急尸··`· {
气.6)
皇后问题、图的m着色问题和装载问题等。组合优化问题就是找到该问题的一个或全部最优解，如背包问题、子集和数问题及货郎问题等。
你还可能感兴趣
我要评论
|
