了得網研究生_人工智能及應用

商品搜索

类别：

关键字：

商品分类

　研究生
　 工学
　 公共课
　 经济管理
　 理学
　 农学
　 文法类
　 医学

　音乐
　 音乐理论

　声乐　通俗音乐　音乐欣赏　钢琴　二胡　小提琴

人工智能及應用
該商品所屬分類：研究生 -> 研究生
【市場價】	297-430元
【優惠價】	186-269元
【作者】	魯斌、劉麗、李繼榮、姜麗梅
【所屬類別】	圖書教材研究生/本科/專科教材工學
【出版社】	清華大學出版社
【ISBN】	9787302450337
【折扣說明】	一次購物滿999元台幣免運費+贈品一次購物滿2000元台幣95折+免運費+贈品一次購物滿3000元台幣92折+免運費+贈品一次購物滿4000元台幣88折+免運費+贈品
【本期贈品】	①優質無紡布環保袋，做工棒！②品牌簽字筆 ③品牌手帕紙巾

版本	正版全新電子版PDF檔
您已选择：	正版全新
溫馨提示：如果有多種選項，請先選擇再點擊加入購物車。 . 電子圖書價格是0.69折，例如了得網價格是100元，電子書pdf的價格則是69元。 . 購買電子書不支持貨到付款，購買時選擇atm或者超商、PayPal付款。付款後1-24小時內通過郵件傳輸給您。 *. 如果收到的電子書不滿意，可以聯絡我們退款。謝謝。

內容介紹

開本：16開

紙張：膠版紙

包裝：平裝-膠訂

是否套裝：否

國際標準書號ISBN：9787302450337

叢書名：高等學校計算機類國家級特色專業繫列規劃教材

作者：魯斌、劉麗、李繼榮、姜麗梅

出版社：清華大學出版社

出版時間：2017年04月

編輯推薦

人工智能是一門涉及內容廣泛、發展迅速的交叉學科，近年來新理論和新方法不斷湧現。本教材作為人工智能科學技術基礎教育的課程內容，主要介紹人工智能的經典理論和方法，討論該學科的*技術和發展動向，反映相關領域的應用成果，為相關學科學生提供人工智能的經典理論、方法和新技術。

內容簡介

本書繫統介紹人工智能的基本原理、方法和應用技術，全面地反映了國內外人工智能研究領域的進展和熱點。全書共11章，主要包括人工智能的基本概念、知識表示技術、搜索策略、邏輯推理技術、不確定性推理方法、專家繫統、機器學習、模式識別、Agent和多Agent繫統、人工智能程序設計語言以及人工智能在電力繫統中的應用。內容由淺入深、循序漸進，條理清晰，各章均有大量的例題和習題，便於讀者掌握和鞏固所學知識，使其具備應用人工智能技術解決實際問題的能力。
本書可用作高等學校計算機類和電氣信息類相關專業高年級本科生和研究生的教材或教學參考書，也可供其他教學、研究、設計和技術開發人員參考。

作者簡介

魯斌，博士，副教授，碩士生導師，中國人工智能學會委員，河北省機器學習學會理事，研究方向主要是人工智能及其在電力繫統中的應用、分布式能源繫統等。

目錄
第1章緒論1
1.1人工智能的基本概念1
1.1.1智能的概念1
1.1.2現代人工智能的興起3
1.1.3人工智能的定義3
1.1.4其他相關的概念4
1.1.5圖靈測試和中文房間問題5
1.2人工智能的發展歷程9
1.2.1孕育期(1956年之前)9
1.2.2形成期(1956—1969年)10
1.2.3發展期(1970年之後)11
1.3人工智能的研究目標13
1.4人工智能的學術流派14

第1章緒論1

1.1人工智能的基本概念1

1.1.1智能的概念1

1.1.2現代人工智能的興起3

1.1.3人工智能的定義3

1.1.4其他相關的概念4

1.1.5圖靈測試和中文房間問題5

1.2人工智能的發展歷程9

1.2.1孕育期(1956年之前)9

1.2.2形成期(1956—1969年)10

1.2.3發展期(1970年之後)11

1.3人工智能的研究目標13

1.4人工智能的學術流派14

1.4.1符號主義、連接主義與行為主義14

1.4.2傳統人工智能與現場人工智能15

1.4.3弱人工智能與強人工智能16

1.4.4簡約與粗陋16

1.5人工智能的研究和應用領域17

1.5.1專家繫統18

1.5.2自然語言理解19

1.5.3機器學習20

1.5.4分布式人工智能20

1.5.5人工神經網絡21

1.5.6自動定理證明22

1.5.7博弈23

1.5.8機器人學23

1.5.9模式識別24

1.5.10自動程序設計24

1.5.11智能控制25

1.5.12智能決策支持繫統25

1.5.13智能電網26

本章小結26

習題27第2章知識表示28

2.1概述28

2.1.1知識概述28

2.1.2知識的性質29

2.1.3知識的分類30

2.1.4知識表示32

2.1.5知識表示觀33

2.2一階謂詞邏輯表示法36

2.2.1一階謂詞邏輯表示法的邏輯基礎36

2.2.2一階謂詞邏輯表示知識的步驟38

2.2.3一階謂詞邏輯表示法的特點40

2.3產生式表示法41

2.3.1產生式表示的方法42

2.3.2產生式繫統的基本結構43

2.3.3產生式繫統的推理方式45

2.3.4產生式表示法的特點48

2.4語義網絡表示法48

2.4.148

2.4.2基本語義關繫49

2.4.3關繫的表示51

2.4.4情況、動作和事件的表示53

2.4.5謂詞連接詞的表示53

2.4.6量詞的表示54

2.4.7基於語義網絡的推理55

2.4.8語義網絡表示法的特點57

2.5框架表示法57

2.5.1框架的一般結構58

2.5.2框架繫統61

2.5.3基於框架的推理61

2.5.4框架表示法的特點63

2.6腳本表示法63

2.6.1概念依賴理論63

2.6.2腳本表示方法64

2.6.3腳本表示法的特點66

2.7過程表示法66

2.7.1陳述性知識表示與過程性知識表示66

2.7.2過程知識表示方法67

2.7.3過程表示的問題求解過程67

2.7.4過程表示的特點68

2.8Petri網表示法69

2.8.1表示知識的方法69

2.8.2Petri網表示法的特點71

本章小結72

習題72第3章搜索策略74

3.1概述74

3.1.1搜索概述74

3.1.2搜索的主要過程75

3.1.3搜索策略的分類75

3.1.4搜索的方向75

3.1.5主要的搜索策略76

3.2狀態空間知識表示方法76

3.2.1狀態空間表示法77

3.2.2狀態空間圖79

3.3狀態空間的盲目搜索81

3.3.1回溯策略82

3.3.2一般的圖搜索策略88

3.3.3深度優先搜索策略92

3.3.4寬度優先搜索策略95

3.4狀態空間的啟發式搜索98

3.4.1啟發性信息與評價函數99

3.4.2A算法101

3.4.3分支界限法104

3.4.4動態規劃法107

3.4.5爬山法108

3.4.6A算法109

3.5與/或圖搜索117

3.5.1與/或圖表示法117

3.5.2與/或圖的搜索策略121

3.5.3與/或樹的搜索策略125

3.6博弈樹搜索131

3.6.1博弈概述131

3.6.2Grundy博弈132

3.6.3極大極小搜索法133

3.6.4α-β剪枝方法134

本章小結136

習題137第4章邏輯推理140

4.1概述140

4.1.1推理和推理方法140

4.1.2推理控制策略140

4.1.3經典邏輯推理141

4.2命題邏輯142

4.2.1命題公式的解釋143

4.2.2等價式143

4.2.3範式144

4.2.4命題邏輯的推理規則145

4.2.5命題邏輯的歸結方法147

4.3謂詞邏輯151

4.3.1謂詞公式的解釋151

4.3.2謂詞等價公式與範式152

4.3.3謂詞邏輯的推理規則155

4.3.4謂詞邏輯的歸結方法156

4.4非單調邏輯164

4.4.1非單調推理164

4.4.2封閉世界假設、限制和小模型165

4.4.3默認邏輯167

4.4.4溯因推理168

4.4.5真值維護繫統169

4.5多值邏輯和模糊邏輯170

本章小結172

習題172第5章不確定性推理175

5.1概述175

5.1.1不確定性推理概述175

5.1.2不確定性的表現176

5.1.3不確定性推理要解決的基本問題177

5.1.4不確定性推理方法的分類179

5.2確定性理論179

5.2.1可信度的基本概念180

5.2.2表示問題180

5.2.3計算問題183

5.2.4帶有閾值限度的不確定性推理185

5.2.5帶有權重的不確定性推理187

5.2.6確定性理論的特點188

5.3主觀Bayes方法188

5.3.1證據不確定性的表示188

5.3.2知識不確定性的表示189

5.3.3組合證據的不確定性191

5.3.4結論不確定性的更新192

5.3.5結論不確定性的合成193

5.3.6主觀Bayes方法的特點195

5.4證據理論195

5.4.1D\\|S理論195

5.4.2一個特殊的概率分配函數200

5.4.3表示問題203

5.4.4計算問題203

5.4.5證據理論的特點206

5.5貝葉斯網絡206

5.5.1貝葉斯網絡概述207

5.5.2基於貝葉斯網絡的不確定性知識表示208

5.5.3基於貝葉斯網絡的推理模式209

5.5.4基於貝葉斯網絡的不確定性推理的特點211

5.6模糊推理211

5.6.1模糊理論的基本概念212

5.6.2表示問題218

5.6.3計算問題219

5.6.4模糊推理的特點226

本章小結226

習題227第6章專家繫統229

6.1概述229

6.1.1專家繫統發展歷程229

6.1.2專家繫統特點230

6.1.3專家繫統的類型231

6.1.4新型專家繫統233

6.2專家繫統結構234

6.3專家繫統設計237

6.3.1專家繫統的設計步驟237

6.3.2知識獲取239

6.3.3知識庫設計和知識管理241

6.3.4推理機設計243

6.3.5解釋功能設計244

6.3.6繫統結構設計245

6.3.7專家繫統的評價245

6.4專家繫統應用案例246

6.4.1動物識別專家繫統246

6.4.2PROSPECTOR繫統249

6.5開發工具與環境251

6.5.1程序設計語言252

6.5.2骨架繫統252

6.5.3知識表示語言253

6.5.4輔助型工具254

6.5.5專家繫統開發環境254

本章小結255

習題255第7章機器學習256

7.1概述256

7.1.1機器學習的定義256

7.1.2機器學習的發展257

7.1.3機器學習分類259

7.1.4歸納學習260

7.2決策樹學習261

7.2.1決策樹261

7.2.2決策樹構造算法263

7.2.3決策樹的歸納偏置264

7.3變型空間學習266

7.3.1泛化和特化266

7.3.2候選刪除算法268

7.4基於解釋的學習271

7.4.1基本概念271

7.4.2基於解釋的學習方法272

7.5人工神經網絡274

7.5.1基本概念275

7.5.2感知器280

7.5.3多層神經網絡282

7.5.4Hopfield神經網絡287

7.5.5雙向相關記憶290

7.5.6自組織神經網絡293

7.6進化計算298

7.6.1模擬自然進化298

7.6.2遺傳算法299

7.6.3進化策略304

7.6.4遺傳編程305

本章小結307

習題308第8章模式識別310

8.1概述310

8.1.1模式識別的發展與應用310

8.1.2模式識別繫統311

8.1.3模式識別方法314

8.1.4模式識別實例317

8.2線性分類器319

8.2.1感知器準則320

8.2.2小均方誤差320

8.2.3Fisher準則321

8.2.4支持向量機323

8.3貝葉斯決策理論327

8.3.1小錯誤貝葉斯決策規則327

8.3.2小風險貝葉斯決策規則328

8.3.3正態分布的貝葉斯分類329

8.3.4密度估計的參數法330

8.3.5密度估計的非參數法331

8.4聚類分析333

8.4.1動態聚類法333

8.4.2層次聚類法334

本章小結335

習題336第9章Agent和多Agent繫統337

9.1概述337

9.2Agent理論 339

9.2.1Agent的基本概念339

9.2.2Agent的特性340

9.2.3Agent的內部結構341

9.2.4Agent類型344

9.2.5Agent的實現工具345

9.3多Agent繫統346

9.3.1多Agent的結構模型346

9.3.2通信方式348

9.3.3通信語言349

9.3.4協調與協作350

9.4MAS的應用案例354

9.5Agent技術應用355

本章小結357

習題357第10章人工智能程序設計語言358

10.1概述358

10.1.1LISP語言簡介358

10.1.2PROLOG語言簡介359

10.2表處理語言LISP359

10.2.1LISP素360

10.2.2LISP的運行機制360

10.2.3LISP的基本函數361

10.2.4LISP的表處理364

10.2.5LISP的應用實例369

10.3邏輯程序設計語言PROLOG373

10.3.1Horn子句373

10.3.2PROLOG程序的語句374

10.3.3PROLOG的推理機制374

10.3.4PROLOG的表結構376

10.3.5PROLOG的應用實例378

本章小結382

習題383第11章人工智能在電力繫統中的應用384

11.1概述384

11.2人工智能在電力繫統故障診斷中的應用385

11.2.1電網故障診斷原理386

11.2.2貝葉斯網絡建模388

11.2.3貝葉斯網絡故障診斷推理388

11.2.4改進的貝葉斯網絡故障診斷模型389

11.2.5其他智能故障診斷技術的應用390

11.3人工智能在電力巡檢中的應用391

11.3.1電力設備巡檢391

11.3.2巡檢機器人392

11.3.3繫統實時監控後臺393

11.3.4路徑規劃管理395

11.3.5設備狀態識別396

11.3.6Agent技術397

11.4人工智能在電力大數據分析中的應用400

11.4.1大數據基本概念400

11.4.2電力大數據的來源401

11.4.3大數據分析與人工智能402

11.4.4電力大數據分析典型應用場景403

本章小結406參考文獻407

前言

作為世界三大尖端技術之一，人工智能（Artificial Intelligent）自1956年誕生之日起，就成為科學發展史上一顆令人矚目的新星，吸引著無數科學工作者從事相關的研究與創造。人工智能是一門新理論、新技術、新方法和新思想不斷湧現的前沿交叉學科，與計算機科學、控制論、信息論、神經生理學、哲學、語言學等密切相關，研究領域除了經典的知識表示、啟發式搜索理論、推理技術、人工智能繫統和語言之外，還涉及專家繫統、自然語言理解、機器學習、博弈、機器人學、模式識別、智能檢索、自動程序設計、數據挖掘、計算機視覺、分布式人工智能、人工神經網絡、智能控制、智能決策支持繫統、智能電網等領域，相關研究成果也已廣泛應用到生產、生活的各個方面。我們所處的時代是知識爆炸的時代，各種海量信息充斥著世界各個角落，而僅僅依靠人類自身，很難實現對這些信息的有效處理。人工智能作為一門研究和制造智能機器或智能繫統的學科，目標在於模擬和延展人類的智能，這與當今時代發展的需求是不謀而合的。因此，培養更多高水平的人工智能技術人纔迫在眉睫。本書是一本綜合、全面、實用的教材，反映了作者多年來的教學思路和經驗，具有內容全面、重點突出、層次分明、特色鮮明等特點，具體體現在以下各方面。(1) 內容全面。本書詳細介紹了人工智能研究中的經典理論和方法，而且對專家繫統、機器學習、模式識別、分布式人工智能等也有較為全面的概括和說明，有利於幫助相關讀者充分掌握人工智能的基本理論，並為其後續深入研究奠定扎實基礎。(2) 重點突出。本書定位為人工智能的入門級教材，因此重點放在啟發式搜索、推理、知識表示、人工智能繫統和語言等經典理論、方法和技術，並對如模式識別、多智能體、機器學習等發展相對成熟的人工智能熱點和重點研究領域有較為全面的介紹和說明，有助於讀者循序漸進地了解這門學科。(3) 層次分明。本書在章節安排上結合了智能繫統構建的過程，首先介紹知識表示技術和方法，然後引入各種搜索技術、推理技術和其他研究熱點，後通過實例對人工智能的應用詳細說明，層次分明，有利於幫助讀者理解這一學科的發展研究初衷。(4) 特色鮮明。電力行業是關繫國計民生的基礎性行業，隨著電力市場化以及電網建設的進一步發展，人工智能相關技術對電力信息化、智能化發展的重要促進作用也逐步凸現，編者結合自身的研究工作，對近年人工智能在電力繫統中的應用進行了介紹，特色鮮明，尤其適合具有“大電力”研究背景的讀者。讀完本書並且親自動手實踐了書中的人工智能程序之後，讀者將能夠做到以下幾點。(1) 熟悉人工智能的發展概況、研究內容和應用領域等，對人工智能這個學科有較為全面和深入地理解。(2) 扎實地掌握人工智能的基礎理論、基本原理和經典算法等，具備運用基本人工智能方法解決實際問題的能力。(3) 熟悉人工智能的研究熱點和成果，了解應用人工智能技術解決實際問題的基本思路，掌握一定的人工智能新技術和新方法，能很快地開展相關領域的深入研究。本書共11章，在內容安排上可以劃分為三大部分。部分詳細介紹了人工智能的核心研究課題，第二部分闡述了一些人工智能的基本技術和方法，第三部分介紹了人工智能在實際生產生活中，尤其是在電力行業中的應用，內容編排體現了人工智能這一學科的發展脈絡。第1章為緒論，介紹了人工智能的基本概念、發展歷史、研究目標、研究途徑以及研究領域等。第2章為知識表示，討論了人工智能的典型知識表示技術，以及基於這些知識表示技術的推理方法等。第3章為搜索策略，主要討論狀態空間圖的盲目搜索、啟發式搜索、與/或圖搜索和博弈樹搜索等。第4章為邏輯推理，對命題邏輯、謂詞邏輯、非單調邏輯、多值邏輯和模糊邏輯及其推理技術作了介紹，重點給出了歸結原理的基本原理和應用方法。第5章為不確定性推理，討論了確定性理論、主觀Bayes方法、證據理論、貝葉斯網絡、模糊推理等不確定性推理技術。第6章為專家繫統，給出了專家繫統構建的基本原理、方法和實例。第7章為機器學習，討論了有關機器學習的基本概念，以及一些重要的機器學習方法，主要包括決策樹學習、變型空間學習、基於解釋的學習、人工神經網絡和進化計算等。第8章為模式識別，主要介紹統計模式識別方法，並對其他模式識別技術如結構模式識別方法、模糊模式識別方法、神經網絡識別方法加以概述。第9章為Agent和多Agent繫統，從分布式人工智能的概念出發，介紹Agent基本理論、多Agent繫統的體繫結構、通信機制以及協調協作機制，為分布式繫統的分析、設計、實現和應用提供解決方法。第10章為人工智能程序設計語言，對人工智能程序設計語言的研究發展進行了概述，並詳細討論了LISP和PROLOG兩種程序設計語言。第11章為人工智能在電力繫統中的應用，給出了人工智能在電力繫統故障診斷、電力巡檢和電力大數據分析中的應用實例。本書參編人員包括魯斌、劉麗、李繼榮和姜麗梅。在本書編寫過程中參閱了國內外大量的文獻資料，在此謹向這些文獻的作者表示由衷的敬意和感謝。由於編者水平有限，尤其是人工智能這門學科發展很快，不斷有新的技術和方法湧現，書中難免有不足之處，懇請廣大讀者批評指正。本書可用作高等學校計算機類和電氣信息類相關專業高年級本科生和研究生的教材或教學參考書，也可供其他教學、研究、設計和技術開發人員參考。
編者2017年3月

媒體評論

評論

在線試讀

第3章搜索策略在進行問題的智能求解時，一般會涉及兩個部分。部分是問題的表示，也就是把待求解的問題表示出來。如果一個問題找不到一種合適的表示方法，對它的求解也就無從談起。在第2章中已經討論過各種知識表示技術，可以基於這些技術表示待求解的問題。第二部分是問題的具體求解，即針對問題，分析其特征，選擇一種相對合適的方法進行求解。目前問題求解的基本方法有搜索法、歸約法、歸結法、推理法、約束滿足法、規劃和產生式、模擬退火法、遺傳算法等。本章主要討論問題的搜索求解策略，即采用搜索法求解問題時怎樣表示問題、怎樣基於具體的搜索策略解決問題。3.1概述搜索是人工智能的經典問題之一，它與推理密切相關，搜索策略的優劣直接影響智能繫統的性能。以下給出搜索的概念，並對搜索的基本過程、控制策略以及搜索策略的分類等做一個簡單的介紹。3.1.1搜索概述人工智能所要解決的問題大多數是結構不良或非結構化的問題。對於這樣的問題，一般很難獲得其全部信息，也沒有成熟的求解算法可供利用，問題求解隻能依靠經驗，利用已有的知識一步步地摸索著前進。例如，對於醫療診斷的智能繫統，基於已知的初始癥狀，需要在規則庫中尋找可以使用的醫療知識，逐步診斷出患者的疾病，這就存在按照何種線路進行診斷的問題。另外，從初始的癥狀到後疾病的判斷可能存在多條診斷路線，這就存在按照哪條路線進行診斷可以獲得較高求解效率的問題。像這種根據問題的實際情況，不斷尋找可以利用的知識，從而構造出一條代價較少的推理路線，使得問題得到圓滿解決的過程稱為搜索。人工智能進行問題求解時，即使對於結構性能較好，理論上也有算法可依的問題，如果問題本身或算法的復雜性較高(如按照指數級增長)，同時受計算機在時間和空間上的限制，會產生人們常說的組合爆炸問題。例如，64階漢諾塔問題有364種狀態，僅從空間上看，這是任何計算機都無法存儲的問題。再如，在實現一個能進行人機對弈的智能繫統時，計算機為了取得勝利，需要考慮所有的可能性，然後選擇的走步方式，設計這樣的算法並不困難，但卻需要計算機驚人的時間和空間代價。對於這種雖然理論上有算法但卻無法付諸實現的問題，有時也需要通過搜索策略來解決。搜索中需要解決的基本問題有以下幾個。(1) 搜索過程是否一定能找到一個解？(2) 搜索過程是否能終止運行？或是否會陷入一個死循環？(3) 當搜索過程找到一個解時，找到的是否是解？(4) 搜索過程的時間和空間復雜性如何？我們曾經遇到過的走迷宮問題、旅行商問題、八數碼問題等，都是很經典的搜索問題，後文會基於這些典型問題的求解，探討不同的搜索策略及其特征。3.1.2搜索的主要過程不同的搜索策略，搜索的具體步驟並不一樣，但它們都具有以下主要過程。(1) 從初始狀態或目標狀態出發，並把它們作為當前狀態。(2) 掃描操作算子集(操作算子用於實現狀態的轉換)，將適用於當前狀態的一些操作算子作用於當前狀態得到新的狀態，並建立指向其父結點的指針。(3) 檢查所生成的新狀態是否滿足結束狀態？如果滿足，則得到問題的一個解，並可以沿著有關指針從結束狀態逆向到達開始狀態，給出這一解的路徑；否則，將新狀態作為當前狀態，返回第(2)步再進行搜索。3.1.3搜索策略的分類可以根據搜索過程中是否使用了啟發性的信息將搜索分為盲目搜索和啟發式搜索兩種類型。盲目搜索，也稱無信息引導的搜索，是指沒有利用和問題相關的知識，按照預定的控制策略進行搜索，在搜索過程中獲得的中間信息也不用來改進控制策略。由於搜索總是按照預先設定的路線進行，沒有考慮待求解問題本身的特性，因此這種搜索具有盲目性，效率不高，不擅長解決復雜問題。但盲目搜索具有通用性，當一時難以找到待求解問題的有效知識時，是一種不得不采用的方法。啟發式搜索，也稱有信息引導的搜索，它與盲目搜索正好相反，在搜索中加入了與問題有關的啟發性信息，用以指導搜索朝著有希望的方向前進，加速了問題求解的過程，以盡快找到()解。啟發式搜索由於利用了問題的有關知識，一般來說，問題的搜索範圍會有所縮小，搜索效率會有所提高。但如何找到對問題求解有幫助的知識，以及如何利用這些知識，是啟發式搜索的關鍵和難點。根據問題的表示方式，也可以將搜索分為狀態空間搜索和與/或圖搜索。由於涉及的細節較多，這裡不做過多闡述，狀態空間搜索策略將在3.2節～3.4節詳細討論，與/或圖搜索策略則放在3.5節、3.6節說明。 3.1.4搜索的方向搜索可以沿著兩個方向進行，即正向搜索和逆向搜索。1. 正向搜索正向搜索指從初始狀態出發的搜索，也稱為數據驅動的搜索。它從問題給出的條件和一個用於狀態轉換的操作算子集出發，不斷應用操作算子從給定的條件中產生新的條件，再用操作算子從新條件中產生更多的新條件，直到有滿足目標要求的解產生為止。2. 逆向搜索逆向搜索指從目標狀態出發的搜索，也稱為目標驅動的搜索。它從想要達到的目標入手，看哪些操作算子能產生該目標，以及應用這些操作算子產生該目標時需要哪些條件，這些條件就成為想要達到的新目標，即子目標。通過反向搜索不斷尋找子目標，直到找到問題給定的條件為止，這樣就找到了從初始狀態到目標狀態的解，盡管搜索方向和解正好相反。究竟采用正向搜索還是逆向搜索，一般應該考慮以下3個因素。(1) 初始狀態和目標狀態中，哪個狀態多？一般從小的狀態集合出發朝大的狀態集合搜索，這樣問題求解更容易一些。(2) 正向搜索和逆向搜索哪個分支因素低？一般朝著分支因素低的方向進行搜索。分支因素是指從一個結點出發可以直接到達的平均結點數。(3) 選擇搜索方向時還可以考慮操作算子的數目和復雜性、狀態空間的形狀和人們的思考方法等。當然，也可以將正向搜索和逆向搜索結合起來構成雙向搜索，即兩個方向同時進行，直到在中間的某處彙合為止。3.1.5主要的搜索策略到目前為止，人工智能領域已經出現了很多具體的搜索方法，概括起來有以下幾種。1. 求任一解的搜索策略(1) 回溯法(BackTracking)。(2) 爬山法(Hill Climbing)。(3) 寬度優先法(Breadthfirst)。(4) 深度優先法(Depthfirst)。(5) 限定範圍搜索法(Beam Search)。(6) 優先法(Bestfirst)。2. 求解的搜索策略(1) 大英博物館法(British Museum)。(2) 分支界限法(Branch and Bound)。(3) 動態規劃法(Dynamic Programming)。(4) 圖搜索法(A)。3. 求與/或關繫解圖的搜索法(1) 一般與/或圖搜索法(AO)。(2) 極小極大法(Minimax)。(3) α\\|β剪枝法(Alpha\\|beta Pruning)。(4) 啟發式剪枝法(Heuristic Pruning)。本章將對其中幾個基本的搜索策略做進一步討論。3.2狀態空間知識表示方法人工智能雖然有很多研究領域，而且每個研究領域又有自己的特點和規律，但從它們解決實際問題的過程來看，都可以歸納抽像成一個“問題求解”的過程。采用搜索法進行問題求解時，首先必須采用某種知識表示技術將待求解的問題表示出來，其表示方法是否恰當將直接影響問題求解的效率。本節介紹的狀態空間表示法和後文將要介紹的與/或圖表示法是兩種基本的知識表示方法，可以用來表示問題及其求解過程。考慮到它們和搜索問題的密切關繫，以及搜索問題在人工智能研究中的核心地位，將這兩種知識表示技術放在本章詳細討論，而沒有將它們同謂詞邏輯、產生式、語義網絡等知識表示技術一起放在“第2章知識表示”中單獨說明。3.2.1狀態空間表示法狀態空間表示法是用“狀態”和“操作”來表示和求解問題的一種方法。其中，“狀態”用來描述問題求解過程中的各種情況，“操作”用來實現“狀態”之間的轉換。1. 狀態狀態(State)是描述問題求解過程中每一步問題狀況的數據結構，一般采用以下形式表示，即Sk=(Sk0,Sk1,…)其中，當對每一個分量Ski賦予一個確定的值時，就得到了一個具體的狀態。在實際問題求解時，可以采用任何恰當類型的數據結構來描述狀態，如符號、字符串、向量、多維數組、樹和表格等，使之有利於問題的解決。2. 操作操作(Operator)，也稱為算符，是將問題從一個狀態轉換為另一個狀態的手段。當對一個狀態使用某個可用的操作時，會引起該狀態中某些分量的值的變化，導致問題從這個狀態轉換為另一個狀態。簡單地說，操作可以看成是狀態集合上的一個函數，它描述了狀態之間的關繫。操作可以是一個運算、一條規則、一個過程或一個機械步驟。例如，在產生式繫統中，操作實際就是一條條的產生式規則。3. 狀態空間狀態空間(State Space)是由問題的全部狀態和全部可用操作構成的集合，它描述了問題的所有狀態和它們之間的相互關繫，一般用組表示，即(S,O,S0,G)其中，S是狀態集合，S中的素表示一個狀態； O是操作的集合，O 中的素表示一個操作； S0 是問題的初始狀態集合，是 S 的非空子集，S0S ； G 是問題的目標狀態集合，是 S 的非空子集，GS，G 可以是若干具體的狀態，也可是滿足某些性質的路徑信息描述。從S0結點到G結點的路徑被稱為求解路徑。圖31八數碼問題的一個狀態狀態空間的一個解是一個有限操作算子序列，它使初始狀態轉化為目標狀態，即S0O1S1O2S2O3…OkG其中，Oi為操作算子，O1,O2,O3,…,Ok是狀態空間的一個解。解也可以用對應的狀態序列來表示。當然，解往往不是的。例31八數碼問題的狀態空間表示。八數碼問題(重排九宮問題)是在圖31所示的3×3的方格棋盤上，放置8張標記為1～8的將牌，還有一個空格，空格四周上下左右的將牌可以移動到空格中。需要找到一種將牌移動的方式，使8張將牌的排列由某種情況轉換為另一種情況。用狀態空間表示法表示八數碼問題。【解】現對八數碼問題的狀態空間表示中狀態、操作和狀態空間的形式進行說明。(1) 8張將牌的任何一種排列方式都是一種狀態，所有的排列方式構成了狀態集合S，其大小為9!個。(2) 操作是進行狀態變換的手段，可以從兩個角度進行設計。從將牌的角度看，操作可以是對將牌的移動，每張將牌可以有上、下、左、右4個移動方向，一共有8張將牌，因此操作算子共有4×8=32個；從空格的角度看，操作也可以看成是對空格的移動，空格可以有上、下、左、右4個移動方向，而且隻有1個空格，因此操作算子共有4×1=4個，即空格上移Up、空格下移Down、空格左移Left和空格右移Right。顯然後一種操作的設計方式更為簡單。值得注意的是，並不是任何狀態都可以使用這4個操作，對某個狀態實施操作時還要確保空格不會被移出方格棋盤之外。例如，當空格在左下角時，隻有兩個操作可以使用，它們是空格上移Up和空格右移Right。同理，如果從將牌移動的角度設計操作，也並不是任何狀態都可以使用32個操作，畢竟隻有和空格相鄰的將牌纔能移動。(3) 狀態空間描述了問題所有的狀態和它們之間的關繫組(S,O,S0,G)中，狀態集合與操作集合都已在上面說明，問題的初始狀態集合S0和目標狀態集合G可以是需要的任何布局，如圖32就是其中的一種。在搜索問題中，其實就是要尋找到一個將牌移動的序列(操作序列)，使得問題由初始狀態變換為目標狀態。圖32八數碼問題的初始狀態和目標狀態例32二階漢諾塔問題的狀態空間表示。假設有編號為1號、2號和3號的3個鋼針，初始情況下，1號鋼針上穿有A和B兩個金片，A比B小，A位於B的上面。要求通過金片的移動將A和B移動到另外一根鋼針上，規定每次隻能移動一個金片，而且任何時刻都不能使大的金片位於小的金片上方。問題的初始狀態和目標狀態如圖33所示。圖33二階漢諾塔問題的初始狀態和目標狀態【解】現對漢諾塔問題用狀態空間表示法表示時，狀態、操作和狀態空間的形式進行說明。(1) 兩個金片任意一種合法的放置方式都是一種狀態，假設狀組Sk=(Sk0,Sk1)表示，其中Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。如S0=(1,1)表示A片在1號鋼針上，B片也在1號鋼針上，且A片在B片上面。(2) 問題全部可能的狀態一共有9種，即S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)如圖34所示。它們構成了狀態集合 S，其大小為9個。圖34二階漢諾塔問題的所有狀態(3) 初始狀態集合為{S0}，目標狀態集合為{S4,S8}。(4) 操作是進行狀態變換的手段，分別用A(i,j)和B(i,j)表示，其中A(i,j)表示把A片從第i號鋼針移動到第j號鋼針上，B(i,j)表示把B片從第i號鋼針移動到第j號鋼針上。操作共有12種，它們分別是: A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2) B(1,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)在進行問題求解時，應當注意保證狀態的合法性，即保證操作算子使用後不會使大的金片位於小的金片上方。(5) 狀態空間描述了問題所有的狀態和它們之間的關繫，狀態集合、操作集合、初始狀態集，目標狀態集在上面都已說明。在搜索問題中，其實就是要尋找到一個移動金片的操作序列，使得問題由初始狀態變換為目標狀態。3.2.2狀態空間圖狀態空間可以用有向圖來描述，因為圖是直觀的。圖中的結點表示問題的狀態，圖中的有向弧表示狀態之間的關繫，也就是操作。進行問題求解時，初始狀態對應實際問題的已知信息，是圖的根結點。問題求解就是尋找從初始狀態轉換為目標狀態的某個操作算子序列，也就是尋找從初始狀態到目標狀態的一條路徑。因此，問題的解又可以很形像地稱為解路徑。和操作算子序列對應的，問題的解也可以是一個合法狀態的序列，其中序列的個狀態是問題的初始狀態，後一個狀態是問題的結束狀態。介於初始狀態和結束狀態之間的則是中間狀態。除了個狀態外，該序列中任何一個狀態，都可以通過一個操作，由與它相鄰的前一個狀態轉換得到。在圖35所示的狀態空間圖中，初始狀態集合為{S0}，目標狀態集合為{S12}，有向弧上的標識說明了相應的操作算子。通過利用操作算子對狀態進行轉換，可以找到從初始狀態到目標狀態的一個解，即O2、O6、O12，或者用狀態的序列表示為S0、S2、S6、S12。圖35狀態空間的有向圖示例在某些問題中，各操作算子的執行代價不同，這時隻需要在圖中給各弧線標注代價即可。一般來說，實際待求解問題的規模是比較大的，即問題所有可能出現的狀態數是比較多的。當問題有解時，如何縮小搜索範圍，快速有效地找到問題的解，甚至是問題的解，正是搜索問題所要研究和探討的。不難想像，對同一個問題來說，采用不同的搜索策略，找到解的搜索空間是有區別的。一般來說，對大空間問題，搜索策略就是要解決組合爆炸的問題。例33旅行商問題(Traveling Salesman Problem，TSP)的狀態空間圖。假設一個推銷員從圖36所示的A城市出發，到其他所有城市去推銷產品，終再回到出發地A城市，需要找到一條路徑，能使推銷員訪問每個城市後回到出發地經過的路徑短或費用較少。各個城市之間的距離(或費用)標注在弧線上。圖36旅行商問題圖37描述了旅行商問題的部分狀態空間圖。下方的表格裡列出了各條路徑及其耗散(代價)。圖37旅行商問題的部分狀態空間圖在前面的例子中，都可以畫出問題的全部狀態空間圖，即使對於例33的五城市旅行商問題而言，雖然隻畫出了狀態空間圖的一部分，但將其補充完整是可能的。但是，如果是80個城市的旅行商問題，要在有限時間畫出問題的全部狀態空間圖難度卻很大，因此，這類顯示的描述對於復雜問題來說是不切實際的，而對於包含無限結點的問題更是不可能的，此時，一個問題的狀態空間是客觀存在的，隻不過組之類的隱式描述而已。3.3狀態空間的盲目搜索盲目搜索的過程中由於沒有利用與問題有關的啟發性知識，其搜索效率可能不如啟發式搜索，但由於啟發式搜索需要啟發性信息，而啟發性信息的獲取和利用一般比較困難，因此在難以獲取啟發性信息的情況下，盲目搜索不失為一種比較好的選擇。本節主要討論狀態空間的盲目搜索策略。3.3.1回溯策略前面已經分析過，尋找從初始狀態到目標狀態的解路徑實際就是在狀態空間中尋找從初始狀態到目標狀態的一個操作序列，如果在尋找這個操作序列時，繫統能給出一個可靠或正確的選擇策略，那就不需要搜索了，求解會一次性成功穿過狀態空間到達目標狀態，得到解路徑。但對於實際問題來說，不可能存在這樣一個可靠的預測，求解必須通過不斷地嘗試，直到找到目標狀態為止。回溯策略就是一種繫統地嘗試狀態空間中不同路徑的搜索技術。以下將給出回溯策略的算法描述和基於此策略的搜索實例。1. 一個基本的回溯策略回溯策略是一種用於狀態空間搜索的盲目搜索策略。其主要思想簡單來說是: 首先將問題所有的規則(即操作、操作算子)給出一個固定的排序，在搜索時對當前狀態(剛開始搜索時，當前狀態就是初始狀態)依次檢測規則集中的每一條規則，在當前狀態未使用過的規則集中找到條可以觸發的規則，應用於當前狀態，得到一個新的狀態，新狀態重新設置為當前狀態，並重復以上搜索。如果對當前狀態而言，沒有規則可用，或者所有的規則都已經被試探過但仍然沒有找到問題的解，則將當前狀態的前一個狀態(即當前狀態的父狀態)設置為當前狀態，重復以上搜索。如此進行下去，直到找到問題的解，或者試探了所有可能後仍找不到問題的解為止。基於回溯策略進行搜索的過程明顯呈現出遞歸的性質，其主要過程如下面的StepTrack。其返回值有兩種情況: 如果從當前狀態Data到目標狀態有路徑存在，則返回以規則序列(操作序列)表示的從Data到目標狀態的解路徑；如果從當前狀態Data到目標狀態沒有路徑存在，則返回Fail。遞歸過程StepTrack(Data)如下。(1) If Goal(Data) Then Return Nil;Goal(Data)返回值為真,表示Data是目標狀態,即找到目標,過程返回空表Nil(2) If Deadend(Data) Then Return Fail;Deadend(Data)返回值為真,表示Data是非法狀態,過程返回Fail,即需要回溯(3) Rules :=Apprules(Data);如果Deadend(Data)返回值為假,執行Apprules函數,計算Data所有可應用的規則,再按照某種原則排列後賦給Rules(4) Loop: If Null(Rules) Then Return Fail;Null(Rules)返回值為真,表示規則用完未找到目標或根本沒有可應用的規則,過程返回Fail,即需要回溯(5) R :=First(Rules);取頭條可應用的規則(6) Rules :=Tail(Rules);刪去頭條規則,更新未被使用的規則集(7) Newdata :=Gen(R,Data);調用規則R作用於當前狀態,生成新狀態(8) Path :=StepTrack(Newdata);對新狀態遞歸調用本過程(9) If Path=Fail Then Go Loop Else Return Cons(R,Path);當Path=Fail時,表示遞歸調用失敗,沒有找到從Newdata到目標的解路徑,轉移到Loop處調用下一條規則進行測試;否則過程返回解路徑遞歸過程StepTrack(Data)將遞歸和循環結合在一起，實現了解路徑的縱向和橫向搜索。如圖38所示，如果當前狀態A不是目標狀態，則對它個子狀態B調用回溯過程StepTrack(B)，在StepTrack(B)中，又首先對B的個子狀態E調用回溯過程StepTrack(E)，…，這是一種縱向的搜索，依靠遞歸來實現。如果在以B為根的子圖中沒有找到目標狀態，就對B的兄弟狀態C調用回溯過程StepTrack(C)，如果在以C為根的子圖中沒有找到目標狀態，就對B和C的兄弟狀態D調用回溯過程StepTrack(D)，…，這是一種橫向的搜索，依靠循環來實現。圖38給出了一個狀態空間中搜索A到D的解路徑的回溯搜索過程，圖中虛線箭頭指出了搜索的軌跡，結點旁邊的數字說明了該結點被搜索到的次序。圖38回溯搜索示意圖算法StepTrack(Data)有以下幾點需要注意。(1) 當某一個狀態t滿足結束條件時，算法在第(1)步結束並返回Nil，此時StepTrack(t)的返回值為Nil，即t到目標狀態的解路徑是一張空的規則表。(2) 算法返回Fail發生在第(2)和第(4)步，第(2)步由於不合法狀態返回Fail，第(4)步由於所有規則都試探失敗返回Fail。一旦返回Fail，意味著過程會回溯到上一層繼續運行，而在層返回Fail則整個過程失敗退出。(3) 如果找到解路徑，算法在第(9)步通過Cons函數構造出解路徑。例34N皇後問題的回溯實現。在一個N×N的國際像棋棋盤上，依次擺放N個皇後棋子，擺好後要求滿足每行、每列和每個對角線上隻允許出現一個皇後，即皇後之間不許相互俘獲。圖39給出4皇後問題的幾種擺放方式，其中a和b滿足擺放要求，皇後在行、列和對角線上均沒有衝突，而c、d、e和f為非法狀態，c中有列的衝突，d中有行的衝突，e中是4×4棋盤的主對角線衝突，f則是一個較短對角線(3×3的棋盤上)的衝突。圖39皇後問題的合法狀態和非法狀態對於4皇後問題，求解前首先給所有規則排序，這裡的規則就是操作算子，是擺放皇後的方法。假設皇後擺放的次序為棋盤上從左到右，從上到下，依次為r11、r12、r13、r14、r21、r22、r23、r24、r31、r32、…、r44，其中rij表示將一個皇後放置在第i行第j列。問題的狀態用一個表來表示，如圖39中的a圖為(12 24 31 43)，每個分量表示一個皇後所在的行列編號，由於4皇後問題中多有4個皇後，所以表中多有4個分量。根據StepTrack的基本流程，可以得到圖310所示的搜索圖。其中，為簡單起見，每個狀態隻寫出其增量部分。由圖中向上的箭頭可知，為了解決問題，共進行了22次回溯。圖3104皇後問題的回溯搜索2. 一個改進的回溯策略在遞歸過程StepTrack(Data)中，第(2)步和第(4)步設置了兩個回溯點，一個是非法狀態回溯，一個是試探了一個狀態的所有子狀態後，仍然找不到解時回溯。然而，對於某些問題還可能會遇到其他一些情況，StepTrack(Data)無法解決。例如，如果問題的狀態空間圖中有某個分支可以向縱深無限深入進去，即這個分支是一個“無限深淵”，StepTrack(Data)可能會落入這個“深淵”中永遠回溯不回來，這樣，即使問題在旁邊的分支上有解，算法一旦落入這個無限深淵中就不能找到這個解。又如，問題的狀態空間圖的某一個分支上具有環路，搜索一旦進入這個環路就會陷入無限循環，在這個環路中一直搜索，同樣也回溯不回來，這樣，即使問題在旁邊的分支上有解，也不可能找到這個解。為了解決這兩個問題，可以對StepTrack(Data)做一些改進，通過增加回溯點的方法解決“無限深淵”與“環路”的問題。下面給出的算法StepTrack1，它將StepTrack增加了兩個回溯點: 一個是超過深度限制Bound的回溯點，一旦發現當前結點的深度超過深度限制，強制回溯；另一個是出現環路的回溯點，算法記錄了從初始結點到當前結點的搜索路徑，一旦發現當前結點已經在搜索路徑上出現過，就說明有環路存在，強制回溯。StepTrack1的返回值和StepTrack一樣，有兩種情況: 如果從當前狀態Data到目標狀態有路徑存在，則返回以規則序列表示的從Data到目標狀態的解路徑；如果從當前狀態Data到目標狀態沒有路徑存在，則返回Fail。而且，為了處理環路的問題，StepTrack1的形參由原先StepTrack的當前狀態Data換為從初始狀態到當前狀態的逆序表Datalist，即初始狀態排在表的後，而當前狀態排在表的前面。遞歸過程StepTrack1(Datalist)如下。(1) Data:=First(Datalist);設置Data為當前狀態(2) If Member(Data,Tail(Datalist)) Then Return Fail;函數Tail是取尾操作,Tail(Datalist)表示取Datalist中素以外素。Member(Data,Tail(Datalist))取值為真,表示Data在Tail(Datalist)中存在,即有環路出現,過程返回Fail,需要回溯(3) If Goal(Data) Then Return Nil;Goal(Data)返回值為真,表示Data是目標狀態,即找到目標,過程返回空表Nil(4) If Deadend(Data) Then Return Fail; Data是非法狀態,過程返回Fail,即需要回溯(5) If Length(Datalist) Bound Then Return Fail;函數Length計算Datalist的長度,即搜索的深度,當搜索深度大於給定常數Bound時,返回Fail,即需要回溯(6) Rules:=Apprules(Data);執行Apprules函數,計算Data所有可應用的規則,再按照某種原則排列後賦給Rules(7) Loop: If Null(Rules) Then Return Fail;Null(Rules)返回值為真,表示規則用完未找到目標或根本沒有可應用的規則,返回Fail,即需要回溯(8) R:=First(Rules);取頭條可應用的規則(9) Rules:=Tail(Rules);刪去頭條規則,更新未被使用的規則集(10) Newdata:=Gen(R,Data);調用規則R作用於當前狀態,生成新狀態(11) Newdatalist:=Cons(Newdata,Datalist);將新狀態加入到表Datalist前面,構成新的狀態列表(12) Path:=StepTrack1(Newdatalist);遞歸調用本過程(13) If Path=Fail Then Go Loop Else Return Cons(R,Path);當Path=Fail時,表示遞歸調用失敗,沒有找到從Newdata到目標的解路徑,轉移到Loop處調用下一條規則進行測試;否則過程返回解路徑StepTrack1比StepTrack增加了兩個回溯點，即第(2)步的環路回溯和第(5)步的深度超限回溯。當然，在StepTrack1中也可能存在深度限制不合理的問題，如問題的解的深度為Bound 1，但由於設定的深度界限為Bound不太合理，導致找不到問題的解。此時，可以做可變深度限制的處理，即在遍歷過深度Bound之內的結點後仍然沒有找到問題的解，適當增加Bound的值接著搜索。3. 避免多次試探同一個結點的回溯策略上面介紹的StepTrack和StepTrack1盡管已經能處理非法狀態的回溯、試探過所有子結點的回溯、無限深淵回溯和環路回溯，但還是有可能出現多次試探同一個結點的問題。對於什麼是多次試探同一個結點，可以通過幾個例子說明。在圖38中的StepTrack或StepTrack1的搜索軌跡，如果增加一條從C結點到F結點的路徑，如圖311所示，即F結點可以由B結點生成，也可以由C結點生成，搜索的情況就會稍稍發生變化。此時由於StepTrack和StepTrack1隻保留了從初始結點到當前結點的一條路徑，而沒有其他的數據結構記錄那些試探過的、但不在從初始結點到當前結點的路徑上的結點，導致F結點被試探兩次，試探其是否能通向目標結點。其中，次試探來自B結點，B的個子結點E無法通向目標，因此試探E的兄弟F，此時算法記錄的結點序列是A→B→F，發現F也無法通向目標，由於E和F沒有其他兄弟結點，回溯至B結點，回溯至A結點。接著試探B的兄弟C是否能通向目標，C有兩個孩子結點，個是F，此時算法記錄的結點序列為A→C→F，由於沒有數據結構記錄剛剛F的試探結果，此時會對F進行第二次向縱深進行的試探，而這次試探來自C結點。試探後發現F無法通向目標，再去試探C的另一個孩子、F的兄弟G結點。與F結點類似，K結點也會被試探兩次。圖中虛線箭頭指出了搜索的軌跡，結點旁邊的數字說明了該結點被搜索到的次序。再來看圖312所示的一個更的例子，初始結點有若干個子結點，每個子結點都鏈接到3條很深的路徑中，且其中兩條是左邊的A路徑和B路徑，而目標結點t位於右邊路徑的深處。圖311回溯搜索示意圖圖312回溯搜索示意圖第3章搜索策略在進行問題的智能求解時，一般會涉及兩個部分。部分是問題的表示，也就是把待求解的問題表示出來。如果一個問題找不到一種合適的表示方法，對它的求解也就無從談起。在第2章中已經討論過各種知識表示技術，可以基於這些技術表示待求解的問題。第二部分是問題的具體求解，即針對問題，分析其特征，選擇一種相對合適的方法進行求解。目前問題求解的基本方法有搜索法、歸約法、歸結法、推理法、約束滿足法、規劃和產生式、模擬退火法、遺傳算法等。本章主要討論問題的搜索求解策略，即采用搜索法求解問題時怎樣表示問題、怎樣基於具體的搜索策略解決問題。3.1概述搜索是人工智能的經典問題之一，它與推理密切相關，搜索策略的優劣直接影響智能繫統的性能。以下給出搜索的概念，並對搜索的基本過程、控制策略以及搜索策略的分類等做一個簡單的介紹。3.1.1搜索概述人工智能所要解決的問題大多數是結構不良或非結構化的問題。對於這樣的問題，一般很難獲得其全部信息，也沒有成熟的求解算法可供利用，問題求解隻能依靠經驗，利用已有的知識一步步地摸索著前進。例如，對於醫療診斷的智能繫統，基於已知的初始癥狀，需要在規則庫中尋找可以使用的醫療知識，逐步診斷出患者的疾病，這就存在按照何種線路進行診斷的問題。另外，從初始的癥狀到後疾病的判斷可能存在多條診斷路線，這就存在按照哪條路線進行診斷可以獲得較高求解效率的問題。像這種根據問題的實際情況，不斷尋找可以利用的知識，從而構造出一條代價較少的推理路線，使得問題得到圓滿解決的過程稱為搜索。人工智能進行問題求解時，即使對於結構性能較好，理論上也有算法可依的問題，如果問題本身或算法的復雜性較高(如按照指數級增長)，同時受計算機在時間和空間上的限制，會產生人們常說的組合爆炸問題。例如，64階漢諾塔問題有364種狀態，僅從空間上看，這是任何計算機都無法存儲的問題。再如，在實現一個能進行人機對弈的智能繫統時，計算機為了取得勝利，需要考慮所有的可能性，然後選擇的走步方式，設計這樣的算法並不困難，但卻需要計算機驚人的時間和空間代價。對於這種雖然理論上有算法但卻無法付諸實現的問題，有時也需要通過搜索策略來解決。搜索中需要解決的基本問題有以下幾個。(1) 搜索過程是否一定能找到一個解？(2) 搜索過程是否能終止運行？或是否會陷入一個死循環？(3) 當搜索過程找到一個解時，找到的是否是解？(4) 搜索過程的時間和空間復雜性如何？我們曾經遇到過的走迷宮問題、旅行商問題、八數碼問題等，都是很經典的搜索問題，後文會基於這些典型問題的求解，探討不同的搜索策略及其特征。3.1.2搜索的主要過程不同的搜索策略，搜索的具體步驟並不一樣，但它們都具有以下主要過程。(1) 從初始狀態或目標狀態出發，並把它們作為當前狀態。(2) 掃描操作算子集(操作算子用於實現狀態的轉換)，將適用於當前狀態的一些操作算子作用於當前狀態得到新的狀態，並建立指向其父結點的指針。(3) 檢查所生成的新狀態是否滿足結束狀態？如果滿足，則得到問題的一個解，並可以沿著有關指針從結束狀態逆向到達開始狀態，給出這一解的路徑；否則，將新狀態作為當前狀態，返回第(2)步再進行搜索。3.1.3搜索策略的分類可以根據搜索過程中是否使用了啟發性的信息將搜索分為盲目搜索和啟發式搜索兩種類型。盲目搜索，也稱無信息引導的搜索，是指沒有利用和問題相關的知識，按照預定的控制策略進行搜索，在搜索過程中獲得的中間信息也不用來改進控制策略。由於搜索總是按照預先設定的路線進行，沒有考慮待求解問題本身的特性，因此這種搜索具有盲目性，效率不高，不擅長解決復雜問題。但盲目搜索具有通用性，當一時難以找到待求解問題的有效知識時，是一種不得不采用的方法。啟發式搜索，也稱有信息引導的搜索，它與盲目搜索正好相反，在搜索中加入了與問題有關的啟發性信息，用以指導搜索朝著有希望的方向前進，加速了問題求解的過程，以盡快找到()解。啟發式搜索由於利用了問題的有關知識，一般來說，問題的搜索範圍會有所縮小，搜索效率會有所提高。但如何找到對問題求解有幫助的知識，以及如何利用這些知識，是啟發式搜索的關鍵和難點。根據問題的表示方式，也可以將搜索分為狀態空間搜索和與/或圖搜索。由於涉及的細節較多，這裡不做過多闡述，狀態空間搜索策略將在3.2節～3.4節詳細討論，與/或圖搜索策略則放在3.5節、3.6節說明。 3.1.4搜索的方向搜索可以沿著兩個方向進行，即正向搜索和逆向搜索。1. 正向搜索正向搜索指從初始狀態出發的搜索，也稱為數據驅動的搜索。它從問題給出的條件和一個用於狀態轉換的操作算子集出發，不斷應用操作算子從給定的條件中產生新的條件，再用操作算子從新條件中產生更多的新條件，直到有滿足目標要求的解產生為止。2. 逆向搜索逆向搜索指從目標狀態出發的搜索，也稱為目標驅動的搜索。它從想要達到的目標入手，看哪些操作算子能產生該目標，以及應用這些操作算子產生該目標時需要哪些條件，這些條件就成為想要達到的新目標，即子目標。通過反向搜索不斷尋找子目標，直到找到問題給定的條件為止，這樣就找到了從初始狀態到目標狀態的解，盡管搜索方向和解正好相反。究竟采用正向搜索還是逆向搜索，一般應該考慮以下3個因素。(1) 初始狀態和目標狀態中，哪個狀態多？一般從小的狀態集合出發朝大的狀態集合搜索，這樣問題求解更容易一些。(2) 正向搜索和逆向搜索哪個分支因素低？一般朝著分支因素低的方向進行搜索。分支因素是指從一個結點出發可以直接到達的平均結點數。(3) 選擇搜索方向時還可以考慮操作算子的數目和復雜性、狀態空間的形狀和人們的思考方法等。當然，也可以將正向搜索和逆向搜索結合起來構成雙向搜索，即兩個方向同時進行，直到在中間的某處彙合為止。3.1.5主要的搜索策略到目前為止，人工智能領域已經出現了很多具體的搜索方法，概括起來有以下幾種。1. 求任一解的搜索策略(1) 回溯法(BackTracking)。(2) 爬山法(Hill Climbing)。(3) 寬度優先法(Breadthfirst)。(4) 深度優先法(Depthfirst)。(5) 限定範圍搜索法(Beam Search)。(6) 優先法(Bestfirst)。2. 求解的搜索策略(1) 大英博物館法(British Museum)。(2) 分支界限法(Branch and Bound)。(3) 動態規劃法(Dynamic Programming)。(4) 圖搜索法(A)。3. 求與/或關繫解圖的搜索法(1) 一般與/或圖搜索法(AO)。(2) 極小極大法(Minimax)。(3) α\\|β剪枝法(Alpha\\|beta Pruning)。(4) 啟發式剪枝法(Heuristic Pruning)。本章將對其中幾個基本的搜索策略做進一步討論。3.2狀態空間知識表示方法人工智能雖然有很多研究領域，而且每個研究領域又有自己的特點和規律，但從它們解決實際問題的過程來看，都可以歸納抽像成一個“問題求解”的過程。采用搜索法進行問題求解時，首先必須采用某種知識表示技術將待求解的問題表示出來，其表示方法是否恰當將直接影響問題求解的效率。本節介紹的狀態空間表示法和後文將要介紹的與/或圖表示法是兩種基本的知識表示方法，可以用來表示問題及其求解過程。考慮到它們和搜索問題的密切關繫，以及搜索問題在人工智能研究中的核心地位，將這兩種知識表示技術放在本章詳細討論，而沒有將它們同謂詞邏輯、產生式、語義網絡等知識表示技術一起放在“第2章知識表示”中單獨說明。3.2.1狀態空間表示法狀態空間表示法是用“狀態”和“操作”來表示和求解問題的一種方法。其中，“狀態”用來描述問題求解過程中的各種情況，“操作”用來實現“狀態”之間的轉換。1. 狀態狀態(State)是描述問題求解過程中每一步問題狀況的數據結構，一般采用以下形式表示，即Sk=(Sk0,Sk1,…)其中，當對每一個分量Ski賦予一個確定的值時，就得到了一個具體的狀態。在實際問題求解時，可以采用任何恰當類型的數據結構來描述狀態，如符號、字符串、向量、多維數組、樹和表格等，使之有利於問題的解決。2. 操作操作(Operator)，也稱為算符，是將問題從一個狀態轉換為另一個狀態的手段。當對一個狀態使用某個可用的操作時，會引起該狀態中某些分量的值的變化，導致問題從這個狀態轉換為另一個狀態。簡單地說，操作可以看成是狀態集合上的一個函數，它描述了狀態之間的關繫。操作可以是一個運算、一條規則、一個過程或一個機械步驟。例如，在產生式繫統中，操作實際就是一條條的產生式規則。3. 狀態空間狀態空間(State Space)是由問題的全部狀態和全部可用操作構成的集合，它描述了問題的所有狀態和它們之間的相互關繫，一般用組表示，即(S,O,S0,G)其中，S是狀態集合，S中的素表示一個狀態； O是操作的集合，O 中的素表示一個操作； S0 是問題的初始狀態集合，是 S 的非空子集，S0S ； G 是問題的目標狀態集合，是 S 的非空子集，GS，G 可以是若干具體的狀態，也可是滿足某些性質的路徑信息描述。從S0結點到G結點的路徑被稱為求解路徑。圖31八數碼問題的一個狀態狀態空間的一個解是一個有限操作算子序列，它使初始狀態轉化為目標狀態，即S0O1S1O2S2O3…OkG其中，Oi為操作算子，O1,O2,O3,…,Ok是狀態空間的一個解。解也可以用對應的狀態序列來表示。當然，解往往不是的。例31八數碼問題的狀態空間表示。八數碼問題(重排九宮問題)是在圖31所示的3×3的方格棋盤上，放置8張標記為1～8的將牌，還有一個空格，空格四周上下左右的將牌可以移動到空格中。需要找到一種將牌移動的方式，使8張將牌的排列由某種情況轉換為另一種情況。用狀態空間表示法表示八數碼問題。【解】現對八數碼問題的狀態空間表示中狀態、操作和狀態空間的形式進行說明。(1) 8張將牌的任何一種排列方式都是一種狀態，所有的排列方式構成了狀態集合S，其大小為9!個。(2) 操作是進行狀態變換的手段，可以從兩個角度進行設計。從將牌的角度看，操作可以是對將牌的移動，每張將牌可以有上、下、左、右4個移動方向，一共有8張將牌，因此操作算子共有4×8=32個；從空格的角度看，操作也可以看成是對空格的移動，空格可以有上、下、左、右4個移動方向，而且隻有1個空格，因此操作算子共有4×1=4個，即空格上移Up、空格下移Down、空格左移Left和空格右移Right。顯然後一種操作的設計方式更為簡單。值得注意的是，並不是任何狀態都可以使用這4個操作，對某個狀態實施操作時還要確保空格不會被移出方格棋盤之外。例如，當空格在左下角時，隻有兩個操作可以使用，它們是空格上移Up和空格右移Right。同理，如果從將牌移動的角度設計操作，也並不是任何狀態都可以使用32個操作，畢竟隻有和空格相鄰的將牌纔能移動。(3) 狀態空間描述了問題所有的狀態和它們之間的關繫組(S,O,S0,G)中，狀態集合與操作集合都已在上面說明，問題的初始狀態集合S0和目標狀態集合G可以是需要的任何布局，如圖32就是其中的一種。在搜索問題中，其實就是要尋找到一個將牌移動的序列(操作序列)，使得問題由初始狀態變換為目標狀態。圖32八數碼問題的初始狀態和目標狀態例32二階漢諾塔問題的狀態空間表示。假設有編號為1號、2號和3號的3個鋼針，初始情況下，1號鋼針上穿有A和B兩個金片，A比B小，A位於B的上面。要求通過金片的移動將A和B移動到另外一根鋼針上，規定每次隻能移動一個金片，而且任何時刻都不能使大的金片位於小的金片上方。問題的初始狀態和目標狀態如圖33所示。圖33二階漢諾塔問題的初始狀態和目標狀態【解】現對漢諾塔問題用狀態空間表示法表示時，狀態、操作和狀態空間的形式進行說明。(1) 兩個金片任意一種合法的放置方式都是一種狀態，假設狀組Sk=(Sk0,Sk1)表示，其中Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。如S0=(1,1)表示A片在1號鋼針上，B片也在1號鋼針上，且A片在B片上面。(2) 問題全部可能的狀態一共有9種，即S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)如圖34所示。它們構成了狀態集合 S，其大小為9個。圖34二階漢諾塔問題的所有狀態(3) 初始狀態集合為{S0}，目標狀態集合為{S4,S8}。(4) 操作是進行狀態變換的手段，分別用A(i,j)和B(i,j)表示，其中A(i,j)表示把A片從第i號鋼針移動到第j號鋼針上，B(i,j)表示把B片從第i號鋼針移動到第j號鋼針上。操作共有12種，它們分別是: A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2) B(1,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)在進行問題求解時，應當注意保證狀態的合法性，即保證操作算子使用後不會使大的金片位於小的金片上方。(5) 狀態空間描述了問題所有的狀態和它們之間的關繫，狀態集合、操作集合、初始狀態集，目標狀態集在上面都已說明。在搜索問題中，其實就是要尋找到一個移動金片的操作序列，使得問題由初始狀態變換為目標狀態。3.2.2狀態空間圖狀態空間可以用有向圖來描述，因為圖是直觀的。圖中的結點表示問題的狀態，圖中的有向弧表示狀態之間的關繫，也就是操作。進行問題求解時，初始狀態對應實際問題的已知信息，是圖的根結點。問題求解就是尋找從初始狀態轉換為目標狀態的某個操作算子序列，也就是尋找從初始狀態到目標狀態的一條路徑。因此，問題的解又可以很形像地稱為解路徑。和操作算子序列對應的，問題的解也可以是一個合法狀態的序列，其中序列的個狀態是問題的初始狀態，後一個狀態是問題的結束狀態。介於初始狀態和結束狀態之間的則是中間狀態。除了個狀態外，該序列中任何一個狀態，都可以通過一個操作，由與它相鄰的前一個狀態轉換得到。在圖35所示的狀態空間圖中，初始狀態集合為{S0}，目標狀態集合為{S12}，有向弧上的標識說明了相應的操作算子。通過利用操作算子對狀態進行轉換，可以找到從初始狀態到目標狀態的一個解，即O2、O6、O12，或者用狀態的序列表示為S0、S2、S6、S12。圖35狀態空間的有向圖示例在某些問題中，各操作算子的執行代價不同，這時隻需要在圖中給各弧線標注代價即可。一般來說，實際待求解問題的規模是比較大的，即問題所有可能出現的狀態數是比較多的。當問題有解時，如何縮小搜索範圍，快速有效地找到問題的解，甚至是問題的解，正是搜索問題所要研究和探討的。不難想像，對同一個問題來說，采用不同的搜索策略，找到解的搜索空間是有區別的。一般來說，對大空間問題，搜索策略就是要解決組合爆炸的問題。例33旅行商問題(Traveling Salesman Problem，TSP)的狀態空間圖。假設一個推銷員從圖36所示的A城市出發，到其他所有城市去推銷產品，終再回到出發地A城市，需要找到一條路徑，能使推銷員訪問每個城市後回到出發地經過的路徑短或費用較少。各個城市之間的距離(或費用)標注在弧線上。圖36旅行商問題圖37描述了旅行商問題的部分狀態空間圖。下方的表格裡列出了各條路徑及其耗散(代價)。圖37旅行商問題的部分狀態空間圖在前面的例子中，都可以畫出問題的全部狀態空間圖，即使對於例33的五城市旅行商問題而言，雖然隻畫出了狀態空間圖的一部分，但將其補充完整是可能的。但是，如果是80個城市的旅行商問題，要在有限時間畫出問題的全部狀態空間圖難度卻很大，因此，這

網友評論我們期待著您對此商品發表評論

相關商品

商品搜索

商品分类

【醫學】

【各大出版社】