人工智能（復(fù)雜問題求解的結(jié)構(gòu)和策略原書第5版）

出版者的話.
專家指導(dǎo)委員會(huì)
譯者序
前言
致謝
第一部分 人工智能的歷史淵源及研究范圍
第1章 人工智能的歷史及應(yīng)用 3
1.1 從伊甸園到第一臺(tái)電子計(jì)算機(jī) 3
1.1.1 人工智能基礎(chǔ)的簡(jiǎn)要?dú)v史 4
1.1.2 理性主義和經(jīng)驗(yàn)主義學(xué)派對(duì)人工智能的影響 6
1.1.3 形式邏輯的發(fā)展 7
1.1.4 圖靈測(cè)試 10
1.1.5 智能的生物和社會(huì)模型：主體理論 12
1.2 人工智能的應(yīng)用領(lǐng)域 15
1.2.1 博弈 15
1.2.2 自動(dòng)推理和定理證明 16
1.2.3 專家系統(tǒng) 16
1.2.4 自然語(yǔ)言理解和語(yǔ)義建模 18
1.2.5 對(duì)人類工作能力建模 18
1.2.6 規(guī)劃和機(jī)器人 19
1.2.7 人工智能的語(yǔ)言和環(huán)境 20
1.2.8 機(jī)器學(xué)習(xí) 20
1.2.9 另類表示：神經(jīng)網(wǎng)絡(luò)和遺傳算法 21
1.2.10 AI和哲學(xué) 22
1.3 人工智能概要 22
1.4 結(jié)語(yǔ)和參考文獻(xiàn) 23
1.5 習(xí)題 24
第二部分 作為表示和搜索的人工智能
第2章 謂詞演算 32
2.0 簡(jiǎn)介 32
2.1 命題演算 32
2.1.1 符號(hào)和語(yǔ)句 32
2.1.2 命題演算的語(yǔ)義 33
2.2 謂詞演算 35
2.2.1 謂詞的語(yǔ)法和語(yǔ)句 35
2.2.2 謂詞演算的語(yǔ)義 40
2.2.3 語(yǔ)義含義的積木世界例子 42
2.3 使用推理規(guī)則產(chǎn)生謂詞演算表達(dá)式 44
2.3.1 推理規(guī)則 44
2.3.2 合一算法 46
2.3.3 合一的例子 49
2.4 應(yīng)用：一個(gè)基于邏輯的財(cái)務(wù)顧問 52
2.5 結(jié)語(yǔ)和參考文獻(xiàn) 55
2.6 習(xí)題 55
第3章 用以搜索狀態(tài)空間的結(jié)構(gòu)和策略 57
3.0 簡(jiǎn)介 57
3.1 圖論 59
3.1.1 狀態(tài)空間搜索的結(jié)構(gòu) 59
3.1.2 有限狀態(tài)自動(dòng)機(jī) 61
3.1.3 問題的狀態(tài)空間表示 62
3.2 用于狀態(tài)空間搜索的策略 67
3.2.1 數(shù)據(jù)驅(qū)動(dòng)搜索和目標(biāo)驅(qū)動(dòng)搜索 67
3.2.2 圖搜索的實(shí)現(xiàn) 68
3.2.3 深度優(yōu)先搜索和寬度優(yōu)先搜索 71
3.2.4 迭代加深的深度優(yōu)先搜索 76
3.3 利用狀態(tài)空間來(lái)表示謂詞演算推理 77
3.3.1 邏輯系統(tǒng)的狀態(tài)空間描述 77
3.3.2 與或圖 78
3.3.3 進(jìn)一步的例子和應(yīng)用 80
3.4 結(jié)語(yǔ)和參考文獻(xiàn) 87
3.5 習(xí)題 87
第4章 啟發(fā)式搜索 89
4.0 簡(jiǎn)介 89
4.1 啟發(fā)式搜索算法 92
4.1.1 爬山 92
4.1.2 動(dòng)態(tài)程序設(shè)計(jì) 93
4.2 最佳優(yōu)先搜索算法 96
4.2.1 實(shí)現(xiàn)最佳優(yōu)先搜索 96
4.2.2 實(shí)現(xiàn)啟發(fā)評(píng)估函數(shù) 98
4.2.3 啟發(fā)式搜索和專家系統(tǒng) 103
4.3 可采納性. 單調(diào)性和信息度 104
4.3.1 可采納性尺度 104
4.3.2 單調(diào)性 106
4.3.3 信息度更高的啟發(fā)是更好的啟發(fā) 107
4.4 在博弈中使用啟發(fā) 108
4.4.1 針對(duì)可窮舉搜索情況的極小極大過程 108
4.4.2 固定層深的極小極大過程 109
4.4.3 α-β過程 113
4.5 復(fù)雜度問題 114
4.6 結(jié)語(yǔ)和參考文獻(xiàn) 116
4.7 習(xí)題 117
第5章 隨機(jī)方法 120
5.0 簡(jiǎn)介 120
5.1 計(jì)數(shù)基礎(chǔ)（選讀） 121
5.1.1 加法和乘法定理 121
5.1.2 排列與組合 123
5.2 概率論基礎(chǔ) 124
5.2.1 樣本空間. 概率和獨(dú)立性 124
5.2.2 概率推理：一個(gè)道路/交通例子 126
5.2.3 隨機(jī)變量 127
5.2.4 條件概率 129
5.3 隨機(jī)方法學(xué)的應(yīng)用 131
5.4 貝葉斯定理 133
5.4.1 概述 133
5.4.2 道路/交通例子的擴(kuò)展 136
5.5 結(jié)語(yǔ)和參考文獻(xiàn) 137
5.6 習(xí)題 138
第6章 為狀態(tài)空間搜索建立控制算法 140
6.0 簡(jiǎn)介 140
6.1 基于遞歸的搜索（可選） 141
6.1.1 遞歸 141
6.1.2 一個(gè)遞歸搜索的例子：模式驅(qū)動(dòng)推理 142
6.2 產(chǎn)生式系統(tǒng) 145
6.2.1 定義和歷史 145
6.2.2 產(chǎn)生式系統(tǒng)的例子 147
6.2.3 產(chǎn)生式系統(tǒng)中的搜索控制 153
6.2.4 AI產(chǎn)生式系統(tǒng)的優(yōu)點(diǎn) 156
6.3 用于問題求解的黑板結(jié)構(gòu) 157
6.4 結(jié)語(yǔ)和參考文獻(xiàn) 159
6.5 習(xí)題 160
第三部分 表示和智能：AI中的挑戰(zhàn)
第7章 知識(shí)表示 164
7.0 知識(shí)表示問題 164
7.1 AI表象圖式的簡(jiǎn)要?dú)v史 165
7.1.1 語(yǔ)義關(guān)聯(lián)理論 165
7.1.2 語(yǔ)義網(wǎng)絡(luò)的早期研究 167
7.1.3 網(wǎng)絡(luò)關(guān)系的標(biāo)準(zhǔn)化 170
7.1.4 腳本 174
7.1.5 框架 177
7.2 概念圖：網(wǎng)絡(luò)語(yǔ)言 180
7.2.1 概念圖簡(jiǎn)介 180
7.2.2 類型. 個(gè)體和名字 181
7.2.3 類型層次 182
7.2.4 泛化和特化 183
7.2.5 命題結(jié)點(diǎn) 185
7.2.6 概念圖和邏輯 185
7.3 顯式表示的替代方法 187
7.3.1 Brooks假設(shè)和包容結(jié)構(gòu) 187
7.3.2 Copycat結(jié)構(gòu) 189
7.4 基于主體的和分布式的問題求解方法 192
7.4.1 基于主體的定義 192
7.4.2 基于主體的應(yīng)用 193
7.5 結(jié)語(yǔ)和參考文獻(xiàn) 195
7.6 習(xí)題 197
第8章 求解問題的強(qiáng)方法 200
8.0 簡(jiǎn)介 200
8.1 專家系統(tǒng)技術(shù)概覽 201
8.1.1 基于規(guī)則的專家系統(tǒng)設(shè)計(jì) 201
8.1.2 問題選擇和知識(shí)工程的步驟 202
8.1.3 概念模型及其在知識(shí)獲取中的作用 204
8.2 基于規(guī)則的專家系統(tǒng) 206
8.2.1 產(chǎn)生式系統(tǒng)和目標(biāo)驅(qū)動(dòng)問題求解 206
8.2.2 目標(biāo)驅(qū)動(dòng)推理中的解釋和透明性 209
8.2.3 利用產(chǎn)生式系統(tǒng)進(jìn)行數(shù)據(jù)驅(qū)動(dòng)推理 210
8.2.4 專家系統(tǒng)的啟發(fā)和控制 212
8.3 基于模型系統(tǒng). 基于案例系統(tǒng)和混合系統(tǒng) 214
8.3.1 基于模型推理簡(jiǎn)介 214
8.3.2 基于模型推理：來(lái)自NASA的例子 217
8.3.3 基于案例推理介紹 219
8.3.4 混合設(shè)計(jì)：強(qiáng)方法系統(tǒng)的優(yōu)勢(shì)和不足 222
8.4 規(guī)劃 224
8.4.1 簡(jiǎn)介 224
8.4.2 使用規(guī)劃宏：STRIPS 228
8.4.3 teleo-reactive規(guī)劃 231
8.4.4 規(guī)劃：來(lái)自NASA的例子 233
8.5 結(jié)語(yǔ)和參考文獻(xiàn) 235
8.6 習(xí)題 236
第9章 不確定條件下的推理 238
9.0 簡(jiǎn)介 .. 238
9.1 基于邏輯的反繹推理 239
9.1.1 非單調(diào)推理邏輯 239
9.1.2 真值維護(hù)系統(tǒng) 242
9.1.3 基于最小模型的邏輯 245
9.1.4 集合覆蓋和基于邏輯的反繹 247
9.2 反繹：邏輯之外的辦法 249
9.2.1 Stanford確信度代數(shù) 249
9.2.2 模糊集推理 251
9.2.3 Dempster-Shafer證據(jù)理論 254
9.3 處理不確定性的隨機(jī)方法 258
9.3.1 有向圖模型：貝葉斯信念網(wǎng)絡(luò) 258
9.3.2 有向圖模型：d-可分 260
9.3.3 有向圖模型：一個(gè)推理算法 261
9.3.4 馬爾可夫模型：離散馬爾可夫過程 263
9.3.5 隱馬爾可夫模型 265
9.3.6 用HMM和韋特比算法解碼音素串 266
9.4 結(jié)語(yǔ)和參考文獻(xiàn) 269
9.5 習(xí)題 270
第四部分 機(jī)器學(xué)習(xí)
第10章 基于符號(hào)的機(jī)器學(xué)習(xí) 275
10.0 簡(jiǎn)介 275
10.1 基于符號(hào)學(xué)習(xí)的框架 277
10.2 變型空間搜索 281
10.2.1 泛化操作和概念空間 281
10.2.2 候選解排除算法 282
10.2.3 LEX：?jiǎn)l(fā)式歸納搜索 287
10.2.4 評(píng)估候選解排除算法 289
10.3 ID3決策樹歸納算法 290
10.3.1 自頂向下決策樹歸納 292
10.3.2 測(cè)試選擇的信息論方法 293
10.3.3 評(píng)價(jià)ID3 295
10.3.4 決策樹數(shù)據(jù)問題：打包. 推進(jìn) 296
10.4 歸納偏置和學(xué)習(xí)能力 296
10.4.1 歸納偏置 296
10.4.2 可學(xué)習(xí)性理論 298
10.5 知識(shí)和學(xué)習(xí) 299
10.5.1 Meta-DENDRAL 300
10.5.2 基于解釋的學(xué)習(xí) 301
10.5.3 EBL和知識(shí)層學(xué)習(xí) 304
10.5.4 類比推理 304
10.6 無(wú)監(jiān)督學(xué)習(xí) 306
10.6.1 發(fā)現(xiàn)和無(wú)監(jiān)督學(xué)習(xí) 307
10.6.2 概念聚類 308
10.6.3 COBWEB和生物分類知識(shí)的結(jié)構(gòu) 310
10.7 強(qiáng)化學(xué)習(xí) 313
10.7.1 強(qiáng)化學(xué)習(xí)的組成部分 313
10.7.2 一個(gè)例子：九宮游戲 315
10.7.3 強(qiáng)化學(xué)習(xí)的推理算法和應(yīng)用 316
10.8 結(jié)語(yǔ)和參考文獻(xiàn) 318
10.9 習(xí)題 319
第11章 連接主義的機(jī)器學(xué)習(xí) 321
11.0 簡(jiǎn)介 321
11.1 連接網(wǎng)絡(luò)的基礎(chǔ) 322
11.2 感知機(jī)學(xué)習(xí) 324
11.2.1 感知機(jī)學(xué)習(xí)算法 324
11.2.2 例子：用感知機(jī)進(jìn)行分類 325
11.2.3 通用delta規(guī)則 328
11.3 反傳學(xué)習(xí) 330
11.3.1 反傳算法的起源 330
11.3.2 反傳算法實(shí)例1：NETtalk 333
11.3.3 反傳算法實(shí)例2：異或 334
11.4 競(jìng)爭(zhēng)學(xué)習(xí) 335
11.4.1 對(duì)于分類的“勝者全拿”學(xué)習(xí) 335
11.4.2 學(xué)習(xí)原型的Kohonen網(wǎng)絡(luò) 336
11.4.3 Outstar網(wǎng)絡(luò)和逆?zhèn)?337
11.4.4 支持向量機(jī) 339
11.5 Hebbian一致性學(xué)習(xí) 341
11.5.1 概述 341
11.5.2 無(wú)監(jiān)督Hebbian學(xué)習(xí)的例子 342
11.5.3 有監(jiān)督Hebbian學(xué)習(xí) 344
11.5.4 聯(lián)想記憶和線性聯(lián)想器 345
11.6 吸引子網(wǎng)絡(luò)或“記憶” 348
11.6.1 概述 348
11.6.2 BAM, 雙向聯(lián)想記憶 349
11.6.3 BAM處理的例子 350
11.6.4 自相關(guān)記憶和Hopfield 網(wǎng)絡(luò) 352
11.7 結(jié)語(yǔ)和參考文獻(xiàn) 355
11.8 習(xí)題 356
第12章 機(jī)器學(xué)習(xí)：社會(huì)性和涌現(xiàn)性 357
12.0 社會(huì)性和涌現(xiàn)性的學(xué)習(xí)模型 357
12.1 遺傳算法 358
12.1.1 兩個(gè)例子：CNF可滿足性問題和巡回推銷員問題 360
12.1.2 遺傳算法的評(píng)估 363
12.2 分類器系統(tǒng)和遺傳程序設(shè)計(jì) 365
12.2.1 分類器系統(tǒng) 365
12.2.2 用遺傳算子進(jìn)行程序設(shè)計(jì) 369
12.3 人工生命和基于社會(huì)的學(xué)習(xí) 373
12.3.1 生命游戲 373
12.3.2 進(jìn)化規(guī)劃 375
12.3.3 涌現(xiàn)的實(shí)例研究 377
12.4 結(jié)語(yǔ)和參考文獻(xiàn) 380
12.5 習(xí)題 381
第五部分 人工智能問題求解的高級(jí)課題
第13章 自動(dòng)推理 384
13.0 定理證明中的弱方法 384
13.1 通用問題求解程序和差別表 385
13.2 歸結(jié)定理證明 389
13.2.1 概述 389
13.2.2 為進(jìn)行歸結(jié)反駁生成子句形式 390
13.2.3 二元?dú)w結(jié)證明過程 393
13.2.4 歸結(jié)策略和簡(jiǎn)化技術(shù) 396
13.2.5 從歸結(jié)反駁中抽取解答 400
13.3 PROLOG和自動(dòng)推理 402
13.3.1 概述 402
13.3.2 邏輯編程和PROLOG 403
13.4 自動(dòng)推理進(jìn)一步的問題 407
13.4.1 弱方法求解的統(tǒng)一表示法 407
13.4.2 可選推理規(guī)則 409
13.4.3 搜索策略及其使用 410
13.5 結(jié)語(yǔ)和參考文獻(xiàn) 411
13.6 習(xí)題 411
第14章 自然語(yǔ)言理解 413
14.0 自然語(yǔ)言理解問題 413
14.1 解構(gòu)語(yǔ)言：符號(hào)分析 415
14.1.1 概述 415
14.1.2 語(yǔ)言分析的過程 416
14.2 語(yǔ)法 417
14.2.1 使用上下文無(wú)關(guān)文法說明和解析 417
14.2.2 轉(zhuǎn)移網(wǎng)絡(luò)解析器 418
14.2.3 喬姆斯基層次和上下文相關(guān)文法 421
14.3 ATN解析器的語(yǔ)法和知識(shí) 423
14.3.1 擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò)解析器 423
14.3.2 結(jié)合語(yǔ)法和語(yǔ)義知識(shí) 426
14.4 語(yǔ)言分析隨機(jī)工具 430
14.4.1 概述 430
14.4.2 馬爾可夫模型方法 431
14.4.3 決策樹方法 432
14.4.4 隨機(jī)技術(shù)的解析和其他語(yǔ)言應(yīng)用 434
14.5 自然語(yǔ)言應(yīng)用 435
14.5.1 故事理解和問題解答 435
14.5.2 數(shù)據(jù)庫(kù)前端 436
14.5.3 Web信息抽取和摘要系統(tǒng) 438
14.5.4 用學(xué)習(xí)算法來(lái)泛化抽取的信息 440
14.6 結(jié)語(yǔ)和參考文獻(xiàn) 440
14.7 習(xí)題 441
第六部分 人工智能語(yǔ)言與程序設(shè)計(jì)
第15章 PROLOG介紹 447
15.0 簡(jiǎn)介 447
15.1 謂詞演算程序設(shè)計(jì)的語(yǔ)法 447
15.1.1 事實(shí)和規(guī)則的表示 447
15.1.2 創(chuàng)建. 改變和監(jiān)控PROLOG環(huán)境 450
15.1.3 PROLOG的列表和遞歸 451
15.1.4 PROLOG的遞歸搜索 454
15.1.5 在PROLOG中使用cut操作來(lái)控制搜索 455
15.2 PROLOG的抽象數(shù)據(jù)類型 457
15.2.1 ADT堆棧 457
15.2.2 ADT隊(duì)列 458
15.2.3 ADT優(yōu)先隊(duì)列 458
15.2.4 ADT集合 459
15.3 一個(gè)PROLOG產(chǎn)生式系統(tǒng)的例子 460
15.4 設(shè)計(jì)各種搜索策略 464
15.4.1 采用closed列表的深度優(yōu)先搜索算法 464
15.4.2 PROLOG的寬度優(yōu)先搜索 466
15.4.3 PROLOG的最佳優(yōu)先搜索 467
15.5 一個(gè)PROLOG規(guī)劃器 468
15.6 PROLOG的元謂詞. 類型和合一 470
15.6.1 元邏輯謂詞 470
15.6.2 PROLOG的類型 471
15.6.3 合一：用來(lái)啟動(dòng)謂詞匹配和評(píng)估的工具 473
15.7 PROLOG的元解釋器 475
15.7.1 有關(guān)PROLOG的PROLOG 475
15.7.2 基于規(guī)則的專家系統(tǒng)的外殼 478
15.7.3 PROLOG的語(yǔ)義網(wǎng)絡(luò) 485
15.7.4 PROLOG的框架和模式 486
15.8 PROLOG的學(xué)習(xí)算法 488
15.8.1 PROLOG的變型空間搜索 488
15.8.2 候選消除算法 491
15.8.3 PROLOG的基于解釋的學(xué)習(xí) 493
15.9 PROLOG的自然語(yǔ)言處理 495
15.9.1 自然語(yǔ)言處理的語(yǔ)義表示 495
15.9.2 PROLOG的遞歸下降上下文無(wú)關(guān)解析器 496
15.9.3 概率上下文無(wú)關(guān)解析器 498
15.9.4 概率詞匯化上下文無(wú)關(guān)解析器 500
15.9.5 PROLOG上下文相關(guān)解析器 502
15.9.6 PROLOG的遞歸下降語(yǔ)義網(wǎng)解析器 503
15.10 結(jié)語(yǔ)和參考文獻(xiàn) 505
15.11 習(xí)題 507
第16章 LISP介紹 511
16.0 簡(jiǎn)介 511
16.1 基本語(yǔ)法 511
16.1.1 符號(hào)表達(dá)式 511
16.1.2 控制LISP評(píng)估：quote和eval 514
16.1.3 LISP編程：創(chuàng)建新函數(shù) 515
16.1.4 LISP中的程序控制：條件和謂詞 516
16.1.5 函數(shù). 表和符號(hào)計(jì)算 518
16.1.6 表的遞歸結(jié)構(gòu) 520
16.1.7 嵌套表. 結(jié)構(gòu)以及car/cdr遞歸 522
16.1.8 用set綁定變量 524
16.1.9 用let定義局部變量 526
16.1.10 Common LISP中的數(shù)據(jù)類型 527
16.2 LISP中的搜索 528
16.3 高階函數(shù)和抽象 532
16.3.1 映像和過濾器 532
16.3.2 函數(shù)參數(shù)和lambda表達(dá)式 534
16.4 LISP中的搜索策略 534
16.4.1 寬度優(yōu)先和深度優(yōu)先搜索 535
16.4.2 最佳優(yōu)先搜索 537
16.5 LISP中的模式匹配 538
16.6 遞歸合一函數(shù) 539
16.7 解釋器和嵌入式語(yǔ)言 542
16.8 LISP中的邏輯編程 544
16.8.1 一個(gè)簡(jiǎn)單的邏輯編程語(yǔ)言 544
16.8.2 流和流處理 546
16.8.3 基于流的邏輯程序解釋器 547
16.9 流和延遲分析 550
16.10 一個(gè)LISP的專家系統(tǒng)外殼 553
16.10.1 實(shí)現(xiàn)確定性因子 553
16.10.2 lisp-shell的體系結(jié)構(gòu) 554
16.10.3 用lisp-shell分類 557
16.11 LISP中的語(yǔ)義網(wǎng)絡(luò)和繼承 559
16.12 用CLOS的面向?qū)ο蟮木幊?561
16.12.1 CLOS中類和實(shí)例的定義 562
16.12.2 定義通用函數(shù)和方法 564
16.12.3 CLOS中的繼承 565
16.12.4 例子：自動(dòng)調(diào)溫器仿真 566
16.13 LISP中的學(xué)習(xí)：ID3算法 570
16.13.1 用defstruct定義結(jié)構(gòu) 570
16.13.2 ID3算法 575
16.14 結(jié)語(yǔ)和參考文獻(xiàn) 580
16.15 習(xí)題 580
第七部分 后 記
第17章 人工智能是經(jīng)驗(yàn)式的學(xué)科 587
17.0 簡(jiǎn)介 587
17.1 人工智能：修訂的定義 588
17.1.1 人工智能和物理符號(hào)系統(tǒng)假設(shè) 588
17.1.2 連接主義或者“神經(jīng)”計(jì)算 592
17.1.3 主體. 涌現(xiàn)和智能 594
17.1.4 概率模型和隨機(jī)技術(shù) 596
17.2 智能系統(tǒng)科學(xué) 598
17.2.1 心理學(xué)約束 598
17.2.2 認(rèn)識(shí)論問題 600
17.3 人工智能：當(dāng)前的挑戰(zhàn)和未來(lái)的方向 605
17.4 結(jié)語(yǔ)和參考文獻(xiàn) 608
參考文獻(xiàn) 610
作者索引 634
主題索引 ... 640