本書講解了搜索算法的相關(guān)知識(shí)，內(nèi)容包括算法問(wèn)題中涉及的基本數(shù)據(jù)結(jié)構(gòu)和復(fù)雜度分析，及狀態(tài)空間、樹(shù)、圖等較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；同時(shí)，通過(guò)相關(guān)實(shí)例，講解了各類搜索方法及線性規(guī)劃與非線性規(guī)劃；也重點(diǎn)解讀了組合優(yōu)化問(wèn)題和群智能算法。全書內(nèi)容包含了搜索算法所能用到的核心方法和技術(shù)，另附三個(gè)附錄，分別講解了類與繼承以及博弈基礎(chǔ)等。
本書面向在人工智能方向零基礎(chǔ)的讀者，內(nèi)容定位于專業(yè)知識(shí)入門和普及層面，全面系統(tǒng)，通俗易懂，讓讀者真正了解和理解人工智能的相關(guān)技術(shù)方向，而不僅僅是編程技術(shù)。
新一代人工智能的崛起深刻影響著國(guó)際競(jìng)爭(zhēng)格局，人工智能已經(jīng)成為推動(dòng)國(guó)家與人類社會(huì)發(fā)展的重大引擎。2017年，國(guó)務(wù)院發(fā)布《新一代人工智能發(fā)展規(guī)劃》，其中明確指出：支持開(kāi)展形式多樣的人工智能科普活動(dòng)，鼓勵(lì)廣大科技工作者投身人工智能知識(shí)的普及與推廣，全面提高全社會(huì)對(duì)人工智能的整體認(rèn)知和應(yīng)用水平。實(shí)施全民智能教育項(xiàng)目，在中小學(xué)階段設(shè)置人工智能相關(guān)課程，逐步推廣編程教育，鼓勵(lì)社會(huì)力量參與寓教于樂(lè)的編程教學(xué)軟件、游戲的開(kāi)發(fā)和推廣。
為了貫徹落實(shí)《新一代人工智能發(fā)展規(guī)劃》，國(guó)家有關(guān)部委相繼頒布出臺(tái)了一系列政策。截至2022年2月，全國(guó)共有440所高校設(shè)置了人工智能本科專業(yè)，387所高等職業(yè)教育（�？疲⿲W(xué)校設(shè)置了人工智能技術(shù)服務(wù)專業(yè)，一些高校甚至已經(jīng)在積極探索人工智能跨學(xué)科的建設(shè)。在高中階段，“人工智能初步”已經(jīng)成為信息技術(shù)課程的選擇性必修內(nèi)容之一。在2022年實(shí)現(xiàn)“從0到1”突破的義務(wù)教育階段信息科技課程標(biāo)準(zhǔn)中，明確要求在7～9年級(jí)需要學(xué)習(xí)“人工智能與智慧社會(huì)”相關(guān)內(nèi)容，實(shí)際上，1～6年級(jí)階段信息技術(shù)課程的不少內(nèi)容也與人工智能關(guān)系密切，是學(xué)習(xí)人工智能的基礎(chǔ)。
人工智能是一門具有高度交叉屬性的學(xué)科，筆者認(rèn)為其交叉性至少體現(xiàn)在三個(gè)方面：行業(yè)交叉、學(xué)科交叉、學(xué)派交叉。在大數(shù)據(jù)、算法、算力三駕馬車的推動(dòng)下，新一代人工智能已經(jīng)逐步開(kāi)始賦能各個(gè)行業(yè)。人工智能也在助力各學(xué)科的研究，近幾年，《自然》等頂級(jí)刊物不斷刊發(fā)人工智能賦能學(xué)科的文章，如人工智能推動(dòng)數(shù)學(xué)、化學(xué)、生物、考古、設(shè)計(jì)、音樂(lè)以及美術(shù)等的發(fā)展。人工智能內(nèi)部的學(xué)派也在不斷交叉融合，像知名的AlphaGo，就是集三大主流學(xué)派優(yōu)勢(shì)，并且現(xiàn)在這種不同學(xué)派間取長(zhǎng)補(bǔ)短的研究開(kāi)展得如火如荼�？傊磥�(lái)的學(xué)習(xí)、工作與生活中，人工智能賦能的身影將無(wú)處不在，因此掌握一定的人工智能知識(shí)與技能將大有裨益。
從筆者長(zhǎng)期從事人工智能教學(xué)、研究經(jīng)驗(yàn)來(lái)看，一些人對(duì)人工智能還存在一定的誤區(qū)。比如將編程與人工智能直接畫上了等號(hào)，又或是認(rèn)為人工智能就只有深度學(xué)習(xí)等。實(shí)際上，人工智能的知識(shí)體系十分龐大，內(nèi)容涵蓋相當(dāng)廣泛，不但有邏輯推理、知識(shí)工程、搜索算法等相關(guān)內(nèi)容，還涉及機(jī)器學(xué)習(xí)、深度學(xué)習(xí)以及強(qiáng)化學(xué)習(xí)等算法模型。當(dāng)然，了解人工智能的起源與發(fā)展、人工智能的道德倫理對(duì)正確認(rèn)識(shí)人工智能和樹(shù)立正確的價(jià)值觀也是十分必要的。
通過(guò)對(duì)人工智能及其相關(guān)知識(shí)的系統(tǒng)學(xué)習(xí)，可以培養(yǎng)數(shù)學(xué)思維（mathematicalthinking）、邏輯思維（reasoningthinking）、計(jì)算思維（computationalthinking）、藝術(shù)思維（artisticthinking）、創(chuàng)新思維（innovativethinking）與數(shù)據(jù)思維（datathinking），即MRCAID。然而遺憾的是，目前市場(chǎng)上既能較綜合介紹人工智能相關(guān)知識(shí)，又能輔以程序代碼解決問(wèn)題，同時(shí)還能迅速入門的圖書并不多見(jiàn)。因此筆者策劃了本系列圖書，以期實(shí)現(xiàn)體系內(nèi)容較全、配合程序操練及上手簡(jiǎn)單方便等特點(diǎn)。
本書以搜索算法為主線，按照如下內(nèi)容進(jìn)行組織：第1章以棋局為引，介紹了搜索算法與智能、盲目搜索與啟發(fā)式搜索以及優(yōu)化的相關(guān)概念；第2章主要介紹算法問(wèn)題中涉及的基本數(shù)據(jù)結(jié)構(gòu)與復(fù)雜度分析等內(nèi)容；第3章介紹了狀態(tài)空間、樹(shù)和圖的一些基本知識(shí)；第4章圍繞具體問(wèn)題，分別介紹了廣度優(yōu)先搜索算法、深度優(yōu)先搜索算法、啟發(fā)式算法以及對(duì)抗搜索算法等內(nèi)容；第5章著重介紹線性規(guī)劃與非線性規(guī)劃的內(nèi)容，這些內(nèi)容是學(xué)習(xí)人工智能，尤其是機(jī)器學(xué)習(xí)的重要基礎(chǔ)之一；第6章引入模擬退火與禁忌搜索算法求解組合優(yōu)化問(wèn)題；第7章介紹了遺傳算法、蟻群算法和粒子群算法是如何解決實(shí)際問(wèn)題的案例，也讓讀者了解到群智能中的競(jìng)爭(zhēng)、競(jìng)合與合作是如何演變成算法的過(guò)程。值得注意的是，第6章與第7章中大部分內(nèi)容體現(xiàn)了人工智能跨學(xué)科的思想，讀者可以從這兩章的內(nèi)容中感受到交叉學(xué)科解決問(wèn)題的強(qiáng)大力量。本書的附錄部分回顧了類、繼承等相關(guān)概念，介紹了人工智能博弈基礎(chǔ)的相關(guān)內(nèi)容，同時(shí)還介紹了Python實(shí)驗(yàn)室JupyterLab的使用。
本書的出版要感謝曾提供熱情指導(dǎo)與幫助的院士、教授、中小學(xué)教師等專家學(xué)者，也要感謝與筆者一起并肩參與寫作的其他作者，同時(shí)還要感謝化學(xué)工業(yè)出版社編輯老師們的熱情支持與一絲不茍的工作態(tài)度。
在本書的出版過(guò)程中，未來(lái)基因（北京）人工智能研究院、騰訊教育、阿里云、科大訊飛等機(jī)構(gòu)給予了大力支持，在此一并表示感謝。
由于筆者水平有限，書中內(nèi)容不可避免會(huì)存在疏漏，歡迎廣大讀者批評(píng)指正并提出寶貴的意見(jiàn)。
龔超
于清華大學(xué)
第1章 搜索的世界 001
1.1 出“棋”不易 002
1.1.1 棋技，智力的象征？ 002
1.1.2 搜索＋評(píng)估=智能？ 006
1.1.3 AlphaGo是怎樣煉成的？ 008
1.2 給盲目一些信息 011
1.2.1 盲目搜索 011
1.2.2 啟發(fā)式搜索 013
1.2.3 博弈中前行 015
1.3 一切皆可優(yōu)化 017
1.3.1 目標(biāo)與約束 017
1.3.2 蒙特卡洛樹(shù)搜索 021
1.3.3 群智能 024
第2章 基本數(shù)據(jù)結(jié)構(gòu)與復(fù)雜度分析 030
2.1 數(shù)據(jù)關(guān)系與數(shù)據(jù)結(jié)構(gòu) 031
2.1.1 數(shù)據(jù)關(guān)系 031
2.1.2 數(shù)據(jù)結(jié)構(gòu) 032
2.2 棧與隊(duì)列 033
2.2.1 棧 033
2.2.2 隊(duì)列 038
2.2.3 雙端隊(duì)列 040
2.3 復(fù)雜度 042
2.3.1 衡量算法的效率 042
2.3.2 復(fù)雜度的分析 044
第3章 狀態(tài)空間、樹(shù)與圖 050
3.1 狀態(tài)空間 051
3.1.1 狀態(tài)的表示 051
3.1.2 迷宮、漢諾塔與八數(shù)碼 053
3.1.3 農(nóng)夫過(guò)河 054
3.2 樹(shù) 057
3.2.1 樹(shù)的基本概念 057
3.2.2 二叉樹(shù) 059
3.3 圖 062
3.3.1 圖的基本概念 062
3.3.2 圖的存儲(chǔ)方式 065
第4章 搜索技術(shù) 072
4.1 盲目搜索 073
4.1.1 廣度優(yōu)先搜索算法 073
4.1.2 深度優(yōu)先搜索算法 080
4.2 啟發(fā)式搜索 086
4.2.1 貪婪算法 086
4.2.2 A*算法 089
4.3 對(duì)抗搜索 093
4.3.1 博弈下的極小極大搜索 094
4.3.2 alpha–beta剪枝算法 102
第5章 線性與非線性規(guī)劃中的搜索 105
5.1 優(yōu)化問(wèn)題 106
5.1.1 無(wú)處不在的優(yōu)化 106
5.1.2 優(yōu)化問(wèn)題的描述 106
5.2 線性規(guī)劃 108
5.2.1 圖解線性規(guī)劃 110
5.2.2 搜頂點(diǎn) 113
5.2.3 程序求解 114
5.3 非線性規(guī)劃 117
5.3.1 從導(dǎo)數(shù)中獲得搜索信息 117
5.3.2 非線性規(guī)劃難在哪 124
5.3.3 程序求解 126
第6章 組合優(yōu)化與求解 132
6.1 組合優(yōu)化問(wèn)題 133
6.1.1 旅行商問(wèn)題 134
6.1.2 背包問(wèn)題 138
6.2 模擬退火 140
6.2.1 基本原理 140
6.2.2 參數(shù)與流程 142
6.2.3 程序代碼 144
6.3 禁忌搜索 149
6.3.1 基本原理 149
6.3.2 參數(shù)與流程 152
6.3.3 程序代碼 155
第7章 群智能算法 160
7.1 遺傳算法 161
7.1.1 基本原理 161
7.1.2 參數(shù)與流程 166
7.1.3 程序代碼 171
7.2 蟻群算法 176
7.2.1 基本原理 176
7.2.2 參數(shù)與流程 180
7.2.3 程序代碼 184
7.3 粒子群算法 189
7.3.1 基本原理 189
7.3.2 參數(shù)與流程 191
7.3.3 程序代碼 196
附錄 199
附錄一 類與繼承 200
附錄二 人工智能的博弈基礎(chǔ) 208
附錄三 騰訊扣叮Python實(shí)驗(yàn)室：JupyterLab使用說(shuō)明 214
書單推薦
