《人工智能 第三章 基本的問題求解方法》由會員分享，可在線閱讀，更多相關(guān)《人工智能 第三章 基本的問題求解方法（87頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,,,*,第三章,基本的問題求解方法,問題求解的過程：1）知識表示；2）針對問題，分析特征，選擇合適的方法來求解（包括搜索和推理）,方法：,1）基于狀態(tài)圖方法-搜索；,2）基于謂詞邏輯方法-推理；,3）基于結(jié)構(gòu)化的知識表示方法來求解問題；,本章介紹,搜索技術(shù),,,搜索,技,技術(shù),是,是人,工,工智,能,能的,基,基本,技,技術(shù),之,之一,,在,在人,工,工智,能,能各,應(yīng),應(yīng)用,領(lǐng),領(lǐng)域,中,中被,廣,廣泛,地,地使,用,用。,早期,的,的人,工,工智,能,能程,序,序與,搜,搜索,技,技術(shù),聯(lián),聯(lián)系,就,就

2、更,為,為緊,密,密，,幾,幾乎,所,所有,的,的早,期,期的,人,人工,智,智能,程,程序,都,都是,以,以搜,索,索為,基,基礎(chǔ),的,的。,A.Newell,和,和H,·,·A,·,·Simon-LT程,序,序,A·Newell,和,和H,·,·A,·,·Simon-GPS(GeneralProblemSolver),R.Fikes和N.Nilsson-STRIPS(StanfordResearchInstituteProblemSolver),現(xiàn)在,,搜,搜索,技,技術(shù),滲,滲透,在,在各,種,種人,工,工智,能,能系,統(tǒng),統(tǒng)中,,在,在專,家,家系,統(tǒng),統(tǒng)、,自,自然,語,語言,理,理

3、解,、,、自,動,動程,序,序設(shè),計,計、,模,模式,識,識別,、,、機,器,器人,學(xué),學(xué)、,信,信息,檢,檢索,和,和博,奕,奕都,廣,廣泛,使,使用,。,。,,,搜索(search),路徑,狀態(tài)序列,搜索,尋找從初始狀態(tài),到,到目標(biāo)狀態(tài)的路,徑,徑;,S0,Sg,,,搜索的必要性,AI為什么要研,究,究search?,問題沒有直接的,解,解法;,解方程組;,定理證明;,需要探索地求解;,,,搜索與檢索的區(qū),別,別,狀態(tài)是否動態(tài)生,成,成;,檢索: 靜態(tài);,在數(shù)據(jù)庫中檢索,某,某人的紀(jì)錄;,搜索: 動態(tài)生,成,成;,下棋,,,幾個問題,目標(biāo)狀態(tài)是否確,定,定?,確定: 定理證,明,明, ei

4、ght-puzzle,不確定: 求積,分,分, 下棋;,確定目標(biāo)的性質(zhì);,問題的解: 路,徑,徑(解路徑)/,目,目標(biāo)狀態(tài);,需要路徑:,下棋,不需要路徑:,電路設(shè)計,需要/不需要:,診,診病,約束條件,目標(biāo)狀態(tài)不確定,時,時, 用來約束,目,目標(biāo)狀態(tài)的性質(zhì);,X+Y=4:,非,非整數(shù)解/整數(shù),解,解,,,幾個問題(續(xù)1),多解性;,X+Y=4:整,數(shù),數(shù)解,最優(yōu)解,評價標(biāo)準(zhǔn)/判斷,準(zhǔn),準(zhǔn)則;,min(x*y),北京->上海:,時,時間最短/費,用,用最少,最優(yōu)解是否唯一?,下棋,,,,搜索問題,狀態(tài)空間,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,

5、,6,,5,,,,搜索不是檢索,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,難點,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,啟發(fā)式方法,2,,3,,7,,,,5,,1,,4,,8,,6,,1,,2,,3,,8,,,4,,7,,6,,5,,,,搜索方法的評價,標(biāo),標(biāo)準(zhǔn),搜索問題是AI,核,核心理論問題之,一,一。一般一個問,題,題可以用好幾種,搜,搜索技術(shù)解決,,選,選擇一種好的,搜,搜索技術(shù)對解決,問,問題的效率很有,關(guān),關(guān)系, 甚至關(guān),系,系到求解問題有,沒,沒有解。

6、?搜,索,索方法好的標(biāo)準(zhǔn), 一般認為有,兩,兩個：(1)搜索空,間,間小;(2)解最佳,。,。,,,搜索分類,搜索從問題性質(zhì),上,上來看, 可分,為,為一般搜索和博,奕,奕搜索, 從處,理,理方法上來看,,可,可分為盲目搜,索,索和啟發(fā)式搜索,。,。還可以分得更,細,細。,到目前為止,AI領(lǐng)域中已提,出,出許多具體的搜,索,索方法, 概括,起,起來有：(1)求任,一,一解路的搜索策,略,略,回溯法；爬山法(Hill Climbing)；,寬度優(yōu)先法(Breadth-first)；,深,深度優(yōu)先法(Depth-first),(2)求最佳解,路,路的搜索策略,大英博物館法(BritishMuse

7、um)；最佳圖搜索,法,法(A*),(3)求與或關(guān),系,系解圖的搜索法,一般與或圖搜索,法,法(AO*)；,極,極小極大法(Minimax),剪,剪枝法(Alpha-beta Pruning)；啟發(fā)式,剪,剪枝法(HeuristicPruning),,,,,TOPICS,回溯策略（,Backtracking,）,圖搜索（GRAPHSEARCH）,無信息搜索,啟發(fā)式搜索,,,TOPIC1,Backtracking,N,1,N,0,N,2,N,3,N,4,N,5,回溯策略,,,例：四皇后問題,,,( ),,,( ),Q,((1,1)),,,( ),Q,Q,((1,1)),((1,1)(2,3)),

8、,,( ),Q,((1,1)),((1,1) (2,3)),,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),Q,((1,1) (2,4)(3.2)),,,( ),Q,Q,((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)(

9、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,2)(2,4)),Q,((1,2)(2,4)(3,1)),,,Q,Q,Q,Q,( ),((1,1)),

10、((1,1) (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),((1,2)),((1,2) (2,4)),((1,2) (2,4) (3,1)),((1,2) (2,4) (3,1) (4,3)),,,存在問題及解,決,決辦法,問題和解決方,法,法：,深度問題,對搜索深度加,以,以限制,死循環(huán)問題,狀態(tài)重復(fù):A→B,，,B→C, C,→,→A,記錄從初始狀,態(tài),態(tài)到當(dāng)前狀態(tài),的,的路徑,,,TOPIC2GRAPHSEARCH,圖搜索策略,問題的引出,回溯搜索：只,保,保留從初始狀,態(tài),態(tài)到當(dāng)前狀態(tài),的,的一條路徑。,圖搜索：保留,所,所有已經(jīng)搜索,過,過的路徑

11、。,,N,5,N,1,N,0,N,2,,N,3,,N,4,,,一些基本概念,圖：一個節(jié)點,的,的集合。節(jié)點,由,由弧連接起來,。,。,有向圖：弧是,一,一個節(jié)點指向,另,另一個節(jié)點的,圖,圖，稱為有向,圖,圖。,后繼,/,父親：如果有,一,一條弧從,n,i,指向,n,j,，則,n,j,稱為,n,i,的后繼，,n,i,稱為,n,j,的父輩（父親,）,）；,,,一些基本概念(續(xù)1),路徑：如果存,在,在一個節(jié)點序,列,列（,n,i0,，,n,i1,，,……,，,n,ik,），,n,ij,是,n,ij-1,是的后繼，,j=1,，,……,，,k,，則稱這個,序,序列是從節(jié),點,點,n,i0,到節(jié)點,n

12、,ik,的一條路徑,，,，長度為,k,。,祖先/后裔,：,：如果存在,一,一條從n,i,到n,j,的路徑，則,稱,稱n,j,是n,i,的后裔，n,i,稱為n,j,的祖先。,樹：每個節(jié),點,點最多只有,一,一個父輩。,沒,沒有父輩的,節(jié),節(jié)點稱為根,節(jié),節(jié)點。沒有,后,后繼的節(jié)點,稱,稱為葉節(jié)點,。,。,,,一些基本概,念,念(續(xù)2),節(jié)點深度：,根節(jié)點深度=0,其它節(jié)點深,度,度=父節(jié)點,深,深度+1,0,1,2,3,,,一些基本概念（,續(xù),續(xù)3）,擴展一個節(jié)點,生成出該節(jié)點的,所,所有后繼節(jié)點。,弧的費用,有一條弧連接n,i,和n,j,兩個節(jié)點, 用C(n,i,, n,j,),表示使用規(guī)則從

13、n,i,到n,j,的費用(耗散值)。,玉泉路---天,安,安門,路徑的耗散值,一條路徑的耗散,值,值等于連接這條,路,路徑各節(jié)點間所,有,有耗散值的總和,。,。用C(n,i,, n,j,),表示從n,i,到n,j,的路徑的耗散值,。,。,,,,GRAPHSEARCH,的思路,OPEN,表,已經(jīng)生成但未擴,展,展節(jié)點,CLOSED,表,已擴展節(jié)點,擴展節(jié)點,i,生成節(jié)點,j,指針,調(diào)整指針,,,圖搜索（,Graph Search,）的一般過程,1、建立一個只,有,有起始節(jié)點S的,搜,搜索圖G，把S,放,放入一個叫open的未擴展節(jié),點,點表；,2、? 建立已,擴,擴展節(jié)點表closed，初始,為

14、,為空；,3、? LOOP；若open,為,為空，則失敗退,出,出；,4、? 選open表中的第一,個,個節(jié)點，設(shè)為n,，,，移入closed表；,5、若n為目標(biāo),節(jié),節(jié)點，則成功退,出,出，該問題的解,即,即是G中沿S指,向,向n的路徑；,6、若不是目標(biāo),節(jié),節(jié)點，則擴展n,，,，生成不是n的,祖,祖先的那些后繼,節(jié),節(jié)點的集合m，,把,把m的成員作為n的后繼加入G,中,中；,7、對未曾在G,中,中出現(xiàn)過的m成,員,員，設(shè)一通向n,的,的指針，把它們,加,加入open表,。,。對已在closed或open表上的m成員,，,，確定是否要更,改,改到n的指針方,向,向，對已在closed上的m,

15、成,成員，確定是否,要,要更改G中通向,每,每個后裔節(jié)點的,指,指針方向。,8、按某一方式,（,（深度優(yōu)先、寬,度,度優(yōu)先、A,*,算法）重排open表,9、GO LOOP,,,例子,S,OPEN,CLOSE,{S},{},1,2,3,{},{S},{1,2,3},{S},{2,1,3},{S},4,5,{1,3},{S,2},{1,3,4,5},{S,2},{3,1,4,5},{S,2},{1,4,5},{S,2,3},6,{1,4,5,6},{S,2,3},,,例：右圖中黑節(jié),點,點表示已擴展，,白,白節(jié)點表示未擴,展,展，問題：先擴,展,展6號節(jié)點生成m1={4，7}，然后擴展節(jié),點,點

16、1，生成m2={2}，按算,法,法第七步重新修,改,改原圖。,6,1,2,4,5,3,難點！,！,??！算,法,法中第,七,七步,7,,,擴展節(jié),點,點6生,成,成m1={4,，,，7},的,的調(diào)整,6,1,2,4,5,3,7,,1,2,3,5,4,6,7,×,,,再擴展,節(jié),節(jié)點1,生,生成m2={2}的,調(diào),調(diào)整,,1,2,3,5,4,6,7,,1,2,3,5,4,6,7,×,×,,,最終結(jié),果,果,6,1,2,4,5,3,7,,1,2,3,5,4,6,7,,,圖搜索,與,與回溯,算,算法的,區(qū),區(qū)別,擴展節(jié),點,點,:,回溯算,法,法:,生,生成一,個,個兒子,節(jié),節(jié)點.,圖搜索:,擴,擴

17、,展,展節(jié)點,,,生成所,有,有兒子,節(jié),節(jié)點.,候選節(jié),點,點:,回溯算,法,法:,一,一個.,圖搜索:,多,多,個,個.,回溯:,回溯算,法,法,:,返回父,親,親節(jié)點.,圖搜索:,不,不一定,返,返回父,親,親節(jié)點.,,,TOPIC3,無,無信,息,息搜索,如果在,GRAPHSEARCH,中，對,節(jié),節(jié)點的,排,排序不,使,使用與,問,問題相,關(guān),關(guān)的信,息,息，則,稱,稱為無,信,信息圖,搜,搜索（,盲,盲目搜,索,索）,寬度優(yōu),先,先和深,度,度優(yōu)先,,,1、breadth-firstsearch,寬度優(yōu),先,先搜索,：,：如果,搜,搜索是,以,以接近,起,起始節(jié),點,點的程,度,度

18、依次,擴,擴展節(jié),點,點的,。,。,搜索逐,層,層進行,；,；在對,下,下一層,的,的任一,節(jié),節(jié)點進,行,行搜索,之,之前，,必,必須搜,索,索完本,層,層的所,有,有節(jié)點,。,。,,,(1),把,把起,始,始節(jié)點,放,放到OPEN,表,表中(,如,如果該,起,起始節(jié),點,點為一,目,目標(biāo)節(jié),點,點，則,求,求得一,個,個解答)。,(2),如,如果OPEN是個,空,空表，,則,則沒有,解,解，失,敗,敗退出,；,；否則,繼,繼續(xù)。,(3),把,把第,一,一個,節(jié),節(jié)點(節(jié),點,點n)從OPEN,表,表移,出,出，,并,并把,它,它放,入,入CLOSED的,擴,擴展,節(jié),節(jié)點,表,表中,。,。

19、,(4),擴,擴展,節(jié),節(jié)點n。,如,如果,沒,沒有,后,后繼,節(jié),節(jié)點,，,，則,轉(zhuǎn),轉(zhuǎn)向,上,上述,第,第(2),步,步。,(5),把,把n的所,有,有后繼節(jié),點,點放到OPEN表,的,的末端，,并,并提供從,這,這些后繼,節(jié),節(jié)點回到n的指針,。,。,(6),如,如果n的,任,任一個后,繼,繼節(jié)點是,個,個目標(biāo)節(jié),點,點，則找,到,到一個解,答,答，成功,退,退出；否,則,則轉(zhuǎn)向第(2)步,。,。,算法,,,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,★,21,22,23,24,★,26,27,28,29,30,31,1,2,3,4,5

20、,6,7,8,9,10,11,12,13,14,15,16,17,18,19,★,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,,,,,,,,,,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,搜索,演示,★,已擴展,節(jié),節(jié)點,正,正在擴,展,展節(jié)點,擴展的,子,子節(jié)點,未,未擴,展,展節(jié)點,目標(biāo),,,寬度優(yōu),先,先法應(yīng),用,用示例,寬度優(yōu),先,先法求,九,九宮重,排,排問題,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,,,23,184,7

21、65,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2

22、 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目標(biāo),8,2 3 4,1 8,7 6 5,4,,,寬度優(yōu),先,先搜索,是,是圖搜,索,索一般,過,過程的,特,特殊情,況,況，將,圖,圖搜索,一,一般過,程,程中的,第,第8步,具,具體化,為,為本算,法,法中的,第,第6步,，,，這實,際,際是將OPEN表作,為,為“先,進,進先出,”,”的隊,列,列進行,操,操作。,一定能,找,找到解,找到

23、的,解,解一定,是,是最佳,解,解,(在每個,路,路徑消,耗,耗是同,樣,樣的意,義,義上),搜索的,空,空間大,、,、慢。,分析,,,深度優(yōu),先,先搜索,：,：首先,擴,擴展最,新,新產(chǎn)生,的,的(即,最,最深的)節(jié)點,。,。深度,相,相等的,節(jié),節(jié)點可,以,以任意,排,排列。,特點：,擴,擴展最,深,深的節(jié),點,點,使,得,得搜索,沿,沿著狀,態(tài),態(tài)空間,某,某條單,一,一的路,徑,徑從起,始,始節(jié)點,向,向下進,行,行下去,；,；只有,當(dāng),當(dāng)搜索,到,到達一,個,個沒有,后,后裔的,狀,狀態(tài)時,，,，它才,考,考慮另,一,一條替,代,代的路,徑,徑。,算法：,與,與寬度,優(yōu),優(yōu)先相,似,

24、似，不,同,同在于,：,：(5),把,把n,的,的所有,后,后繼節(jié),點,點放到OPEN表的,前,前端,2、depth-first search,,,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,★,23,24,★,26,27,28,29,30,31,1,2,活結(jié)點,表,表,1,1,2,1,1,2,4,2,2,4,8,4,4,8,16,8,8,16,16,,8,17,8,8,17,17,,8,8,,4,9,4,4,9,18,9,9,18,18,,9,19,9,19,19,,,4,4,,2,5,2,2,5,10,5,5,10,20,9,9,9,

25、10,10,20,20,,10,21,10,10,21,21,,10,10,,5,11,5,5,11,★,演示,,,例,九宮重排問,題,題,8 3,6 4,7 ■5,初始狀態(tài),1 23,8 ■4,765,目標(biāo)狀態(tài),,應(yīng)用示例,,,23,1 84,7 65,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7

26、 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5

27、,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,d,1 2 3,8 4,7 6 5,目標(biāo),,,分析,①不一定能,找,找到解。,②解不一定,是,是最佳解。,,,3、其他方,法,法,含有深度界,限,限的深度優(yōu),先,先搜索算法,：,：,基于代價樹,的,的搜索算法,：,：,,,TOPIC4,heuristicsearch,盲目搜索效,率,率低，耗費,過,過多的計算,空,空間與時間,，,，這是組合,爆,

28、爆炸的一種,表,表現(xiàn)形式。,利用知識來,引,引導(dǎo)搜索，,達,達到減少搜,索,索范圍，降,低,低問題復(fù)雜,度,度的目的。,啟發(fā)式方法的本質(zhì)是部,分,分地放棄算,法,法"一般化, 通用化"的概念,,把,把所要解,的,的問題的具,體,體領(lǐng)域 的,知,知識加進算,法,法中去,,以,以提高算法,的,的效率。,,,啟發(fā)式搜索：就是利用,與,與問題有關(guān),的,的啟發(fā)信息,進,進行搜索,啟發(fā)信息：,與,與具體問題,有,有關(guān)的特性,信,信息,啟發(fā)信息的,強,強度,強：降低搜,索,索工作量，,但,但可能導(dǎo)致,找,找不到最優(yōu),解,解,弱：一般導(dǎo),致,致工作量加,大,大，極限情,況,況下變?yōu)槊?目,目搜索，但,可,可能

29、可以找,到,到最優(yōu)解,難點：,獲取；,強度的確定,；,；,,,啟發(fā)信息的,用,用途,a、用于決,定,定要擴展的,下,下一節(jié)點（,避,避免盲目擴,展,展）,b、在擴展,過,過程中，用,于,于決定生成,哪,哪一個或哪,幾,幾個后繼（,以,以免太多無,用,用節(jié)點）,C、用于決,定,定被拋棄or被修剪的,節(jié),節(jié)點（博羿,中,中常用，其,它,它不常見）,。。。,,,基本,思,思想,啟發(fā),式,式搜,索,索過,程,程中,,要,要對OPEN,表,表進,行,行排,序,序,,這,這,就,就需,要,要有一,種,種方,法,法來,計,計算,待,待擴,展,展節(jié),點,點有,希,希望,通,通向,目,目標(biāo),節(jié),節(jié)點,的,的不,

30、同,同程,度,度,,我,我們,總,總是,希,希望,能,能找,到,到最,有,有希,望,望通,向,向目,標(biāo),標(biāo)節(jié),點,點的,待,待擴,展,展節(jié),點,點優(yōu),先,先擴,展,展。,希望,的,的量,度,度就,是,是通,過,過估,價,價函,數(shù),數(shù)f,（,（n,）,）來,描,描述,的,的,,,,估價,函,函數(shù),：,：定,義,義為,從,從初,始,始節(jié),點,點經(jīng),過,過n,節(jié),節(jié)點,到,到達,目,目的,節(jié),節(jié)點,的,的路,徑,徑的,最,最小,代,代價,的,的估,計,計值,，,，,X,W,Z,g(X),h,(X),估價,函,函數(shù),的,的形,式,式為f(n)=g(n)+h(n),g（n）,—,—是到目,前,前為,止,

31、止,,從,從s,到,到n,的,的最,小,小路,徑,徑（實,際,際值,）,）,h（n）,—,—n節(jié),點,點到,目,目標(biāo),節(jié),節(jié)點,最,最佳,路,路徑,的,的估,計,計值,，,，體,現(xiàn),現(xiàn)了,啟,啟發(fā),信,信息,通常f（n）,由,由經(jīng),驗,驗和,直,直覺,得,得到,的,的，,有,有很,多,多種,取,取法,，,，關(guān),鍵,鍵在,于,于h,（,（n,）,）。,,,e．g．八數(shù)碼,難,難題的估價函數(shù),f（n）=g（n）+h（n）,d（n）：節(jié)點n的深度,w（n）：不在,位,位的數(shù)字個數(shù),p（n）：不在,位,位的數(shù)字離目標(biāo),的,的距離之和,例：右圖（a）,中,中2、8、1、6不在位，w（n）=4 ，p,（,

32、（n）=1+2+1+1=5；,（,（b）6、8、2、1不在位，w（n）=4,，,，p（n）=3+2+2+2=9,2 8 3,1 6 4,7 5,6 8 3,2 1 4,7 5,a b c,8 1 2,6 3,7 5 4,,,s（n）：沿著,周,周圍那些非中心,方,方格上依順時針,方,方向檢查n格局,中,中每一將牌，如,果,果其后緊跟的將,牌,牌正好是目標(biāo)格,局,局中該將牌的后,續(xù),續(xù)者，則該將牌,得,得0分，否則得2分；在中中方,格,格上有將牌得1,分,分

33、，無得0分；,將,將所有將牌得分,之,之和即為s（n,）,）。圖（c）中s（a）=6。,2 8 3,1 6 4,7 5,6 8 3,2 1 4,7 5,a b c,8 1 2,6 3,7 5 4,,,例子:eight-puzzle,評價函,數(shù),數(shù),f(n) =d(n)+ W(n),d(n):,節(jié),節(jié)點n,的,的深度;,W(n):與,目,目標(biāo)相,比,比,,錯,錯位的,數(shù),數(shù)字數(shù),目,目，即,不,不在位,的,的數(shù)字,個,個數(shù);,1,,2,,3,,8,,4,,7,

34、,6,5,,2,,8,,3,,1,6,,4,,7,,,,5,,初始狀,態(tài),態(tài),目標(biāo)狀,態(tài),態(tài),,,283,164,75,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 3,1 8 4,7

35、6 5,2 3,1 8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,8 4,7 6 5,1 2 3,7 8 4,6 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目標(biāo),1,2,3,4,5,6,,,由前例,看,看出,,與,與深,度,度優(yōu)先,搜,搜索和,寬,寬度優(yōu),先,先搜索,相,相比較, 啟,發(fā),發(fā)式搜,索,索大大,減,減少了,搜,搜索范,圍,圍,,大,大大減,少,少了擴,展,展的節(jié),點,

36、點,,大,大大減,少,少了生,成,成的節(jié),點,點,,從,從而達,到,到降低,問,問題復(fù),雜,雜度,,提,提高,算,算法的,效,效率的,目,目的。,,,估價函,數(shù),數(shù)的進,一,一步說,明,明,n,S,g*(n),h*(n),g,f*(n)=g*(n)+h*(n)：,從s經(jīng),過,過n到g的最,短,短路徑,g*(n),：,：從s到n,的,的最短路徑,h*(n),：,：從n到g,的,的最短路徑,f（n）=g（n）+h（n）：,從,從s經(jīng)過n,到,到g的最短,路,路徑的估計,值,值,g(n)、h(n),分別是g*(n)、h*(n),的,的估計值,,,g(n),一般,取實際走過,的,的路徑的費,用,用和.

37、,g(n),?,g*(n),隨著算法的,執(zhí),執(zhí)行，由于指針的,變,變動，,g(n),會下降.,h,?,0,沒有啟發(fā)式,信,信息;,,,啟發(fā)式搜索,算,算法,A算法,A*算法,,,A,算法,在Graphsearch過程中,，,，如果第8,步,步的重排open表是,依,依據(jù)f（n,）,）=g（n,）,）+h（n,）,）進行的，,則,則稱該過程,為,為A算法。,g(n)取,實,實際走過的,路,路徑的費用,和,和;,節(jié)點排序是,按,按照f(n)從小到大,排,排;,如前例-九,宮,宮重排問題,,,算法A*,在A算法中,，,，如果滿足,條,條件：,0≤h(n)≤h*(n),則A算法稱,為,為A*算法,。,

38、。,稱h（x）,為,為h*（x,）,）的下界，,它,它表示某種,偏,偏于保守的,估,估計。,啟發(fā)式搜索,算,算法A*又,稱,稱為最佳圖,搜,搜索算法(Optimal Search),。,。,,,,5、經(jīng)典例,題,題（八數(shù)碼,難,難題）：,設(shè)有八數(shù)碼,難,難題，起始,狀,狀態(tài)如右圖,，,，要求找出,九,九宮重排的,最,最終解路徑,，,，并畫框圖,。,。,2 83,1 64,75,,,解法一：,第一步：取,估,估價函數(shù)為f（n）=d（n）+w（n），,則,則顯然按照,定,定義1它是A算法；,第二步：因,為,為w（n）,指,指的是不在,位,位的個數(shù)，,所,所以w（n,）,）=4，即,估,估計

39、只需要,走,走4步即可,到,到達目標(biāo)狀,態(tài),態(tài)，而實際,上,上要到達目,標(biāo),標(biāo)狀態(tài)肯定,要,要大于3步,，,，即w（x,）,）≤w,*,（x），滿,足,足定義，所,以,以是A,*,算法；,第三步：畫,圖,圖，并計算,各,各個狀態(tài)f,（,（n）的值,，,，取f（n,）,）值最小的,節(jié),節(jié)點進行擴,充,充。,(圖見前),,,解法二：取,估,估價函數(shù)為f（n）=d（n）+P（n），,同,同理也是A*算法；,如圖,,,,,TipsA算法,與,與A*算,法,法區(qū)別,區(qū)別在于,在,在A*算,法,法中，0≤h(n)≤h*(n),示例：,八數(shù)碼難,題,題中,h(n),的,的三種定,義,義,h(n)=w(n),

40、 h(n)=p(n)-A*算,法,法,h(n)=p(n)+3s(n)-A算法,,,A*算法,具,具有可采,納,納性,一般地說,對,對任意一,個,個圖,,當(dāng),當(dāng)s到目,標(biāo),標(biāo)節(jié)點有,一,一條路徑,存,存在時,,如,如果搜,索,索算法總,是,是在找到,一,一條從s,到,到目標(biāo)節(jié),點,點的最佳,路,路徑上結(jié),束,束, 則,稱,稱該搜索算法是可,采,采納的(Admissibility)。,A*就具,有,有可采納,性,性,即當(dāng)問題,有,有解時,A*一,定,定能找到,一,一條到達,目,目標(biāo)節(jié)點,的,的最佳路,徑,徑。（why？）,證明見參,考,考資料-A*算法,具,具有可采,納,納性,考慮h(n)≡0,的

41、,的情況！,！,?。。?,,A*算法,的,的理論意,義,義,A*算法,的,的理論意,義,義在于給,出,出了求解,最,最佳解的,條,條件,h(n),≤,≤ h*(n),對給定的,問,問題,函,數(shù),數(shù)h*(n)在問,題,題有解的,條,條件下客,觀,觀上是存,在,在的。但,在,在問題求,解,解過程中,不,不可能都,明,明確知道,。,。因此,,對,對實際,問,問題,,能,能不能使,所,所定義的,啟,啟發(fā)函數(shù),滿,滿足下界,范,范圍條件? 這是,個,個問題。,如,如果困難,很,很大,,那,那未A*,算,算法的實,際,際應(yīng)用就,會,會受到限,制,制。,,,以前面-八數(shù),碼,碼難題為例,定義h(n),為,為

42、任意節(jié)點與,目,目標(biāo)之間的差,異,異,若取= w(n)(將牌不,在,在位個數(shù)),,那,那未很容易,看,看出, 盡管,我,我們對具體的h*(n)是,多,多少很難確切,知,知道, 但根,據(jù),據(jù)“不在位”,將,將牌個數(shù)這個,估,估計, 就能,得,得出至少要移動W(n)步才能到達目標(biāo), 顯然有h(n) =W(n)≤h*(n)。,進一步考慮任,意,意節(jié)點與目標(biāo),之,之間距離的信,息,息, 即取h(n) =p(n),p(n)定義,為,為每一個將牌,與,與其目標(biāo)位置,之,之間距離(不,考,考慮夾在其間,的,的將牌)的總,和,和,那未同樣,能,能斷定至少也要移動p(n)步才能達到目標(biāo),，,，仍然有P(n)≤

43、h*(n)。,,,啟發(fā)信息的強,度,度的進一步分,析,析,強：降低搜索工作,量,量，但可能導(dǎo)致,找,找不到最優(yōu)解,弱：一般導(dǎo)致工作,量,量加大，極限,情,情況下變?yōu)槊?目,目搜索，但可能可以,找,找到最優(yōu)解,,,h(n)取不,同,同函數(shù)時的八,數(shù),數(shù)碼難題求解,情,情況進行比較, 比較h(n) = 0,、,、h(n)= W(n),和,和h(n)= p(n),三,三種情況的求,解,解結(jié)果。,①,①h(n) = 0: 即啟發(fā)函,數(shù),數(shù)啟發(fā)信息為0, f(n) = h(n) + g(n) =g(n)＝,d(n)(搜,索,索深度),,此,此實際上是寬,度,度優(yōu)先搜索。,②,② h(n) = W(n):

44、 即啟,發(fā),發(fā)函數(shù)取將牌,不,不在位的信息, f(n)= h(n) + g(n) = W(n) +d(n) (,搜,搜索深度)。,③,③ h(n)= p(n): 即啟發(fā),函,函數(shù)取每一個,將,將牌與其目標(biāo),位,位置之間距離,的,的總和的信息,,,實際上①中h(n) =0,≤,≤h*(n)，,②和③均已證,明,明W(n)≤h*(n)，P（n）≤h*(n)，即3種算法都是A*算法。,比較搜索空間,，,，分析啟發(fā)信息,強,強弱的效果：,啟發(fā)函數(shù),h(n) = 0,h(n) = W(n),h(n) = p(n),擴展節(jié)點數(shù),26,6,5,生成節(jié)點數(shù),46,13,11,,,附：評價搜索,算,算法的指標(biāo),

45、1、外顯率（Penetrance）,P=L/T,L — 從初,始,始狀態(tài)到目標(biāo),狀,狀態(tài)的長度；,T — 從初,始,始狀態(tài)到目標(biāo),狀,狀態(tài)所產(chǎn)生的,所,所有狀態(tài)的個,數(shù),數(shù)；,顯然P=1時,，,，說明有效路,徑,徑所經(jīng)歷的節(jié),點,點都有用,,,2、有效分支,數(shù),數(shù)（EffectiveBranching Factor）,B —搜索過,程,程中，平均每,個,個節(jié)點產(chǎn)生的,分,分支數(shù)目；,因為每個節(jié)點,產(chǎn),產(chǎn)生的平均分,支,支數(shù)為B，所,以,以從初始到目,標(biāo),標(biāo)狀態(tài)產(chǎn)生的,總,總分支數(shù)T為,：,：,,,本章回顧,教學(xué)內(nèi)容：本,章,章在上一章知,識,識表示的基礎(chǔ),上,上研究問題求,解,解的方法，是,人,人工智能研究,的,的又一核心問,題,題。本章主要,介,介紹基本的搜,索,索技術(shù),教學(xué)重點：圖,搜,搜索策略、啟,發(fā),發(fā)式搜索,教學(xué)難點：啟,發(fā),發(fā)式搜索,教學(xué)方法：課,堂,堂教學(xué)為主，,輔,輔以恰當(dāng)?shù)膶?驗,驗。注意結(jié)合,前,前面所學(xué)知識,表,表示的基礎(chǔ)內(nèi),容,容，將其與問,題,題求解方法融,為,為一體。,教學(xué)要求：重,點,點掌握一般圖,搜,搜索策略，掌,握,握各種搜索方,法,法，尤其是啟,發(fā),發(fā)式搜索中的A*算法。,,,homework,選做：利用,A*算法求解,九,九宮重排問題,。,。,要求：同前,---- THE END ----,,,