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