人工智能超入门丛书–搜索算法：人工智能如何寻觅最优

本书面向在人工智能方向零基础的读者，内容定位于专业知识入门和普及层面，全面系统，通俗易懂，让读者真正了解和理解人工智能的相关技术方向，而不仅仅是编程技术。 

“人工智能超入门丛书”致力于面向人工智能各技术方向零基础的读者，内容涉及数据素养、机器学习、视觉感知、情感分析、搜索算法、强化学习、知识图谱、专家系统等方向，体系完整、内容简洁、文字通俗，综合介绍人工智能相关知识，并辅以程序代码解决问题，使得零基础的读者快速入门。
《搜索算法：人工智能如何寻觅最优》是“人工智能超入门丛书”中的分册，本分册以通俗易懂的语言风格讲解了搜索算法的相关知识，内容包括算法问题中涉及的基本数据结构和复杂度分析，及状态空间、树、图等较复杂的数据结构；同时，通过相关实例，讲解了各类搜索方法及线性规划与非线性规划；也重点解读了组合优化问题和群智能算法。全书内容包含了搜索算法所能用到的核心方法和技术，另附三个附录，分别讲解了类与继承以及博弈基础等。本书搭配关键代码，是一本适合初学者阅读学习的人工智能（AI）图书。
本书可以作为人工智能及计算机相关工作岗位的技术人员的入门读物，也可以供高等院校人工智能及计算机专业的师生阅读参考，对搜索算法及人工智能方向感兴趣的人群也可以阅读。

无

第1章　搜索的世界 001
1.1　出“棋”不易 002
1.1.1　棋技，智力的象征？ 002
1.1.2　搜索＋评估=智能？ 006
1.1.3　AlphaGo是怎样炼成的？ 008
1.2　给盲目一些信息 011
1.2.1　盲目搜索 011
1.2.2　启发式搜索 013
1.2.3　博弈中前行 015
1.3　一切皆可优化 017
1.3.1　目标与约束 017
1.3.2　蒙特卡洛树搜索 021
1.3.3　群智能 024

第2章　基本数据结构与复杂度分析 030
2.1　数据关系与数据结构 031
2.1.1　数据关系 031
2.1.2　数据结构 032
2.2　栈与队列 033
2.2.1　栈 033
2.2.2　队列 038
2.2.3　双端队列 040
2.3　复杂度 042
2.3.1　衡量算法的效率 042
2.3.2　复杂度的分析 044

第3章　状态空间、树与图 050
3.1　状态空间 051
3.1.1　状态的表示 051
3.1.2　迷宫、汉诺塔与八数码 053
3.1.3　农夫过河 054
3.2　树 057
3.2.1　树的基本概念 057
3.2.2　二叉树 059
3.3　图 062
3.3.1　图的基本概念 062
3.3.2　图的存储方式 065

第4章　搜索技术 072
4.1　盲目搜索 073
4.1.1　广度优先搜索算法 073
4.1.2　深度优先搜索算法 080
4.2　启发式搜索 086
4.2.1　贪婪算法 086
4.2.2　A*算法 089
4.3　对抗搜索 093
4.3.1　博弈下的极小极大搜索 094
4.3.2　alpha–beta剪枝算法 102

第5章　线性与非线性规划中的搜索 105
5.1　优化问题 106
5.1.1　无处不在的优化 106
5.1.2　优化问题的描述 106
5.2　线性规划 108
5.2.1　图解线性规划 110
5.2.2　搜顶点 113
5.2.3　程序求解 114
5.3　非线性规划 117
5.3.1　从导数中获得搜索信息 117
5.3.2　非线性规划难在哪 124
5.3.3　程序求解 126

第6章　组合优化与求解 132
6.1　组合优化问题 133
6.1.1　旅行商问题 134
6.1.2　背包问题 138
6.2　模拟退火 140
6.2.1　基本原理 140
6.2.2　参数与流程 142
6.2.3　程序代码 144
6.3　禁忌搜索 149
6.3.1　基本原理 149
6.3.2　参数与流程 152
6.3.3　程序代码 155

第7章　群智能算法 160
7.1　遗传算法 161
7.1.1　基本原理 161
7.1.2　参数与流程 166
7.1.3　程序代码 171
7.2　蚁群算法 176
7.2.1　基本原理 176
7.2.2　参数与流程 180
7.2.3　程序代码 184
7.3　粒子群算法 189
7.3.1　基本原理 189
7.3.2　参数与流程 191
7.3.3　程序代码 196

附录  199
附录一　类与继承 200
附录二　人工智能的博弈基础 208
附录三　腾讯扣叮Python实验室：JupyterLab使用说明 214

新一代人工智能的崛起深刻影响着国际竞争格局，人工智能已经成为推动国家与人类社会发展的重大引擎。2017年，国务院发布《新一代人工智能发展规划》，其中明确指出：支持开展形式多样的人工智能科普活动，鼓励广大科技工作者投身人工智能知识的普及与推广，全面提高全社会对人工智能的整体认知和应用水平。实施全民智能教育项目，在中小学阶段设置人工智能相关课程，逐步推广编程教育，鼓励社会力量参与寓教于乐的编程教学软件、游戏的开发和推广。
为了贯彻落实《新一代人工智能发展规划》，国家有关部委相继颁布出台了一系列政策。截至2022年2月，全国共有440所高校设置了人工智能本科专业，387所高等职业教育（专科）学校设置了人工智能技术服务专业，一些高校甚至已经在积极探索人工智能跨学科的建设。在高中阶段，“人工智能初步”已经成为信息技术课程的选择性必修内容之一。在2022年实现“从0到1”突破的义务教育阶段信息科技课程标准中，明确要求在7～9年级需要学习“人工智能与智慧社会”相关内容，实际上，1～6年级阶段信息技术课程的不少内容也与人工智能关系密切，是学习人工智能的基础。
人工智能是一门具有高度交叉属性的学科，笔者认为其交叉性至少体现在三个方面：行业交叉、学科交叉、学派交叉。在大数据、算法、算力三驾马车的推动下，新一代人工智能已经逐步开始赋能各个行业。人工智能也在助力各学科的研究，近几年，《自然》等顶级刊物不断刊发人工智能赋能学科的文章，如人工智能推动数学、化学、生物、考古、设计、音乐以及美术等的发展。人工智能内部的学派也在不断交叉融合，像知名的AlphaGo，就是集三大主流学派优势，并且现在这种不同学派间取长补短的研究开展得如火如荼。总之，未来的学习、工作与生活中，人工智能赋能的身影将无处不在，因此掌握一定的人工智能知识与技能将大有裨益。
从笔者长期从事人工智能教学、研究经验来看，一些人对人工智能还存在一定的误区。比如将编程与人工智能直接画上了等号，又或是认为人工智能就只有深度学习等。实际上，人工智能的知识体系十分庞大，内容涵盖相当广泛，不但有逻辑推理、知识工程、搜索算法等相关内容，还涉及机器学习、深度学习以及强化学习等算法模型。当然，了解人工智能的起源与发展、人工智能的道德伦理对正确认识人工智能和树立正确的价值观也是十分必要的。
通过对人工智能及其相关知识的系统学习，可以培养数学思维（mathematicalthinking）、逻辑思维（reasoningthinking）、计算思维（computationalthinking）、艺术思维（artisticthinking）、创新思维（innovativethinking）与数据思维（datathinking），即MRCAID。然而遗憾的是，目前市场上既能较综合介绍人工智能相关知识，又能辅以程序代码解决问题，同时还能迅速入门的图书并不多见。因此笔者策划了本系列图书，以期实现体系内容较全、配合程序操练及上手简单方便等特点。
本书以搜索算法为主线，按照如下内容进行组织：第1章以棋局为引，介绍了搜索算法与智能、盲目搜索与启发式搜索以及优化的相关概念；第2章主要介绍算法问题中涉及的基本数据结构与复杂度分析等内容；第3章介绍了状态空间、树和图的一些基本知识；第4章围绕具体问题，分别介绍了广度优先搜索算法、深度优先搜索算法、启发式算法以及对抗搜索算法等内容；第5章着重介绍线性规划与非线性规划的内容，这些内容是学习人工智能，尤其是机器学习的重要基础之一；第6章引入模拟退火与禁忌搜索算法求解组合优化问题；第7章介绍了遗传算法、蚁群算法和粒子群算法是如何解决实际问题的案例，也让读者了解到群智能中的竞争、竞合与合作是如何演变成算法的过程。值得注意的是，第6章与第7章中大部分内容体现了人工智能跨学科的思想，读者可以从这两章的内容中感受到交叉学科解决问题的强大力量。本书的附录部分回顾了类、继承等相关概念，介绍了人工智能博弈基础的相关内容，同时还介绍了Python实验室JupyterLab的使用。
本书的出版要感谢曾提供热情指导与帮助的院士、教授、中小学教师等专家学者，也要感谢与笔者一起并肩参与写作的其他作者，同时还要感谢化学工业出版社编辑老师们的热情支持与一丝不苟的工作态度。
在本书的出版过程中，未来基因（北京）人工智能研究院、腾讯教育、阿里云、科大讯飞等机构给予了大力支持，在此一并表示感谢。
由于笔者水平有限，书中内容不可避免会存在疏漏，欢迎广大读者批评指正并提出宝贵的意见。

龚超
于清华大学