人工智能(第3版)/21世紀(jì)高等學(xué)校計(jì)算機(jī)專業(yè)實(shí)用規(guī)劃教材
定 價:59 元
叢書名:21世紀(jì)高等學(xué)校計(jì)算機(jī)專業(yè)實(shí)用規(guī)劃教材
- 作者:朱福喜 著
- 出版時間:2017/1/1
- ISBN:9787302458876
- 出 版 社:清華大學(xué)出版社
- 中圖法分類:TP18
- 頁碼:473
- 紙張:膠版紙
- 版次:3
- 開本:16開
本書系統(tǒng)地闡述了人工智能的基本原理、實(shí)現(xiàn)技術(shù)及其應(yīng)用,全面地反映了國內(nèi)外人工智能研究領(lǐng)域的新進(jìn)展和發(fā)展方向。全書共19章,分為4個部分:第1部分是搜索與問題求解,用8章的篇幅系統(tǒng)地?cái)⑹隽巳斯ぶ悄苤懈鞣N搜索方法求解的原理和方法,內(nèi)容包括狀態(tài)空間和傳統(tǒng)的圖搜索算法、和聲算法、禁忌搜索算法、遺傳算法、免疫算法、粒子群算法、蟻群算法和Agent技術(shù)等;第2部分為知識與推理,用4章的篇幅討論各種知識表示和處理技術(shù)、各種典型的推理技術(shù),還包括非經(jīng)典邏輯推理技術(shù)和非協(xié)調(diào)邏輯推理技術(shù);第3部分為學(xué)習(xí)與發(fā)現(xiàn),用3章的篇幅討論傳統(tǒng)的機(jī)器學(xué)習(xí)算法、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法、數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù);第4部分為領(lǐng)域應(yīng)用,用3章分別討論專家系統(tǒng)開發(fā)技術(shù)和自然語言處理原理和方法。
這些內(nèi)容能夠使讀者對人工智能的基本概念和人工智能系統(tǒng)的構(gòu)造方法有一個比較清楚的認(rèn)識,對人工智能研究領(lǐng)域里的*新成果有所了解。
本書強(qiáng)調(diào)先進(jìn)性、實(shí)用性和可讀性,可作為計(jì)算機(jī)、信息處理、自動化和電信等IT相關(guān)專業(yè)的高年級本科生和研究生學(xué)習(xí)人工智能的教材,也可供從事計(jì)算機(jī)科學(xué)研究、開發(fā)和應(yīng)用的教學(xué)和科研人員參考。
本書參考了許多較新的國外同類教材和其他文獻(xiàn),力圖保持新穎性和實(shí)用性,強(qiáng)調(diào)基本概念和基本觀點(diǎn),注重理論和實(shí)際相結(jié)合,配備有大量輔助教學(xué)的演示實(shí)例及推理系統(tǒng)。
本書作為大學(xué)本科學(xué)習(xí)人工智能的教科書,雖然內(nèi)容較多,但可以選擇一些基本內(nèi)容,如問題求解、知識表達(dá)、推理等基本方法與技術(shù)、數(shù)據(jù)挖掘技術(shù)等進(jìn)行講授。本書也可以作為研究生教材和計(jì)算機(jī)專業(yè)工作者了解人工智能的自學(xué)用書。
人工智能作為研究機(jī)器智能和智能機(jī)器的一門綜合性高技術(shù)學(xué)科,產(chǎn)生于20世紀(jì)50年代,曾經(jīng)在20世紀(jì)末經(jīng)歷了一個轟轟烈烈的研究和發(fā)展時期,并且取得過不少令人鼓舞的成就,至今它仍然是計(jì)算機(jī)科學(xué)中備受人們重視和非常具有吸引力的前沿學(xué)科,并不斷衍生出很多新的研究方向。
使計(jì)算機(jī)程序具有智能,能夠模擬人的思維和行為,一直是計(jì)算機(jī)科學(xué)工作者的理想和追求。盡管人工智能的發(fā)展道路崎嶇不平,自始至終充滿了艱辛,但不畏艱難地從事人工智能研究的科學(xué)工作者們并沒有放棄對這個理想的追求;盡管計(jì)算機(jī)科學(xué)其他分支的發(fā)展也非常迅猛,并不斷出現(xiàn)些新的學(xué)科領(lǐng)域,但是當(dāng)這些學(xué)科的發(fā)展進(jìn)一步深化的時候,人們不會忘記這樣一個共同的目標(biāo):要使計(jì)算機(jī)更加智能化。所以不同知識背景和專業(yè)的人們都密切關(guān)注人工智能這門具有嶄新思想和實(shí)用價值的綜合性學(xué)科,并正從這個領(lǐng)域發(fā)現(xiàn)某些新思想和新方法。
人工智能的研究范疇不只局限于計(jì)算機(jī)科學(xué)和技術(shù),而是涉及心理學(xué)、認(rèn)知科學(xué)、思維科學(xué)、信息科學(xué)、系統(tǒng)科學(xué)和生物科學(xué)等多個學(xué)科,目前已在知識處理、模式識別、自然語言處理、博弈、自動定理證明、自動程序設(shè)計(jì)、專家系統(tǒng)、知識庫、智能機(jī)器人、智能計(jì)算、數(shù)據(jù)挖掘和知識發(fā)現(xiàn)等多個領(lǐng)域取得了舉世矚目的成果,并形成了多元化的發(fā)展方向。近幾年來,隨著計(jì)算機(jī)網(wǎng)絡(luò),尤其是Internet的發(fā)展,多媒體、分布式人工智能和開放分布式環(huán)境下的多智體(multiagent)以及知識挖掘等計(jì)算機(jī)主流技術(shù)的興起,使得人工智能研究更加活躍,拓寬了其研究和應(yīng)用的領(lǐng)域,正朝著健康和成熟的方向發(fā)展。
然而,也必須看到盡管人工智能取得了以上所述的許多成果,但是比起人工智能剛剛興起時許多專家的預(yù)想還相差甚遠(yuǎn),很多在當(dāng)時過于樂觀的設(shè)想并沒有實(shí)現(xiàn),探究其原因也許要追溯到目前人類對自身的思維規(guī)律和智能行為研究仍然處于探索階段,因此,人工智能研究要比這些專家的預(yù)想艱難、復(fù)雜得多。甚至到今天,對機(jī)器能否實(shí)現(xiàn)智能仍有爭論。這種狀況正如Lovelace女士一百多年前曾經(jīng)說過的:
在考慮任何新穎課題時,常常存在一種傾向,先是過高估計(jì)已發(fā)現(xiàn)是有趣或值得注意的東西。接著,當(dāng)發(fā)現(xiàn)所研究的概念已超過曾一度保持不變的那些概念時,作為一種自然的反應(yīng),就會過低估計(jì)該事件的真實(shí)狀況。
因此,我們必須清楚地認(rèn)識到:人工智能研究道路的曲折和艱難以及許多尖銳的爭論并不表明人工智能學(xué)科沒有前景,它只是向我們表明理解人類認(rèn)知和智能的機(jī)制,探索“智力的形成”是人類面臨的最困難、最復(fù)雜的課題之一。擺在人工智能學(xué)科面前的任務(wù)是極其艱巨和復(fù)雜的,這需要廣大的計(jì)算機(jī)科學(xué)工作者不畏艱難,勇于探索,辛勤耕耘,共同開創(chuàng)人工智能發(fā)展的美好未來。
本書系統(tǒng)地闡述了人工智能的基本原理、實(shí)現(xiàn)技術(shù)及其應(yīng)用,全面地反映了國內(nèi)外人工智能研究領(lǐng)域的最新進(jìn)展和發(fā)展方向。全書共19章,分為4個部分。第1部分是搜索與問題求解,用8章的篇幅系統(tǒng)地?cái)⑹隽巳斯ぶ悄苤杏酶鞣N搜索方法求解的原理和方法,內(nèi)容包括狀態(tài)空間和傳統(tǒng)的圖搜索算法、和聲算法、禁忌搜索算法、遺傳算法、免疫算法、粒子群算法、蟻群算法和Agent技術(shù)等;第2部分為知識與推理,用4章的篇幅討論各種知識表示和處理技術(shù)、各種典型的推理技術(shù),還包括非經(jīng)典邏輯推理技術(shù)和非協(xié)調(diào)邏輯推理技術(shù);第3部分為學(xué)習(xí)與發(fā)現(xiàn),用3章的篇幅討論傳統(tǒng)的機(jī)器學(xué)習(xí)算法、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法、數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù);第4部分為領(lǐng)域應(yīng)用,用3章分別討論專家系統(tǒng)開發(fā)技術(shù)和自然語言處理原理和方法以及智能機(jī)器人技術(shù)。
本書參考了許多較新的國外同類教材和其他文獻(xiàn),力求保持新穎性和實(shí)用性,強(qiáng)調(diào)基本概念和基本觀點(diǎn),注重理論和實(shí)際相結(jié)合,配備有大量輔助教學(xué)的演示實(shí)例及推理系統(tǒng)。
本書作為大學(xué)本科學(xué)習(xí)人工智能的教科書,雖然內(nèi)容較多,但可以選擇一些基本內(nèi)容,如問題求解、知識表達(dá)、推理等基本方法與技術(shù)以及數(shù)據(jù)挖掘技術(shù)等進(jìn)行講授。本書也可以作為研究生教材和計(jì)算機(jī)專業(yè)工作者了解人工智能的自學(xué)用書。
作者在編寫本書時經(jīng)過了漫長的總結(jié)經(jīng)驗(yàn)和收集意見的過程,并與若干老師和同事合作編寫了多種同類教材,得到了他們大量的幫助,在此向這些老師和同事表示衷心的感謝。
在本書的編寫過程中,作者參考了劉娟博士、金濤博士的博士論文,在編寫和搜集資料方面還得到了朱三元、粟藩臣、金敏、楊云水、操郡、朱煒、王丁彬、李珂、賀亢、陳杰、方博、何淼、劉巖、林仁富、黃一釗、劉思等博士和碩士研究生的大力支持,在此向他們表示衷心感謝。
由于水平所限,書中難免存在不足之處,懇請讀者批評指正,使本書得以改進(jìn)和完善。
作者
2016年10月于漢口學(xué)院
第1章概述
1.1人工智能概述
1.2AI的產(chǎn)生及主要學(xué)派
1.3人工智能、專家系統(tǒng)和知識工程
1.4AI模擬智能成功的標(biāo)準(zhǔn)
1.5人工智能應(yīng)用系統(tǒng)
1.6人工智能的技術(shù)特征
習(xí)題1
第1部分搜索與問題求解
第2章用搜索求解問題的基本原理
2.1搜索求解問題的基本思路
2.2實(shí)現(xiàn)搜索過程的三大要素
2.2.1搜索對象
2.2.2擴(kuò)展規(guī)則
2.2.3目標(biāo)測試
2.3通過搜索求解問題
2.4問題特征分析
2.4.1問題的可分解性
2.4.2問題求解步驟的撤回
2.4.3問題全域的可預(yù)測性
2.4.4問題要求的解的滿意度
習(xí)題2
第3章搜索的基本策略
3.1盲目搜索方法
3.1.1寬度優(yōu)先搜索
3.1.2深度優(yōu)先搜索
3.1.3分支有界搜索
3.1.4迭代加深搜索
3.1.5一個盲目搜索問題的幾種實(shí)現(xiàn)
3.2啟發(fā)式搜索
3.2.1啟發(fā)式信息的表示
3.2.2幾種最基本的搜索策略
3.3隨機(jī)搜索
3.3.1模擬退火法
3.3.2其他典型的隨機(jī)搜索算法
習(xí)題3
第4章圖搜索策略
4.1或圖搜索策略
4.1.1通用或圖搜索算法
4.1.2A算法與A*算法
4.2與/或圖搜索
4.2.1問題歸約求解方法與“與/或圖”
4.2.2與/或圖搜索
4.2.3與/或圖搜索的特點(diǎn)
4.2.4與/或圖搜索算法AO*
4.2.5對AO*算法的進(jìn)一步觀察
4.2.6用AO*算法求解一個智力難題
習(xí)題4
第5章博弈與搜索
5.1人機(jī)大戰(zhàn)
5.1.1國際象棋人機(jī)大戰(zhàn)
5.1.2圍棋人機(jī)大戰(zhàn)
5.2博弈與對策
5.3極小極大搜索算法
5.3.1極小極大搜索的思想
5.3.2極小極大搜索算法
5.3.3算法分析與舉例
5.4α-β剪枝算法
習(xí)題5
第6章演化搜索算法
6.1遺傳算法的基本概念
6.1.1遺傳算法的基本定義
6.1.2遺傳算法的基本流程
6.2遺傳編碼
6.2.1二進(jìn)制編碼
6.2.2Gray編碼
6.2.3實(shí)數(shù)編碼
6.2.4有序編碼
6.2.5結(jié)構(gòu)式編碼
6.3適應(yīng)值函數(shù)
6.4遺傳操作
6.4.1選擇
6.4.2交叉操作
6.4.3變異操作
6.5初始化群體
6.6控制參數(shù)的選取
6.7算法的終止準(zhǔn)則
6.8遺傳算法的基本理論
6.8.1模式定理
6.8.2隱含并行性
6.8.3構(gòu)造塊假設(shè)
6.8.4遺傳算法的收斂性
6.9遺傳算法簡例
6.10遺傳算法的應(yīng)用領(lǐng)域
6.11免疫算法
6.11.1免疫算法的發(fā)展
6.11.2免疫算法的基本原理
6.11.3生物免疫系統(tǒng)與人工免疫系統(tǒng)的對應(yīng)關(guān)系
6.11.4免疫算法的基本類型和步驟
6.12典型免疫算法分析
6.12.1陰性選擇算法
6.12.2免疫遺傳算法
6.12.3克隆選擇算法
6.12.4基于疫苗的免疫算法
6.13免疫算法設(shè)計(jì)分析
6.14免疫算法與遺傳算法比較
6.14.1免疫算法與遺傳算法的基本步驟比較
6.14.2免疫算法與遺傳算法不同之處
6.14.3仿真實(shí)驗(yàn)及討論
6.15免疫算法研究的展望
習(xí)題6
第7章群集智能算法
7.1群集智能算法的研究背景
7.2群集智能的基本算法介紹
7.2.1蟻群算法
7.2.2flock算法
7.2.3粒子群算法
7.3集智系統(tǒng)介紹
7.3.1人工魚
7.3.2Terrarium世界
7.4群集智能的優(yōu)缺點(diǎn)
習(xí)題7
第8章記憶型搜索算法
8.1禁忌搜索算法
8.1.1禁忌搜索算法的基本思想
8.1.2禁忌搜索算法的基本流程
8.1.3禁忌搜索示例
8.1.4禁忌搜索算法的基本要素分析
8.1.5禁忌搜索算法流程的特點(diǎn)
8.1.6禁忌搜索算法的改進(jìn)
8.2和聲搜索算法
8.2.1和聲搜索算法簡介和原理
8.2.2算法應(yīng)用
8.2.3算法比較與分析
習(xí)題8
第9章基于Agent的搜索
9.1DAI概述
9.2分布式問題求解
9.3Agent的定義
9.3.1Agent的弱定義
9.3.2Agent的強(qiáng)定義
9.4Agent的分類
9.4.1按功能劃分
9.4.2按屬性劃分
9.5Agent通信
9.5.1Agent通信概述
9.5.2言語動作
9.5.3SHADE通信機(jī)制
9.6移動Agent
9.6.1移動Agent系統(tǒng)的一般結(jié)構(gòu)
9.6.2移動Agent的分類
9.6.3移動Agent的優(yōu)點(diǎn)
9.6.4移動Agent的技術(shù)難點(diǎn)
9.6.5移動Agent技術(shù)的標(biāo)準(zhǔn)化
9.7移動Agent平臺的介紹
9.7.1General Magic公司的Odysses
9.7.2IBM公司的Aglet
習(xí)題9
第2部分知識與推理
第10章知識表示與處理方法
10.1概述
10.1.1知識和知識表示的含義
10.1.2知識表示方法分類
10.1.3AI對知識表示方法的要求
10.1.4知識表示要注意的問題
10.2邏輯表示法
10.3產(chǎn)生式表示法
10.3.1產(chǎn)生式系統(tǒng)的組成
10.3.2產(chǎn)生式系統(tǒng)的知識表示
10.3.3產(chǎn)生式系統(tǒng)的推理方式
10.3.4產(chǎn)生式規(guī)則的選擇與匹配
10.3.5產(chǎn)生式表示的特點(diǎn)
10.4語義網(wǎng)絡(luò)表示法
10.4.1語義網(wǎng)絡(luò)結(jié)構(gòu)
10.4.2二元語義網(wǎng)絡(luò)的表示
10.4.3多元語義網(wǎng)絡(luò)的表示
10.4.4連接詞和量詞的表示
10.4.5語義網(wǎng)絡(luò)的推理過程
10.4.6語義網(wǎng)絡(luò)的一般描述
10.5框架表示法
10.5.1框架理論
10.5.2框架結(jié)構(gòu)
10.5.3框架表示下的推理
10.6過程式知識表示
習(xí)題10
第11章謂詞邏輯的歸結(jié)原理及其應(yīng)用
11.1命題演算的歸結(jié)方法
11.1.1基本概念
11.1.2命題演算的歸結(jié)方法
11.2謂詞演算的歸結(jié)
11.2.1謂詞演算的基本問題
11.2.2將公式化成標(biāo)準(zhǔn)子句形式的步驟
11.2.3合一算法
11.2.4變量分離標(biāo)準(zhǔn)化
11.2.5謂詞演算的歸結(jié)算法
11.3歸結(jié)原理
11.3.1謂詞演算的基本概念
11.3.2歸結(jié)方法可靠性證明
11.3.3歸結(jié)方法的完備性
11.4歸結(jié)過程的控制策略
11.4.1簡化策略
11.4.2支撐集策略
11.4.3線性輸入策略
11.4.4幾種推理規(guī)則及其應(yīng)用
11.5應(yīng)用實(shí)例
11.5.1歸約在邏輯電路設(shè)計(jì)中的應(yīng)用
11.5.2利用推理破案的實(shí)例
習(xí)題11
第12章非經(jīng)典邏輯的推理
12.1非單調(diào)推理
12.1.1單調(diào)推理與非單調(diào)推理的概念
12.1.2默認(rèn)邏輯
12.1.3默認(rèn)邏輯非單調(diào)推理系統(tǒng)
12.2DempsterShater(DS)證據(jù)理論
12.2.1識別框架
12.2.2基本概率分配函數(shù)
12.2.3置信函數(shù)Bel(A)
12.2.4置信區(qū)間
12.2.5證據(jù)的組合函數(shù)
12.2.6DS理論的評價
12.3不確定性推理
12.3.1不確定性
12.3.2主觀概率貝葉斯方法
12.4MYCIN系統(tǒng)的推理模型
12.4.1理論和實(shí)際的背景
12.4.2MYCIN模型
12.4.3MYCIN模型分析
12.4.4MYCIN推理網(wǎng)絡(luò)的基本模式
12.4.5MYCIN推理模型的評價
12.5模糊推理
12.5.1模糊集論與模糊邏輯
12.5.2Fuzzy聚類分析
12.6基于案例的推理
12.6.1基于案例推理的基本思想
12.6.2案例的表示與組織
12.6.3案例的檢索
12.6.4案例的改寫
12.7歸納法推理
12.7.1歸納法推理的理論基礎(chǔ)
12.7.2歸納法推理的基本概念
12.7.3歸納法推理中的主要難點(diǎn)
12.7.4歸納法推理的應(yīng)用
習(xí)題12
第13章次協(xié)調(diào)邏輯推理
13.1次協(xié)調(diào)邏輯的含義
13.1.1傳統(tǒng)的人工智能與經(jīng)典邏輯
13.1.2人工智能中不協(xié)調(diào)的數(shù)據(jù)和知識庫
13.1.3次協(xié)調(diào)邏輯
13.2注解謂詞演算
13.2.1多真值格
13.2.2注解邏輯
13.2.3注解謂詞公式的語義
13.2.4APC中的不協(xié)調(diào)、非、蘊(yùn)涵
13.3基于APC的SLDa推導(dǎo)和SLDa反駁
13.3.1SLDa推導(dǎo)和SLDa反駁
13.3.2注解邏輯推理方法
13.3.3注解邏輯推理舉例
13.4注解邏輯的歸結(jié)原理
13.5應(yīng)用實(shí)例
13.6控制策略
習(xí)題13
第3部分學(xué)習(xí)與發(fā)現(xiàn)
第14章機(jī)器學(xué)習(xí)
14.1概述
14.1.1機(jī)器學(xué)習(xí)的定義和意義
14.1.2機(jī)器學(xué)習(xí)的研究簡史
14.1.3機(jī)器學(xué)習(xí)方法的分類
14.1.4機(jī)器學(xué)習(xí)中的推理方法
14.2歸納學(xué)習(xí)
14.2.1歸納概念學(xué)習(xí)的定義
14.2.2歸納概念學(xué)習(xí)的形式描述
14.2.3歸納概念學(xué)習(xí)算法的一般步驟
14.2.4歸納概念學(xué)習(xí)的基本技術(shù)
14.3基于解釋的學(xué)習(xí)
14.3.1基于解釋學(xué)習(xí)的基本原理
14.3.2基于解釋學(xué)習(xí)的一般框架
14.3.3基于解釋的學(xué)習(xí)過程
14.4基于類比的學(xué)習(xí)
14.4.1類比學(xué)習(xí)的一般原理
14.4.2類比學(xué)習(xí)的表示
14.4.3類比學(xué)習(xí)的求解
14.4.4逐步推理和監(jiān)控的類比學(xué)習(xí)
習(xí)題14
第15章人工神經(jīng)網(wǎng)絡(luò)
15.1人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)
15.2人工神經(jīng)網(wǎng)絡(luò)的基本原理
15.3人工神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu)模式
15.4人工神經(jīng)網(wǎng)絡(luò)互連結(jié)構(gòu)
15.5神經(jīng)網(wǎng)絡(luò)模型分類
15.6幾種基本的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法介紹
15.6.1Hebb型學(xué)習(xí)
15.6.2誤差修正學(xué)習(xí)方法
15.6.3隨機(jī)型學(xué)習(xí)
15.6.4競爭型學(xué)習(xí)
15.6.5基于記憶的學(xué)習(xí)
15.6.6結(jié)構(gòu)修正學(xué)習(xí)
15.7幾種典型神經(jīng)網(wǎng)絡(luò)簡介
15.7.1單層前向網(wǎng)絡(luò)
15.7.2多層前向網(wǎng)絡(luò)及BP學(xué)習(xí)算法
15.7.3Hopfield神經(jīng)網(wǎng)絡(luò)
15.8人工神經(jīng)網(wǎng)絡(luò)與人工智能其他技術(shù)的比較
15.9人工神經(jīng)網(wǎng)絡(luò)的應(yīng)用領(lǐng)域
習(xí)題15
第16章數(shù)據(jù)挖掘與知識發(fā)現(xiàn)
第17章專家系統(tǒng)
第18章自然語言處理
第19章智能機(jī)器人
第3章
搜索的基本策略
本章主要討論搜索的基本策略,即怎樣搜索才可以最有效地達(dá)到目標(biāo)。搜索的基本策略根據(jù)擴(kuò)展的利用問題的特征信息的方式可分為盲目搜索、啟發(fā)式搜索和隨機(jī)搜索。如果沒有利用問題的特征信息,一般的搜索方式與平時找東西在策略上可以說是相同的:
當(dāng)我們在慌亂之中尋找東西的時候通常使用的就是隨機(jī)搜索。
當(dāng)我們在清醒時,有條理地尋找東西的方法大致可以分成兩類: 一種是找眼鏡模式,它指的是眼鏡掉了的時候總是從最近的地方開始尋找,慢慢地?cái)U(kuò)大搜索的范圍; 另一種是走迷宮模式,它指的是在走迷宮的時候由于無法分身只有一條路走到底,走不通再回溯的走法。
這3種方法分別對應(yīng)的就是隨機(jī)搜索、廣度搜索和深度搜索。
下面按是否利用問題的特征信息劃分搜索策略的方法,討論盲目搜索、啟發(fā)式搜索和隨機(jī)搜索。
3.1盲目搜索方法
盲目搜索方法又叫非啟發(fā)式搜索,是一種無信息搜索(uninformed search),一般只適用于求解比較簡單的問題。下面將要討論的幾個搜索方法,它們均屬于盲目搜索方法,雖然其他課程也討論類似的算法,但我們要注重在這里的算法表達(dá)方法。
3.1.1寬度優(yōu)先搜索
在一個搜索樹中,如果搜索是以同層鄰近節(jié)點(diǎn)依次擴(kuò)展節(jié)點(diǎn)的,那么這種搜索就叫寬度優(yōu)先搜索(breathfirst search)。這種搜索是逐層進(jìn)行的,在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前,必須搜索完本層的所有節(jié)點(diǎn)。
在本節(jié)討論的盲目搜索算法中存放節(jié)點(diǎn)都采用一種簡單的數(shù)據(jù)結(jié)構(gòu)——表,表是將節(jié)點(diǎn)按一定的順序用逗號隔開放在一對括號中的一種數(shù)據(jù)結(jié)構(gòu),在表的首部和尾部都可以加入和刪除節(jié)點(diǎn)。
寬度優(yōu)先搜索算法如下。
。1) 令N為一個由初始狀態(tài)構(gòu)成的表。
。2) 若N為空退出,標(biāo)志失敗。
。3) 令n為N中第一個節(jié)點(diǎn),將n從N中刪除。
。4) 若n是目標(biāo),則退出,標(biāo)志成功。
。5) 若n不是目標(biāo),將n的后繼節(jié)點(diǎn)加入到N表的末端,轉(zhuǎn)第(2)步。
寬度優(yōu)先搜索的優(yōu)點(diǎn): 若問題有解,則可找出最優(yōu)解。缺點(diǎn): 效率低,組合爆炸問題難以解決。
3.1.2深度優(yōu)先搜索
與寬度優(yōu)先搜索對應(yīng)的一種盲目搜索叫做深度優(yōu)先搜索(depthfirst search)。在深度優(yōu)先搜索中,首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)到表中。深度相等的節(jié)點(diǎn)可以任意排列。
深度優(yōu)先搜索算法如下。
(1) 令N為一個由初始狀態(tài)構(gòu)成的表。
(2) 若N為空退出,標(biāo)志失敗。
。3) 令n為N中第一個節(jié)點(diǎn),將n從N中刪除。
。4) 若n是目標(biāo),則退出,標(biāo)志成功。
(5) 若n不是目標(biāo),將n的后繼節(jié)點(diǎn)加入到N表的首部,轉(zhuǎn)第(2)步。
深度優(yōu)先搜索的優(yōu)點(diǎn): 節(jié)省大量時間和空間。缺點(diǎn): 不一定能找到解。因?yàn)樵谏疃葻o限搜索樹的情況下,最壞的情況可能是不能停機(jī)。
廣度和深度優(yōu)先搜索雖然在搜索的策略上走了兩個極端,但是它們在控制策略上的差異并不大。它們大都假設(shè)以隊(duì)列作為數(shù)據(jù)結(jié)構(gòu),每次選隊(duì)列的第一個節(jié)點(diǎn)進(jìn)行拓展。廣度和深度優(yōu)先搜索的區(qū)別在于: 廣度優(yōu)先搜索把結(jié)果存在隊(duì)列的尾部; 而深度優(yōu)先搜索則是把它存在首部,只有一字之差。
3.1.3分支有界搜索
分支有界搜索(branchandbound)也是一種深度優(yōu)先搜索,但每個分支都規(guī)定了一個統(tǒng)一的搜索深度,搜索到這個深度后,如果沒有找到目標(biāo)便自動退回到上一層,繼續(xù)按深度優(yōu)先搜索。其算法如下。
。1) 令N為一由初始狀態(tài)構(gòu)成的表。
。2) 若N為空退出,標(biāo)志失敗。
。3) 令n為N中第一個節(jié)點(diǎn),將n從N中刪除。
(4) 若n是目標(biāo),則退出,標(biāo)志成功。
。5) 若n深度為預(yù)先定好的一個界dmax,則轉(zhuǎn)第(2)步。
(6) 若n不是目標(biāo),將n的后繼節(jié)點(diǎn)加入到N表的首部,轉(zhuǎn)第(2)步。
此方法若被搜索樹的深度遠(yuǎn)大于目標(biāo)點(diǎn)的深度,則快于深度優(yōu)先搜索。
3.1.4迭代加深搜索
迭代加深搜索(iterative deepening)是在分支有界搜索的基礎(chǔ)上,對dmax進(jìn)行迭代,即逐步加深。這是一種同時兼顧深度和寬度的搜索方法。在限定的深度內(nèi),保證了對寬度節(jié)點(diǎn)的搜索,如果沒有找到解,再加深深度。
3.1.5一個盲目搜索問題的幾種實(shí)現(xiàn)
這里給出一個簡單的盲目搜索問題: 對于中國象棋,如果“馬”(棋子的名稱)當(dāng)前所在位置是(x,y),它跳一步可能到達(dá)的位置最多有8個,如圖31所示。
要求設(shè)計(jì)一個算法,對于任意給定的棋盤上的坐標(biāo)位置tp,輸出馬從當(dāng)前位置cp出發(fā)通過搜索到達(dá)的該坐標(biāo)位置tp。
……