人工智能（第3版） Artificial Intelligence in the 21st Century

作為電腦科學的一個分支，人工智能主要研究、開發用於模擬、延伸和擴展人類智能的理論、方法、技術及應用系統，涉及機器人、語音識別、圖像識別、自然語言處理和專家系統等方向。

本書包括引言、基礎知識、基於知識的系統、人工智能高級專題、人工智能的現在和未來以及安全與編程六部分內容。第一部分從人工智能的定義講起，對人工智能的早期歷史、思維和智能的內涵、圖靈測試、啟發式方法、新千年人工智能的發展進行了簡要論述。第二部分詳細講述了人工智能中的盲目搜索、知情搜索、博弈中的搜索、人工智能中的邏輯、知識表示和產生式系統等基礎知識。第三部分介紹並探究了人工智能領域的成功案例，如DENDRAL、MYCIN、EMYCIN 等經典的專家系統，振動故障診斷、自動牙科識別等新的專家系統，也介紹了機器學習、深度學習以及受到自然啟發的搜索算法等。第四部分介紹了自然語言處理和自動規劃等高級專題。第五部分對人工智能的歷史和現狀進行了梳理，回顧了幾十年來人工智能所取得的諸多成就，並對其未來進行了展望。第六部分主要介紹人工智能的安全以及編程問題。

本書系統、全面地講解了人工智能的相關知識，既簡明扼要地介紹了這一學科的基礎知識，也對自然語言處理、自動規劃、神經網絡等內容進行了拓展，更輔以實例，可以幫助讀者扎扎實實打好基礎。本書內容易讀易學，適合人工智能相關領域和對該領域感興趣的讀者閱讀，也適合高校電腦專業的教師和學生參考。

史蒂芬·卢奇（Stephen Lucci）拥有纽约市立大学研究生院的博士学位，在纽约城市学院教授计算机科学，在高性能计算和人工智能领域发表过多篇文章。

萨尔汗·M. 穆萨（Sarhan M. Musa）博士，在普雷里维尤农工大学（Prairie View A&M） 任 教， 著 有 Computational Nanophotonics（CRC Press） 和 Finite Element Analysis （MLI）等多部图书。

丹尼·科佩克（Danny Kopec）（已故），本书第 2 版的合著者，曾任教于布鲁克林学院，著有多部图书，是一位国际象棋大师。

第 一部分 引 言

第 1 章 人工智能概述 2

1.0 引言 2

1.0.1 人工智能的定義 3

1.0.2 思維與智能 3

1.1 圖靈測試 5

1.1.1 圖靈測試的定義 5

1.1.2 圖靈測試的爭議和批評 7

1.2 強人工智能與弱人工智能 9

1.3 啟發式方法 10

1.3.1 長方體的對角線：解決一個相對簡單但相關的問題 10

1.3.2 水壺問題：反向倒推 11

1.4 識別適用人工智能來求解的問題 12

1.5 應用和方法 14

1.5.1 搜索算法和拼圖問題 15

1.5.2 二人博弈 16

1.5.3 自動推理 17

1.5.4 產生式規則和專家系統17

1.5.5 細胞自動機 18

1.5.6 神經計算 19

1.5.7 遺傳算法 20

1.5.8 知識表示 21

1.5.9 不確定性推理 22

1.6 人工智能的早期歷史 23

1.7 人工智能的近期歷史到現在 26

1.7.1 電腦博弈 26

1.7.2 專家系統 27

1.7.3 神經計算 28

1.7.4 進化計算 28

1.7.5 自然語言處理 29

1.7.6 生物信息學 31

1.8 新千年人工智能的發展 31

1.9 本章小結 32

第二部分 基 礎 知 識

第 2 章 盲目搜索 42

2.0 簡介：智能系統中的搜索 42

2.1 狀態空間圖 43

2.1.1 假幣問題 43

2.2 生成-測試範式 45

2.2.1 回溯法 46

2.2.2 貪心算法 50

2.2.3 旅行商問題 52

2.3 盲目搜索算法 54

2.3.1 深度優先搜索 54

2.3.2 廣度優先搜索 56

2.4 盲目搜索算法的實現和比較 58

2.4.1 深度優先搜索的實現 58

2.4.2 廣度優先搜索的實現 60

2.4.3 問題求解性能的衡量指標 61

2.4.4 DFS 和 BFS 的比較 61

2.5 本章小結 64

第 3 章 知情搜索 70

3.0 引言 70

3.1 啟發式方法 72

3.2 知情搜索（第 一部分）——找到任一解 76

3.2.1 爬山法 76

3.2.2 最陡爬山法 77

3.3 最佳優先搜索 80

3.4 集束搜索 83

3.5 搜索算法的其他指標 84

3.6 知情搜索（第二部分）——找到最優解 85

3.6.1 分支定界法 85

3.6.2 使用低估計啟發值的分支定界法 90

3.6.3 採用動態規劃的分支定界法 93

3.6.4 A*搜索 94

3.7 知情搜索（第三部分）—高級搜索算法 95

3.7.1 約束滿足搜索 95

3.7.2 與或樹 96

3.7.3 雙向搜索 97

3.8 本章小結 99

第 4 章 博弈中的搜索 104

4.0 引言 104

4.1 博弈樹和極小化極大評估 105

4.1.1 啟發式評估 106

4.1.2 博弈樹的極小化極大評估 107

4.2 帶α-β 剪枝的極小化極大算法 110

4.3 極小化極大算法的變體和改進 114

4.3.1 負極大值算法 115

4.3.2 漸進深化法 116

4.3.3 啟發式方法的後續和地平線效應 117

4.4 機會博弈和期望極小化極大算法 117

4.5 博弈論 119

4.6 本章小結 121

第 5 章 人工智能中的邏輯 126

5.0 引言 126

5.1 邏輯和表示 127

5.2 命題邏輯 128

5.2.1 基礎知識 129

5.2.2 命題邏輯中的論證 133

5.2.3 證明命題邏輯論證有效的第二種方法 134

5.3 謂詞邏輯簡介 135

5.3.1 謂詞邏輯中的合一 136

5.3.2 謂詞邏輯中的歸結 138

5.3.3 將謂詞表達式轉換為子句形式 140

5.4 其他一些邏輯 143

5.4.1 二階邏輯 143

5.4.2 非單調邏輯 144

5.4.3 模糊邏輯 144

5.4.4 模態邏輯 144

5.5 本章小結 145

第 6 章 知識表示 151

6.0 引言 151

6.1 圖形草圖和人類視窗 154

6.2 圖和哥尼斯堡橋問題 157

6.3 搜索樹 158

6.3.1 決策樹 158

6.4 表示方法的選擇 159

6.5 產生式系統 162

6.6 面向對象 162

6.7 框架 164

6.8 腳本和概念依賴系統 166

6.9 語義網絡 169

6.10 關聯 171

6.11 最近的方法 172

6.11.1 概念地圖 172

6.11.2 概念圖 174

6.11.3 Baecker 的工作 174

6.12 智能體：智能或其他 175

6.12.1 智能體的一些歷史 177

6.12.2 當代智能體 179

6.12.3 語義網 180

6.12.4 IBM 眼中的未來世界 180

6.12.5 本書作者的觀點 181

6.13 本章小結 181

第 7 章 產生式系統 188

7.0 引言 188

7.1 背景 188

7.2 基本示例 190

7.3 CarBuyer 系統 192

7.4 產生式系統和推理方法 197

7.4.1 沖突消解 199

7.4.2 前向鏈接 201

7.4.3 後向鏈接 202

7.5 產生式系統和細胞自動機 206

7.6 隨機過程與馬爾可夫鏈 208

7.7 本章小結 209

第三部分 基於知識的系統

第 8 章 人工智能中的不確定性 214

8.0 引言 214

8.1 模糊集 214

8.2 模糊邏輯 216

8.3 模糊推理 217

8.4 概率論和不確定性 220

8.5 本章小結 224

第 9 章 專家系統 227

9.0 引言 227

9.1 背景 227

9.1.1 人類專家和機器專家 228

9.2 專家系統的特點 233

9.3 知識工程 234

9.4 知識獲取 236

9.5 經典的專家系統 238

9.5.1 DENDRAL 238

9.5.2 MYCIN 239

9.5.3 EMYCIN 241

9.5.4 PROSPECTOR 241

9.5.5 模糊知識和貝葉斯規則 243

9.6 提高效率的方法 245

9.6.1 守護規則 245

9.6.2 Rete 算法 246

9.7 基於案例的推理 247

9.8 更多最新的專家系統 251

9.8.1 就業匹配改善系統 251

9.8.2 振動故障診斷專家系統 252

9.8.3 自動牙齒識別 252

9.8.4 更多採用案例推理的專家系統 253

9.9 本章小結 253

第 10 章 機器學習第 一部分：神經 網絡 259

10.0 引言 259

10.1 機器學習概述 260

10.2 機器學習系統中反饋的作用 262

10.3 歸納學習 263

10.4 利用決策樹進行學習 264

10.5 決策樹適用的問題 265

10.6 熵 266

10.7 使用 ID3 構建決策樹 267

10.8 其他問題 269

10.9 人工神經網絡的基本原理 270

10.10 麥卡洛克-皮茨網絡 271

10.11 感知器學習規則 272

10.12 增量規則 280

10.13 反向傳播 284

10.14 實現中的問題 289

10.14.1 模式分析 292

10.14.2 訓練方法 293

10.15 離散霍普菲爾德網絡 294

10.16 應用領域 298

10.17 本章小結 305

第 11 章 機器學習第二部分：深度學習 314

11.0 引言 314

11.1 深度學習應用簡介 315

11.2 深度學習網絡中的層 315

11.3 深度學習類型 316

11.3.1 多層神經網絡 316

11.3.2 捲積神經網絡317

11.3.3 循環神經網絡 321

11.3.4 長短期記憶網絡 322

11.3.5 遞歸神經網絡 322

11.3.6 堆疊自編碼器 322

11.3.7 極限學習機 323

11.4 本章小結 325

第 12 章 受大自然啟發的搜索 333

12.0 引言 333

12.1 模擬退火 334

12.2 遺傳算法 337

12.3 遺傳規劃 344

12.4 禁忌搜索 348

12.5 蟻群優化算法 350

12.6 本章小結 353

第四部分 高 級 專 題

第 13 章 自然語言理解 362

13.0 引言 362

13.1 概述：語言的問題和可能性 362

13.2 自然語言處理的歷史 364

13.2.1 奠基時期（20 世紀 40 年代和 50 年代） 364

13.2.2 符號方法與隨機方法（1957—1970） 365

13.2.3 4 種範式（1970— 1983） 365

13.2.4 經驗主義和有限狀態模型（1983—1993） 366

13.2.5 大融合時期（1994— 1999） 367

13.2.6 機器學習的興起（2000—2008） 367

13.3 語法和形式語法 367

13.3.1 語法類型 368

13.3.2 句法解析：CYK 算法 371

13.4 語義分析和擴展語法 373

13.4.1 轉換語法 373

13.4.2 系統語法 373

13.4.3 格語法 374

13.4.4 語義語法 375

13.4.5 尚克的系統 376

13.5 NLP 中的統計方法 379

13.5.1 統計解析 379

13.5.2 機器翻譯（回顧）和 IBM 的 Candide 系統 380

13.5.3 詞義消歧 380

13.6 用於統計 NLP 的概率模型 381

13.6.1 隱馬爾可夫模型 381

13.6.2 維特比算法 383

13.7 用於統計 NLP 的語言數據集 384

13.7.1 賓州樹庫項目 384

13.7.2 WordNet 385

13.7.3 NLP 中的隱喻模型 385

13.8 應用：信息提取和問答系統 387

13.8.1 問答系統 387

13.8.2 信息提取 391

13.9 當前和未來的研究（基於查尼阿克的觀點） 392

13.10 語音理解 392

13.10.1 語音理解技術 392

13.11 語音理解的應用 395

13.11.1 Dragon 自然語音系統 和 Windows 語音識別系統 396

13.12 本章小結 399

第 14 章 自動規劃 406

14.0 引言 406

14.1 規劃問題 407

14.1.1 規劃中的術語 407

14.1.2 規劃的應用示例 408

14.2 規劃簡史和著名的框架問題 412

14.2.1 框架問題 413

14.3 規劃方法 414

14.3.1 規劃即搜索 414

14.3.2 偏序規劃 418

14.3.3 層次規劃 419

14.3.4 基於案例的規劃 420

14.3.5 規劃方法集錦 421

14.4 早期的規劃系統 422

14.4.1 STRIPS 422

14.4.2 NOAH 422

14.4.3 NONLIN 423

14.5 更多的現代規劃系統 424

14.5.1 O-PLAN 424

14.5.2 Graphplan 426

14.5.3 規劃系統集錦 427

14.5.4 面向學習系統的規劃方法 427

14.5.5 SciBox 自動規劃器 428

14.6 本章小結 430

第五部分 現在和未來

第 15 章 機器人技術 438

15.0 引言 438

15.1 歷史：服務人類、模仿人類、增強人類和替代人類 440

15.1.1 早期的機械機器人 440

15.1.2 電影與文學作品中的機器人 442

15.1.3 20 世紀的機器人 443

15.2 技術問題 447

15.2.1 機器人的組件 447

15.2.2 運動 450

15.2.3 點位機器人的路徑規劃 451

15.2.4 移動機器人運動學 451

15.3 應用：21 世紀的機器人 453

15.4 本章小結 460

第 16 章 高級電腦博弈 462

16.0 引言 462

16.1 跳棋：從塞繆爾到謝弗 462

16.1.1 跳棋游戲中的啟發式學習方法 465

16.1.2 機械式學習與泛化 467

16.1.3 簽名錶評估和棋譜學習 468

16.1.4 謝弗的 Chinook：跳棋程序中的世界冠軍 468

16.1.5 跳棋博弈問題已被解決 470

16.2 國際象棋：人工智能的“果蠅” 472

16.2.1 電腦國際象棋的歷史背景 473

16.2.2 編程方法 474

16.2.3 超越地平線效應 482

16.2.4 Deep Thought 和 Deep Blue 與特級大師的較量：1988 年至 1995 年 482

16.3 電腦國際象棋程序對人工智能的貢獻 484

16.3.1 機器搜索 484

16.3.2 人類搜索與機器搜索 484

16.3.3 啟發式方法、知識和問題求解 485

16.3.4 暴力計算：知識與搜索，表現與能力 486

16.3.5 殘局數據庫和並行計算 487

16.3.6 本書作者 Danny Kopec 的貢獻 491

16.4 其他博弈游戲 491

16.4.1 奧賽羅棋 491

16.4.2 雙陸棋 493

16.4.3 橋牌 494

16.4.4 撲克 495

16.5 圍棋：人工智能的“新果蠅” 497

16.6 本章小結 499

第 17 章 AI 大事記 507

17.0 引言 507

17.1 本書第 1 部分回顧 507

17.2 普羅米修斯歸來 509

17.3 本書第 2 部分回顧：目前 AI 領域的成就 510

17.4 IBM 沃森-危險邊緣挑戰賽 513

17.5 21 世紀的人工智能 517

17.6 本章小結 518

第六部分 安全和編程

第 18 章 網絡安全中的人工智能（選讀） 522

18.0 引言 522

18.1 IPsec 523

18.2 SA. 523

18.3 安全策略 524

18.3.1 安全策略數據庫 524

18.3.2 SA 選擇器 524

18.3.3 SA 的組合 524

18.3.4 IPsec 協議模式 524

18.3.5 防重放窗口 525

18.4 安全電子交易 525

18.4.1 SET 的業務需求 526

18.5 入侵者 526

18.6 入侵檢測 527

18.6.1 入侵檢測方法 527

18.7 惡意程序 529

18.7.1 病毒程序生命周期的不同階段 529

18.8 反病毒掃描 529

18.8.1 反病毒掃描程序的不同版本 530

18.9 蠕蟲程序 530

18.10 防火牆 530

18.10.1 防火牆的特點 531

18.10.2 防火牆控制訪問的方式 531

18.10.3 防火牆的類型 531

18.11 可信系統 531

18.12 本章小結 534

第 19 章 人工智能編程工具（選讀） 538

19.1 Prolog 538

19.1.1 Prolog 與 C/C++的不同 539

19.1.2 Prolog 的運行機制 540

19.1.3 Prolog 語言發展的里程碑 540

19.1.4 子句 541

19.1.5 Robinson 歸結原理 543

19.1.6 Prolog 程序的組成 544

19.1.7 數據庫查詢 544

19.1.8 Prolog 的查詢求解過程 544

19.1.9 復合查詢 545

19.1.10 _變量 545

19.1.11 Prolog 中的遞歸 545

19.1.12 Prolog 中的數據結構：列表 546

19.1.13 列表的頭部和尾部 546

19.1.14 輸出列表中的所有元素 547

19.1.15 逆序輸出列表中的元素 547

19.1.16 為列表追加元素 547

19.1.17 確定給定元素是否在列表中 547

19.1.18 輸出列表的長度 547

19.1.19 Prolog 的執行控制 547

19.1.20 Turbo Prolog 550

19.2 Python 551

19.2.1 運行 Python 552

19.2.2 Python 的不足之處 553

19.2.3 Python 的特性 553

19.2.4 作為第 一類對象的函數 555

19.2.5 有用的 Python 庫 556

19.2.6 實用工具 557

19.2.7 測試代碼 559

19.3 MATLAB 559

19.3.1 開始使用 MATLAB 559

19.3.2 使用 MATLAB 進行計算 560

19.3.3 繪圖 564

19.3.4 符號計算 569

19.3.5 Python 用戶如何使用MATLAB 570