算法精粹

本书是一本面向中高级程序员的算法教程，借助Java语言，用经典的算法、编码技术和原理来求解计算机科学的一些经典问题。全书共10章，讲述了常见的搜索算法、常见的图算法、遗传算法、k均值聚类算法、简单的神经网络、对抗搜索算法等，通过丰富的方案、示例和习题展开具体实践。本书将计算机科学与应用程序、数据、性能等现实问题深度关联，定位独特，示例经典，可以帮助程序员提升用Java解决实际问题的技术、编程和应用能力。

DAVID KOPEC 是费蒙特州伯灵顿大学香普兰学院计算机科学与创新专业的副教授。他的著作有《Classic Computer Science Problems in Python*》 (Manning, 2019),《 Classic Computer Science Problems in Swift》 (Manning, 2018) 以及 《Dart for Absolute Beginners》 (Apress, 2014) 。他还是一名软件开发和播客。

适读人群 ：中高级程序员
无论何种软件开发问题，都有可能已经有了解决方案。本书收集了非常有用的解决方案，可以指导你学习那些经过千锤百炼的解决问题的技术。本书介绍的原则和算法可以保证你在一个又一个的项目中节省大量的时间。
本书包含50多个练习，这些练习是多年来一直在计算机科学课堂中使用的。你可以通过实践这些例子来探索核心算法、约束问题、人工智能应用等。

本书主要内容包括：
递归、记忆化和位操作。
搜索、图和遗传算法。
约束满足问题。
k均值聚类、神经网络和对抗搜索。

20年来，Java已经成为世界上非常流行的编程语言之一。可以说，它已经成为企业、高等教育以及Android应用程序开发中的主导语言。通过本书，我希望能够引领大家意识到Java不仅仅是实现最终目标的一种手段，还是解决计算问题的一种工具。本书中的问题能够帮助老练的程序员在学习某些编程语言高级特性的同时，反思之前学过的计算机科学课程内容并有新的收获。使用Java的在校生和自学型程序员都可以通过学习普遍适用的问题求解技术来加速计算机科学课程的学习进度。本书涵盖了各种各样的问题，因此所有人都能从中受益。
本书不是Java的一般性介绍书籍，因此不适合Java新手阅读，而是面向中高级Java程序员。虽然本书使用的是Java 11中的特性，但并不需要你精通该版本的所有内容。
如果说计算机之于计算机科学就像望远镜之于天文学，那么编程语言就像望远镜的镜头。总之，经典计算机科学问题在这里表示“通常在本科计算机科学课程中教授的编程问题”。无论是在本科的课堂（计算机科学、软件工程等）上，还是在中级编程课本（例如，关于人工智能或算法的入门书）中，有些交给新手程序员解决的特定编程问题已经变得司空见惯了，以至于可以被视为经典。从简单的只需寥寥数行代码就能够解决的问题，到复杂的需要跨多个章节来构建系统的问题，这些问题范围很广。有些问题涉及人工智能，有些问题仅涉及常识，有些问题是实际存在的，而有些问题是虚构的。
本书面向的读者
Java被广泛应用于移动应用程序开发、企业网站开发、计算机科学教育、金融软件等领域。有时，人们批评Java过于冗长且缺乏某些现代特性，但是自从Java诞生以来，它可能比其他任何一种编程语言都更影响人们的生活。Java能够流行必定是有其原因的。Java最初被其创造者James Gosling描绘成更好的C++，这种语言能够提供面向对象编程的能力，同时引入安全特性并简化了C++中一些令人沮丧的问题。在我看来，Java在这方面取得了巨大的成功。
Java是一种非常棒的通用面向对象语言。然而，许多人开始觉得它刻板乏味，无论是Android开发人员还是企业网站开发人员，他们在使用这种语言的大部分时间里感觉就只是在“调用API”。他们把大量时间花在学习SDK或者库的细枝末节上，而不是去解决有趣的问题。本书旨在为这些程序员提供可以缓解这种状况的途径。还有一些程序员，他们从来没有接受过计算机科学相关课程的教育，而这些课程能够教会他们所有能够用来解决问题的强大技术。如果你是只会Java但是不懂计算机科学课程内容的程序员的话，那么这本书非常适合你。
还有一些程序员在从事软件开发工作很长一段时间后，会把Java作为第二、第三、第四甚至第五种语言来学习。对于他们来说，这些已经在其他语言中遇到过的老问题有助于加快对Java的学习速度。本书可以作为他们求职面试前很好的复习材料，为他们揭示一些以前在工作中没有考虑过的问题求解技巧。
本书适合中级和富有经验的程序员阅读。想要加深对Java知识理解的老练程序员，可以发现本书中提到的很多问题似曾相识，在之前上过的计算机科学或者编程课程上都遇到过。中级程序员可以通过他们熟悉的Java语言来学习这些经典的问题。准备进行编程面试的开发人员会发现本书是非常有价值的复习材料。
除了专业程序员，本书对于对Java感兴趣的计算机科学本科生来说也会很有帮助。本书没有对数据结构和算法进行严谨的介绍。这不是一本关于数据结构和算法的教材。你不会在本书中看到证明或者大量使用大O符号的情况。相反，它被定位为关于问题求解技术的入门实践指南，仿佛是数据结构、算法和人工智能课程融合的产物。
再次强调一下，本书需要你具备Java语法和语义的相关知识。没有编程经验的读者无法从本书中受益，而不具备Java经验的程序员也势必会陷入苦战。换句话说，本书是一本面向Java程序员和计算机科学专业学生的书。
本书的结构：路线图
第1章介绍大多数读者可能已经熟知的问题求解技术。像递归、记忆化和位运算这类内容是后续章节讨论其他技术的基础。
第2章重点介绍搜索问题。搜索是一个非常大的主题，本书中的大部分问题都可以归到这个主题下。本章介绍最基本的搜索算法，包括二分搜索、深度优先搜索、广度优先搜索和A*搜索。
第3章介绍如何建立一个框架来解决广泛的问题。这些问题可以用相互之间受到约束的有限领域变量来进行抽象，包括经典的八皇后问题、澳大利亚地图着色问题以及字谜问题。
第4章探索图算法。对于初学者来说，这些算法的适用范围非常广。本章将介绍如何构建图数据结构，然后使用它来解决几个经典的优化问题。
第5章探讨遗传算法，这种算法在不确定性上要比本书中的大多数算法大得多，但有时可以解决那些传统算法无法在合理的时间内解决的问题。
第6章介绍k均值聚类，这可能是本书中算法最具体的一章。这种聚类技术实现简单，易于理解，适用范围广。
第7章解释什么是神经网络，旨在让读者领略简单神经网络究竟是什么样子的。本章不会全面介绍这个令人兴奋而又不断发展的领域，而是介绍如何在不使用外

前　言
致　谢
第1章　一些小问题　1
1.1　斐波那契数列　1
1.1.1　第一次递归尝试　1
1.1.2　基线条件的运用　2
1.1.3　使用记忆化　4
1.1.4　简洁的斐波那契方法　5
1.1.5　使用流来生成斐波那
　契数列　6
1.2　简单的压缩算法　6
1.3　牢不可破的加密方案　10
1.3.1　按顺序获取数据　10
1.3.2　加密和解密　11
1.4　计算π　13
1.5　汉诺塔问题　14
1.5.1　对塔进行建模　15
1 5.2　求解汉诺塔问题　15
1.6　实际应用　17
1.7　习题　18
第2章　搜索问题　19
2.1　DNA搜索　19
2.1.1　存储DNA　19
2.1.2　线性搜索　21
2.1.3　二分搜索　22
2.1.4　通用示例　25
2.2　迷宫求解　26
2.2.1　生成随机迷宫　28
2.2.2　迷宫的其他方法　30
2.2.3　深度优先搜索　31
2.2.4　广度优先搜索　35
2.2.5　A*搜索　38
2.3　传教士和食人族问题　43
2.3.1　用代码来表达问题　44
2.3.2　求解　46
2.4　实际应用　48
2.5　习题　49
第3章　约束满足问题　50
3.1　构建约束满足问题的解决框架　51
3.2　澳大利亚地图着色问题　54
3.3　八皇后问题　57
3.4　单词搜索问题　59
3.5　字谜问题　65
3.6　电路板布局问题　66
3.7　实际应用　67
3.8　习题　67
第4章　图问题　68
4.1　地图是图的一种　68
4.2　搭建图的框架　70
4.3　查找最短路径　76
4.4　最小化网络构建成本　78
4.4.1　权重处理　78
4.4.2　查找最小生成树　82
4.5　在加权图中查找最短路径　87
4.6　实际应用　91
4.7　习题　92
第5章　遗传算法　93
5.1　生物学背景　93
5.2　通用遗传算法　94
5.3　简单测试　101
5.4　回顾字谜问题　103
5.5　优化列表压缩算法　107
5.6　遗传算法面临的挑战　110
5.7　实际应用　110
5.8　习题　111
第6章　k均值聚类　112
6.1　预备知识　112
6.2　k均值聚类算法　115
6.3　按年龄和经度对州长进行
　聚类　121
6.4　按长度对迈克尔·杰克逊的
　专辑进行聚类　125
6.5　k均值聚类算法问题及其
　扩展　127
6.6　实际应用　127
6.7　习题　128
第7章　简单神经网络　129
7.1　生物学基础　129
7.2　人工神经网络　131
7.2.1　神经元　131
7.2.2　层　132
7.2.3　反向传播　133
7.2.4　全貌　135
7.3　预备知识　136
7.3.1　点积　136
7.3.2　激活函数　137
7.4　构建神经网络　138
7.4.1　神经元的实现　138
7.4.2　层的实现　139
7.4.3　神经网络的实现　141
7.5　分类问题　144
7.5.1　数据的归一化　145
7.5.2　经典的鸢尾花数据集　146
7.5.3　葡萄酒的分类　150
7.6　加速神经网络　152
7.7　神经网络存在的问题及扩展　153
7.8　实际应用　154
7.9　习题　155
第8章　对抗搜索　156
8.1　棋盘游戏的基础组件　156
8.2　井字棋　158
8.2.1　井字棋的状态管理　158
8.2.2　极小化极大算法　161
8.2.3　用井字棋测试极小化
　极大算法　164
8.2.4　开发井字棋AI　166
8.3　四子棋　168
8.3.1　四子棋游戏程序　168
8.3.2　四子棋AI　174
8.3.3　用alpha-beta剪枝算法优化
　极小化极大算法　176
8.4　超越alpha-beta剪枝效果的
　极小化极大算法改进方案　177
8.5　实际应用　178
8.6　习题　179
第9章　其他问题　180
9.1　背包问题　180
9.2　旅行商问题　185
9.2.1　朴素解法　186
9.2.2　进阶　190
9.3　电话号码助记符　191
9.4　实际应用　194
9.5　习题　194
第10章　采访布赖恩·戈茨　195
附录A　术语表　206
附录B　更多资源　210