歡迎大家學(xué)習(xí)人工智能導(dǎo)論

1、歡迎大家學(xué)習(xí)人工智能導(dǎo)論 計(jì)算機(jī)系 馬少平自我介紹紹姓名：馬馬少平單位：智智能技術(shù)術(shù)與系統(tǒng)統(tǒng)國(guó)家重點(diǎn)點(diǎn)實(shí)驗(yàn)室室電話(huà)：62782266-8407E-mail：緒論論人工智能能（ArtificialIntelligence）簡(jiǎn)稱(chēng)AI起源于美美國(guó)1956年年的一次次夏季討討論會(huì)什么是AI？計(jì)算算計(jì)計(jì)圖靈實(shí)驗(yàn)驗(yàn)AI的本本質(zhì)問(wèn)題題研究如何何制造出出人造的的智能機(jī)機(jī)器或系系統(tǒng)，來(lái)來(lái)模擬人人類(lèi)智能能活動(dòng)的的能力，以延伸伸人們智智能的科科學(xué)。AI的歷歷史回顧顧第一階段段（40年代中中50年代末末）神神經(jīng)元元網(wǎng)絡(luò)時(shí)時(shí)代雙層網(wǎng)絡(luò)絡(luò)M-P模模型、感知器器模型等等問(wèn)題：XOR問(wèn)問(wèn)題不能能解決Minsky的的著作：Pe

2、rceptions（感感知器）AI的歷歷史回顧顧（續(xù)1）第二階段段（50年代中中60年代中中）通通用方方法時(shí)代代物理符號(hào)號(hào)系統(tǒng)主要研究究的問(wèn)題題：GPS、游游戲、翻翻譯等對(duì)問(wèn)題的的難度估估計(jì)不足足，陷入入困境AI的歷歷史回顧顧（續(xù)2）一個(gè)笑話(huà)話(huà)（英俄俄翻譯）：Thespirit is willingbut thefleshisweek.（心有余余而力不不足）Thevodkaisstrong butmeat is rotten.（伏特加加酒雖然然很濃，但肉是是腐爛的的）AI的歷歷史回顧顧（續(xù)3）出現(xiàn)這樣樣的錯(cuò)誤誤的原因因：Spirit：1）精神神2）烈性性酒結(jié)論：必須理解解才能翻翻譯，而而理解需

3、需要知識(shí)識(shí)AI的歷歷史回顧顧（續(xù)4）第三階段段（60年代中中80年代初初）知知識(shí)工工程時(shí)代代專(zhuān)家系統(tǒng)統(tǒng)知識(shí)工程程知識(shí)工程程席卷全全球各國(guó)發(fā)展展計(jì)劃：美國(guó)星球球大戰(zhàn)計(jì)計(jì)劃英國(guó)ALVEY計(jì)劃法國(guó)UNIKA 計(jì)劃劃日本五代代機(jī)計(jì)劃劃中國(guó)“863”計(jì)劃AI的歷歷史回顧顧（續(xù)5）第四階段段（80年代中中90年代初初）新新的神神經(jīng)元網(wǎng)網(wǎng)絡(luò)時(shí)代代BP網(wǎng)（算法），解決決了多層層網(wǎng)的學(xué)學(xué)習(xí)問(wèn)題題Hopfield網(wǎng)，成功功求解了了貨郎擔(dān)擔(dān)問(wèn)題存在問(wèn)題題：理論依據(jù)據(jù)解決大規(guī)規(guī)模問(wèn)題題的能力力新的動(dòng)向向構(gòu)構(gòu)造化方方法螺旋線(xiàn)分分類(lèi)問(wèn)題題AI的歷歷史回顧顧（續(xù)6）第五階段段（90年代初初現(xiàn)在在）數(shù)數(shù)據(jù)與網(wǎng)網(wǎng)絡(luò)時(shí)代代網(wǎng)絡(luò)給

4、AI帶來(lái)來(lái)無(wú)限的的機(jī)會(huì)知識(shí)發(fā)現(xiàn)現(xiàn)與數(shù)據(jù)據(jù)挖掘AI走向向?qū)嵱没疉I的研研究?jī)?nèi)容容搜索技術(shù)術(shù)知識(shí)表示示規(guī)劃方法法機(jī)器學(xué)習(xí)習(xí)認(rèn)知科學(xué)學(xué)AI的研研究?jī)?nèi)容容（續(xù)1）自然語(yǔ)言言理解與與機(jī)器翻翻譯專(zhuān)家系統(tǒng)統(tǒng)與知識(shí)識(shí)工程定理證明明博弈機(jī)器人數(shù)據(jù)挖掘掘與知識(shí)識(shí)發(fā)現(xiàn)AI的研研究?jī)?nèi)容容（續(xù)2）多Agent系系統(tǒng)復(fù)雜系統(tǒng)統(tǒng)足球機(jī)器器人兩個(gè)組織織：RoboCup和和FIRA模擬組與與機(jī)器人人組控制方式式：FIRA采采用集中中控制，而RoboCup采采用分布布式控制制人機(jī)交互互技術(shù)IBM的的“深藍(lán)藍(lán)”北京時(shí)間間1997年5月12日凌晨晨4點(diǎn)50分，美國(guó)紐紐約公平平大廈，當(dāng)IBM公司司的“深深藍(lán)”超超級(jí)電腦腦將棋盤(pán)盤(pán)上的

5、一一個(gè)兵走走到C4的位置置上時(shí)，國(guó)際象象棋世界界冠軍卡卡斯帕羅羅夫?qū)Α吧钏{(lán)”的人機(jī)機(jī)大戰(zhàn)落落下帷幕幕，“深深藍(lán)”以以3.5：2.5的的總比分分戰(zhàn)勝卡卡斯帕羅羅夫。IBM的的“深藍(lán)藍(lán)”（續(xù)續(xù)1）96年2月第一一次比賽賽結(jié)果：“深藍(lán)”：勝、負(fù)、平平、平、負(fù)、負(fù)負(fù)97年5月第二二次比賽賽結(jié)果：“深藍(lán)”：負(fù)、勝、平平、平、平、勝勝I(mǎi)BM的的“深藍(lán)藍(lán)”（續(xù)續(xù)2）“深藍(lán)”的技術(shù)術(shù)指標(biāo)：32個(gè)CPU每個(gè)CPU有16個(gè)協(xié)協(xié)處理器器每個(gè)CPU有256M內(nèi)存每個(gè)CPU的處處理速度度為200萬(wàn)步步/秒本課主要要學(xué)習(xí)的的內(nèi)容產(chǎn)生式系系統(tǒng)搜索技術(shù)術(shù)盲目搜索索方法啟發(fā)式搜搜索方法法與/或圖圖搜索方方法博弈樹(shù)搜搜索方法法A

6、I中的的謂詞演演算及應(yīng)應(yīng)用知識(shí)表示示簡(jiǎn)介AI中的的其它技技術(shù)介紹紹第一章產(chǎn)產(chǎn)生式式系統(tǒng)1943年P(guān)ost首首先在一一種計(jì)算算形式體體系中提提出60年代代開(kāi)始，成為專(zhuān)專(zhuān)家系統(tǒng)統(tǒng)的最基基本的結(jié)結(jié)構(gòu)形式上很很簡(jiǎn)單，但在一一定意義義上模仿仿了人類(lèi)類(lèi)思考的的過(guò)程1.1產(chǎn)產(chǎn)生式式系統(tǒng)的的基本組組成組成三要要素：一個(gè)綜合合數(shù)據(jù)庫(kù)庫(kù)存存放信息息一組產(chǎn)生生式規(guī)則則知知識(shí)一個(gè)控制制系統(tǒng)規(guī)則則的解釋釋或執(zhí)行行程序（控控制策略略）（推理引引擎）1.2產(chǎn)產(chǎn)生式式系統(tǒng)的的基本過(guò)過(guò)程過(guò)程PRODUCTION1，DATA初始數(shù)據(jù)據(jù)庫(kù)2，until DATA滿(mǎn)滿(mǎn)足結(jié)束束條件，do3，4，在在規(guī)則集集中選擇擇一條可可應(yīng)用于于DA

7、TA的的規(guī)則R5，DATA R應(yīng)用到到DATA得到到的結(jié)果果6，一個(gè)簡(jiǎn)單單的例子子問(wèn)題：設(shè)設(shè)字符轉(zhuǎn)轉(zhuǎn)換規(guī)則則ABCACDBCGBEFDE已知：A，B求：F一個(gè)簡(jiǎn)單單的例子子（續(xù)1）一、綜合合數(shù)據(jù)庫(kù)庫(kù)x，其中x為字符符二、規(guī)則則集1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE一個(gè)簡(jiǎn)單單的例子子（續(xù)2）三、控制制策略順序排隊(duì)隊(duì)四、初始始條件A，B五、結(jié)束束條件Fx求解過(guò)程程數(shù)據(jù)庫(kù)可可觸發(fā)規(guī)規(guī)則被被觸發(fā)發(fā)規(guī)則A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（

8、4）（4）A，B，C，D，G，E，F(xiàn)1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE1 .3 問(wèn)題題表示舉舉例例1：傳傳教士與與野人問(wèn)問(wèn)題（M-C問(wèn)問(wèn)題）問(wèn)題：N個(gè)傳教教士，N個(gè)野人人，一條條船，可可同時(shí)乘乘坐k個(gè)個(gè)人，要要求在任任何時(shí)刻刻，在河河的兩岸岸，傳教教士人數(shù)數(shù)不能少少于野人人的人數(shù)數(shù)。問(wèn)：如何何過(guò)河。以N=3，k=2為例例求解。M-C問(wèn)問(wèn)題（續(xù)續(xù)1）左岸右右岸LRLRm30m03c30c03B10B01M-C問(wèn)問(wèn)題（續(xù)續(xù)2）1，綜合合數(shù)據(jù)庫(kù)庫(kù)（m,c,b)，其中：0m, c3,b0, 12，初始始狀態(tài)（3，3，1）3，目標(biāo)

9、標(biāo)狀態(tài)（結(jié)束狀狀態(tài)）（0，0，0）M-C問(wèn)問(wèn)題（續(xù)續(xù)3）4，規(guī)則則集IF(m,c,1)THEN(m-1,c,0)IF(m,c,1)THEN(m,c-1,0)IF(m,c,1)THEN(m-1,c-1, 0)IF(m,c,1)THEN(m-2,c,0)IF(m,c,1)THEN(m,c-2,0)M-C問(wèn)問(wèn)題（續(xù)續(xù)4）IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1, 1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)5，控制制策略：（略）M-C問(wèn)問(wèn)題（第第二種方方法）4，規(guī)

10、則則集：IF(m,c,1)AND 1i+j2 THEN(m-i,c-j,0)IF(m,c,0)AND 1i+j2 THEN(m+i,c+j,0)猴子摘香香蕉問(wèn)題題abc猴子摘香香蕉問(wèn)題題（續(xù)1）1，綜合合數(shù)據(jù)庫(kù)庫(kù)（M,B,Box,On,H）M：猴子子的位置置B：香蕉蕉的位置置Box：箱子的的位置On=0：猴子子在地板板上On=1：猴子子在箱子子上H=0：猴子沒(méi)沒(méi)有抓到到香蕉H=1：猴子抓抓到了香香蕉猴子摘香香蕉問(wèn)題題（續(xù)2）2，初始始狀態(tài)（c,a,b,0,0）3，結(jié)束束狀態(tài)（x1, x2,x3,x4, 1）其中x1x4為變量量。猴子摘香香蕉問(wèn)題題（續(xù)3）4，規(guī)則則集r1:IF(x,y,z,0,

11、0)THEN(w, y, z, 0, 0)r2:IF(x,y,x,0,0)THEN(z, y, z, 0, 0)r3:IF(x,y,x,0,0)THEN(x, y, x, 1, 0)r4:IF(x,y,x,1,0)THEN(x, y, x, 0, 0)r5:IF(x,x,x,1,0)THEN(x, x, x, 1, 1)其中x, y, z, w為變量1.4產(chǎn)產(chǎn)生式式系統(tǒng)的的特點(diǎn)數(shù)據(jù)驅(qū)動(dòng)動(dòng)知識(shí)的無(wú)無(wú)序性控制系統(tǒng)統(tǒng)與問(wèn)題題無(wú)關(guān)1.5產(chǎn)產(chǎn)生式式系統(tǒng)的的類(lèi)型正向、逆逆向、雙雙向產(chǎn)生生式系統(tǒng)統(tǒng)可交換的的產(chǎn)生式式系統(tǒng)可分解的的產(chǎn)生式式系統(tǒng)第二章產(chǎn)產(chǎn)生式式系統(tǒng)的的搜索策策略?xún)?nèi)容：狀態(tài)空間間的搜索索問(wèn)題。搜索

12、方式式：盲目搜索索啟發(fā)式搜搜索關(guān)鍵問(wèn)題題：如何利用用知識(shí)，盡可能能有效地地找到問(wèn)問(wèn)題的解解（最佳佳解）。產(chǎn)生式系系統(tǒng)的搜搜索策略略（續(xù)1）S0Sg產(chǎn)生式系系統(tǒng)的搜搜索策略略（續(xù)2）討論的問(wèn)問(wèn)題：有哪些常常用的搜搜索算法法。問(wèn)題有解解時(shí)能否否找到解解。找到的解解是最佳佳的嗎？什么情況況下可以以找到最最佳解？求解的效效率如何何。2.1回回溯策策略例：皇后后問(wèn)題( )( )Q(1,1)( )QQ(1,1)(1,1)(2,3)( )Q(1,1)(1,1)(2,3)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4

13、)(3.2)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,

14、2)(2,4)Q(1,2)(2,4)(3,1)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)遞歸的思思想從前有座山 從前有座山 從前有座山遞歸的思思想（續(xù)續(xù)）當(dāng)前狀態(tài)態(tài)目標(biāo)狀態(tài)態(tài)g一個(gè)遞歸歸的例子子intListLenght(LIST *pList)if(pList=NULL)return 0;else returnListLength(pList-next)+1;回溯搜索索算法BACKTRACK（DATA）DATA：當(dāng)前前狀態(tài)。返回值：從當(dāng)前前狀

15、態(tài)到到目標(biāo)狀狀態(tài)的路路徑（以規(guī)則則表的形形式表示示）或FAIL。回溯搜索索算法遞歸過(guò)程程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);存在問(wèn)

16、題題及解決決辦法問(wèn)題：深度問(wèn)題題死循環(huán)問(wèn)問(wèn)題解決辦法法：對(duì)搜索深深度加以以限制記錄從初初始狀態(tài)態(tài)到當(dāng)前前狀態(tài)的的路徑回溯搜索索算法1BACKTRACK1（DATALIST）DATALIST：從從初始到到當(dāng)前的的狀態(tài)表表（逆向向）返回值：從當(dāng)前前狀態(tài)到到目標(biāo)狀狀態(tài)的路路徑（以規(guī)則則表的形形式表示示）或FAIL?；厮菟阉魉魉惴?1,DATA:=FIRST(DATALIST)2,IFMENBER(DATA, TAIL(DATALIST)RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)

17、BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP: IF NULL(RULES) RETURNFAIL;8,R:=FIRST(RULES);回溯搜索索算法1（續(xù)）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);一些深入入的問(wèn)題題失敗原因因分析、多步回回溯QQ一些深入入問(wèn)題（續(xù)）回溯搜索索中知識(shí)識(shí)的

18、利用用基本思想想：盡可能選選取劃去去對(duì)角線(xiàn)線(xiàn)上位置置數(shù)最少少的。QQQQ4 3 3 42.2圖圖搜索索策略問(wèn)題的引引出回溯搜索索：只保保留從初初始狀態(tài)態(tài)到當(dāng)前前狀態(tài)的的一條路路徑。圖搜索：保留所所有已經(jīng)經(jīng)搜索過(guò)過(guò)的路徑徑。一些基本本概念節(jié)點(diǎn)深度度：根節(jié)點(diǎn)深深度=0其它節(jié)點(diǎn)點(diǎn)深度=父節(jié)點(diǎn)點(diǎn)深度+10123一些基本本概念（續(xù)1）路徑設(shè)一節(jié)點(diǎn)點(diǎn)序列為為(n0, n1,nk)，對(duì)于于i=1,k，若若節(jié)點(diǎn)ni-1具有一個(gè)個(gè)后繼節(jié)節(jié)點(diǎn)ni，則該序序列稱(chēng)為為從n0到nk的路徑。路徑的耗耗散值一條路徑徑的耗散散值等于于連接這這條路徑徑各節(jié)點(diǎn)點(diǎn)間所有有耗散值值的總和和。用C(ni, nj)表示從ni到nj的路徑

19、的的耗散值值。一些基本本概念（續(xù)1）擴(kuò)展一個(gè)個(gè)節(jié)點(diǎn)生成出該該節(jié)點(diǎn)的的所有后后繼節(jié)點(diǎn)點(diǎn)，并給給出它們們之間的的耗散值值。這一一過(guò)程稱(chēng)稱(chēng)為“擴(kuò)擴(kuò)展一個(gè)個(gè)節(jié)點(diǎn)”。一般的圖圖搜索算算法1,G=G0 (G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n, OPEN),ADD(n,CLOSED);5,IFGOAL(n) THENEXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);一般的圖圖搜索算算法（續(xù)續(xù)）7,標(biāo)標(biāo)記和修修改指針針：ADD(mj, OPEN

20、),并標(biāo)記mj到n的指針針；計(jì)算是否否要修改改mk、ml到到n的指指針；計(jì)算是否否要修改改ml到到其后繼繼節(jié)點(diǎn)的的指針；8,對(duì)對(duì)OPEN中的的節(jié)點(diǎn)按按某種原則則重新排序序；9,GOLOOP；節(jié)點(diǎn)類(lèi)型型說(shuō)明.mjmkml2.3無(wú)無(wú)信息息圖搜索索過(guò)程深度優(yōu)先先搜索寬度優(yōu)先先搜索深度優(yōu)先先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,IFDEPTH(

21、n)DmGOLOOP;7,EXPAND(n)mi, G:=ADD(mi,G);8,IF目目標(biāo)在mi中THEN EXIT(SUCCESS);9,ADD(mj, OPEN),并并標(biāo)記mj到n的指指針;10,GOLOOP;23184765 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 4

22、7 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標(biāo)深度優(yōu)先先搜索的的性質(zhì)一般不能能保證找找到最優(yōu)優(yōu)解當(dāng)深度限限制不合合理時(shí)，可能找找不到解解，可以以將算法法改為可可變深度度限制最壞情況況時(shí)，搜搜索空間間等同于于窮舉與回溯法法的差別別：圖搜搜索是一個(gè)通通用的與與問(wèn)題無(wú)無(wú)關(guān)的方方法寬度優(yōu)先先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THEN EXIT(FAIL)

23、;3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,EXPAND(n)mi, G:=ADD(mi,G);7,IF目目標(biāo)在mi中THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并標(biāo)記mj到n的指指針;9,GOLOOP;23184765 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4

24、6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 54回溯與寬寬度優(yōu)先先方法的的結(jié)合目的解決寬度度優(yōu)先方方法的空空間問(wèn)題題和回溯溯方法不不能找到到最優(yōu)解解的問(wèn)題題。思想首先給回回溯法一一個(gè)比較較小的深深度限制制，然后后逐漸增增加深度度限制，知道找找到解或或找遍所所以分支支為止。寬度優(yōu)先先搜索的的性質(zhì)當(dāng)問(wèn)題有有解時(shí)，一定能能找到解解當(dāng)問(wèn)題為為單位耗耗散值，且問(wèn)題題有解時(shí)時(shí)，一定定能找到到最優(yōu)解解方法與問(wèn)問(wèn)題無(wú)關(guān)關(guān)，具有有通用性性效率較

25、低低屬于圖搜搜索方法法2.4啟啟發(fā)式式圖搜索索利用知識(shí)識(shí)來(lái)引導(dǎo)導(dǎo)搜索，達(dá)到減減少搜索索范圍，降低問(wèn)問(wèn)題復(fù)雜雜度的目目的。啟發(fā)信息息的強(qiáng)度度強(qiáng)：降低低搜索工工作量，但可能能導(dǎo)致找找不到最最優(yōu)優(yōu)解解弱：一般般導(dǎo)致工工作量加加大，極極限情況況下變?yōu)闉槊っつ克阉魉?，但可可能可以以找到最最?yōu)解希望：引入啟發(fā)發(fā)知識(shí)，在保證證找到最最佳解的的情況下下，盡可可能減少少搜索范范圍，提提高搜索索效率。基本思想想定義一個(gè)個(gè)評(píng)價(jià)函函數(shù)f，對(duì)當(dāng)前前的搜索索狀態(tài)進(jìn)進(jìn)行評(píng)估估，找出出一個(gè)最最有希望望的節(jié)點(diǎn)點(diǎn)來(lái)擴(kuò)展展。1，啟發(fā)發(fā)式搜索索算法A（A算算法）評(píng)價(jià)函數(shù)數(shù)的格式式：f(n) =g(n)+ h(n)f(n)：評(píng)價(jià)價(jià)函數(shù)

26、h(n)：?jiǎn)l(fā)發(fā)函數(shù)符號(hào)的意意義g*(n)：從從s到n的最短短路徑的的耗散值值h*(n)：從從n到g的最短短路徑的的耗散值值f*(n)=g*(n)+h*(n)：從從s經(jīng)過(guò)過(guò)n到g的最短短路徑的的耗散值值g(n)、h(n)、f(n)分別別是g*(n)、h*(n)、f*(n)的估計(jì)計(jì)值A(chǔ)算法1,OPEN:=(s), f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,EXPAND(n)Mi,計(jì)算

27、f(n,mi):=g(n, mi)+h(mi);A算法（續(xù)）ADD(mj, OPEN),標(biāo)標(biāo)記mj到n的的指針；IFf(n, mk)f(mk)THEN f(mk):=f(n, mk),標(biāo)記mk到n的的指針；IFf(n, ml)f*(s)。A*算法法的性質(zhì)質(zhì)（續(xù)2）引理2.2：A*結(jié)束前，OPEN表中中必存在在f(n)f*(s)。A*算法法的性質(zhì)質(zhì)（續(xù)3）定理2：對(duì)無(wú)限圖圖，若從從初始節(jié)節(jié)點(diǎn)s到到目標(biāo)節(jié)節(jié)點(diǎn)t有有路徑存存在，則則A*一一定成功功結(jié)束。A*算法法的性質(zhì)質(zhì)（續(xù)4）推論2.1：OPEN表上任任一具有有f(n) h1(n)，則在在具有一一條從s到t的的路徑的的隱含圖圖上，搜搜索結(jié)束束時(shí)，

28、由由A2所所擴(kuò)展的的每一個(gè)個(gè)節(jié)點(diǎn)，也必定定由A1所擴(kuò)展展，即A1擴(kuò)展展的節(jié)點(diǎn)點(diǎn)數(shù)至少少和A2一樣多多。簡(jiǎn)寫(xiě)：如如果h2(n)h1(n),則則A1擴(kuò)展的的節(jié)點(diǎn)數(shù)數(shù)A2擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)對(duì)h的評(píng)評(píng)價(jià)方法法平均分叉叉樹(shù)設(shè)共擴(kuò)展展了d層層節(jié)點(diǎn)，共搜索索了N個(gè)個(gè)節(jié)點(diǎn)，則:N =(1-b*(d+1)/(1-b)其中，b*稱(chēng)為為平均分分叉樹(shù)。b*越小小，說(shuō)明明h效果果越好。實(shí)驗(yàn)表明明，b*是一個(gè)個(gè)穩(wěn)定的的常數(shù)，基本不不隨問(wèn)題題規(guī)模變變化。對(duì)h的評(píng)評(píng)價(jià)舉例例例：8數(shù)數(shù)碼問(wèn)題題，隨機(jī)機(jī)產(chǎn)生若若干初始始狀態(tài)。使用h1：d=14,N=539,b*=1.44;d=20,N=7276，b*=1.47；使用h2：d=14,N

29、=113,b*=1.23;d=20,N=676,b*=1.27A*的復(fù)復(fù)雜性一般來(lái)說(shuō)說(shuō)，A*的算法法復(fù)雜性性是指數(shù)數(shù)型的，可以證證明，當(dāng)當(dāng)且僅當(dāng)當(dāng)以下條條件成立立時(shí)：abs(h(n)-h*(n)O(log(h*(n)A*的算算法復(fù)雜雜性才是是非指數(shù)數(shù)型的，但是通通常情況況下，h與h*的差差別至少少是和離離目標(biāo)的的距離成成正比的的。3，A*算法的的改進(jìn)問(wèn)題的提提出：因A算法法第6步步對(duì)ml類(lèi)節(jié)點(diǎn)點(diǎn)可能要要重新放放回到OPEN表中，因此可可能會(huì)導(dǎo)導(dǎo)致多次次重復(fù)擴(kuò)擴(kuò)展同一一個(gè)節(jié)點(diǎn)點(diǎn)，導(dǎo)致致搜索效效率下降降。s(10)A(1)B(5)C(8)G 目標(biāo)631118一個(gè)例子子：OPEN表CLOSED表s(

30、10)s(10)A(7) B(8)C(9)A(7) s(10)B(8) C(9)G(14)A(5) C(9)G(14)C(9) G(12)B(7) G(12)A(4) G(12)G(11)B(8) s(10)A(5) B(8)s(10)C(9) A(5)s(10)B(7) C(9)s(10)A(4) B(7)C(9)s(10)出現(xiàn)多次次擴(kuò)展節(jié)節(jié)點(diǎn)的原原因在前面的的擴(kuò)展中中，并沒(méi)沒(méi)有找到到從初始始節(jié)點(diǎn)到到當(dāng)前節(jié)節(jié)點(diǎn)的最最短路徑徑，如節(jié)節(jié)點(diǎn)A。解決的途途徑對(duì)h加以以限制能否對(duì)h增加適適當(dāng)?shù)南尴拗?，使使得第一一次擴(kuò)展展一個(gè)節(jié)節(jié)點(diǎn)時(shí)，就找到到了從s到該節(jié)節(jié)點(diǎn)的最最短路徑徑。對(duì)算法加加以改進(jìn)進(jìn)能否對(duì)算算

31、法加以以改進(jìn)，避免或或減少節(jié)節(jié)點(diǎn)的多多次擴(kuò)展展。改進(jìn)的條條件可采納性性不變不多擴(kuò)展展節(jié)點(diǎn)不增加算算法的復(fù)復(fù)雜性對(duì)h加以以限制定義：一一個(gè)啟發(fā)發(fā)函數(shù)h，如果果對(duì)所有有節(jié)點(diǎn)ni和nj，其其中nj是ni的子節(jié)節(jié)點(diǎn)，滿(mǎn)滿(mǎn)足h(ni)- h(nj) c(ni,nj)h(t) =0則稱(chēng)h是是單調(diào)的的。h(ni)ninjh(nj)c(ni,nj)h單調(diào)的的性質(zhì)定理5：若h(n)是單單調(diào)的，則A*擴(kuò)展了了節(jié)點(diǎn)n之后，就已經(jīng)經(jīng)找到了了到達(dá)節(jié)節(jié)點(diǎn)n的的最佳路路徑。即：當(dāng)A*選n擴(kuò)展時(shí)時(shí)，有g(shù)(n)=g*(n)。h單調(diào)的的性質(zhì)（續(xù)）定理6：若h(n)是單單調(diào)的，則由A*所擴(kuò)擴(kuò)展的節(jié)節(jié)點(diǎn)序列列其f值值是非遞遞減的。h

32、單調(diào)的的例子8數(shù)碼問(wèn)問(wèn)題：h為“不不在位”的將牌牌數(shù)1h(ni)- h(nj) =0(nj為ni的的后繼節(jié)節(jié)點(diǎn))-1h(t) =0c(ni,nj)=1滿(mǎn)足單調(diào)調(diào)的條件件。對(duì)算法加加以改進(jìn)進(jìn)一些結(jié)論論：OPEN表上任任以具有有f(n) f*(s)的節(jié)點(diǎn)點(diǎn)定會(huì)被被擴(kuò)展。A*選作作擴(kuò)展的的任一節(jié)節(jié)點(diǎn)，定定有f(n)f*(s)。改進(jìn)的出出發(fā)點(diǎn)OPEN =( )f*(s)f值小于于f*(s)的的節(jié)點(diǎn)f值大于于等于f*(s)的節(jié)節(jié)點(diǎn)fm：到目前為為止已擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)的最大大f值，用fm代替f*(s)修正過(guò)程程A1,OPEN:=(s), f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=(

33、)THEN EXIT(FAIL);3,NEST:=ni|f(ni)fmIFNEST () THENn:=NEST中g(shù)最小的的節(jié)點(diǎn)ELSE n:=FIRST(OPEN),fm:=f(n);4,8:同過(guò)程A。s(10)A(1)B(5)C(8)G 目標(biāo)631118前面的例例子：OPEN表CLOSED表表fms(0+10)s(0+10)10A(6+1)B(3+5) C(1+8)s(0+10) C(1+8)10A(6+1)B(2+5)s(0+10) C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)h的單調(diào)調(diào)化方法法如果令：f(n) =max(f

34、(n的父父節(jié)點(diǎn)),g(n)+h(n)則容易證證明，這這樣處理理后的h是單調(diào)調(diào)的。IDA*算法(Iterative DeepeningA*)基本思想想：回溯溯與A*的結(jié)合合算法簡(jiǎn)介介（非嚴(yán)嚴(yán)格地）1，設(shè)初初始值f0；2，集合合SNULL；3，用回回溯法求求解問(wèn)題題，如果果節(jié)點(diǎn)n的f值值大于f0，則則將該節(jié)節(jié)點(diǎn)放入入集合S中，并并回溯；4，如果果在3中中找到了了解，則則結(jié)束；5，如果果3以失失敗結(jié)束束，則f0S中節(jié)點(diǎn)點(diǎn)的最小小f值；6，返回回到2。知識(shí)的靈靈活應(yīng)用用例：如何何轉(zhuǎn)動(dòng)，使得每每個(gè)扇區(qū)區(qū)數(shù)字和和為12。13551441332523123122552342543433分析：陰影部分分?jǐn)?shù)字和

35、和：48直徑部分分?jǐn)?shù)字和和：24轉(zhuǎn)45改變陰陰影部分分轉(zhuǎn)90改變變直徑部部分但不改變變陰影部部分轉(zhuǎn)180 改改變扇區(qū)區(qū)部分但不改變變陰影部部分也不改變變直徑部部分4，其他他的搜索索算法爬山法（局部搜搜索算法法）其他的搜搜索算法法（續(xù)1）隨機(jī)搜索索算法動(dòng)態(tài)規(guī)劃劃算法如果對(duì)于于任何n，當(dāng)h(n)=0時(shí)時(shí)，A*算法就就成為了了動(dòng)態(tài)規(guī)規(guī)劃算法法。動(dòng)態(tài)規(guī)劃劃st第一階段段第二階段段第三階段段第四階段段第五階段段5，搜索索算法實(shí)實(shí)用舉例例漢字識(shí)別別后處理理一個(gè)例子子我錢(qián)線(xiàn)載載哦栽哉哉裁劣綏綏優(yōu)仍們仿仿倫奶砧砧犯扔妨妨要耍密窮窮安壁駐駐努窯垂垂扳報(bào)叔嵌嵌奴振技技寂敘蔽蔽奮夯杏蠶蠶香脊秀秀吞吝番番精猜指潔潔括

36、治捐捐活冶桔桔種神襯祥祥科鐘拌拌樣拎補(bǔ)補(bǔ)漢字識(shí)別別后處理理二元語(yǔ)法時(shí)：為常量用識(shí)別信度代替問(wèn)題變?yōu)榍笞畲蟮谌屡c與或圖圖的搜索索目標(biāo)目標(biāo)初始節(jié)點(diǎn)3.1基基本概概念與或圖是是一個(gè)超超圖，節(jié)節(jié)點(diǎn)間通通過(guò)連接接符連接接。K-連接接符：.K個(gè)耗散值的的計(jì)算k(n, N) =Cn+k(n1,N)+k(ni,N)其中：N為終節(jié)節(jié)點(diǎn)集Cn為連連接符的的耗散值值.i個(gè)nn1n2ni目標(biāo)目標(biāo)初始節(jié)點(diǎn)點(diǎn)解圖：能解節(jié)點(diǎn)點(diǎn)終節(jié)點(diǎn)是是能解節(jié)節(jié)點(diǎn)若非終節(jié)節(jié)點(diǎn)有“或”子子節(jié)點(diǎn)時(shí)時(shí)，當(dāng)且且僅當(dāng)其其子節(jié)點(diǎn)點(diǎn)至少有有一能解解時(shí)，該該非終節(jié)節(jié)點(diǎn)才能能解。若非終節(jié)節(jié)點(diǎn)有“與”子子節(jié)點(diǎn)時(shí)時(shí)，當(dāng)且且僅當(dāng)其其子節(jié)點(diǎn)點(diǎn)均能解解時(shí)，該該非終節(jié)節(jié)點(diǎn)才能能解。不能解節(jié)節(jié)點(diǎn)沒(méi)有后裔裔的非終終節(jié)點(diǎn)是是不能解解節(jié)點(diǎn)。若非終節(jié)節(jié)點(diǎn)有“或”子子節(jié)點(diǎn)，當(dāng)且僅僅當(dāng)所有有子節(jié)點(diǎn)點(diǎn)均不能能解時(shí)，該非終終節(jié)點(diǎn)才才不能解解。若非終節(jié)節(jié)點(diǎn)有“與”子子節(jié)點(diǎn)時(shí)時(shí)，當(dāng)至至少有一一個(gè)子節(jié)節(jié)點(diǎn)不能能解時(shí)，該非