人工智能第二章下課件

2.4啟發(fā)式搜索搜索技術(shù)的應(yīng)用－智能搜索引擎啟發(fā)式搜索涉及的基本概念基本的啟發(fā)式搜索方法代價(jià)樹的廣度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹廣度優(yōu)先搜索)代價(jià)樹的深度優(yōu)先搜索(局部優(yōu)先搜索)代價(jià)樹有界深度優(yōu)先搜索局部擇優(yōu)A算法A算法(全局優(yōu)先搜索)2.4啟發(fā)式搜索搜索技術(shù)的應(yīng)用－智能搜索引擎1啟發(fā)式搜索概念啟發(fā)式搜索與無信息搜索無信息（盲目）搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中 獲得的中間信息并不改變控制策略。81

啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo) 搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并 找到最優(yōu)解。啟發(fā)性信息評估函數(shù)啟發(fā)式搜索概念啟發(fā)式搜索與無信息搜索2評估函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)表示：f(x)=g(x)+h(x)g(x)是從初始結(jié)點(diǎn)S0到x實(shí)際代價(jià)h(x)是從x到目標(biāo)結(jié)點(diǎn)Sg的最佳路徑的估計(jì)代價(jià),啟發(fā)性信息的函數(shù)描述。例重排九宮問題f(x)=d(x)+h(x)評估函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)3代價(jià)的計(jì)算邊代價(jià)：從父節(jié)點(diǎn)到子節(jié)點(diǎn)的代價(jià)表示：c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)例：c(s0,A)=2c(A,C)=4代價(jià)：從一個(gè)節(jié)點(diǎn)經(jīng)過一條支路到另一個(gè)節(jié)點(diǎn)所支付的代價(jià)。表示：g(x)表示從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)x的代價(jià)例:g(A)=g(s0)+c(s0,A)=0+2=2

g(C)=g(A)+c(A,C)=2+4=6代價(jià)樹：邊上標(biāo)有代價(jià)的搜索樹s0ACB324s0ABC234代價(jià)的計(jì)算邊代價(jià)：從父節(jié)點(diǎn)到子節(jié)點(diǎn)的代價(jià)s0ACB324s042.4.1代價(jià)驅(qū)動(dòng)的搜索策略代價(jià)樹的廣度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹廣度優(yōu)先搜索)代價(jià)樹的深度優(yōu)先搜索2.4.1代價(jià)驅(qū)動(dòng)的搜索策略代價(jià)樹的廣度優(yōu)先搜索5代價(jià)樹的廣度優(yōu)先搜索基本思想搜索過程實(shí)例存在問題解決方法(動(dòng)態(tài)規(guī)劃法）代價(jià)樹的廣度優(yōu)先搜索基本思想6基本思想open表的節(jié)點(diǎn)順序按的節(jié)點(diǎn)代價(jià)排列（從小到大）基本思想open表的節(jié)點(diǎn)順序按的節(jié)點(diǎn)代價(jià)排列（從小到大）7搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)，并按各個(gè)節(jié)點(diǎn)的代價(jià)對表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順序），然后轉(zhuǎn)（2）步。搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=08例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用代寬演示.pptSADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中9代價(jià)樹的廣度優(yōu)先搜索（例）1234567101112138919202115171814S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)B2(11)B3(13)E3(10)E2(12)16D3(14)F3(16)B4(15)F2(14)C3(17)A3(15)C2(15)34445552454224544443代價(jià)樹的廣度優(yōu)先搜索（例）1234567101112138910Open表（代價(jià)樹的廣度優(yōu)先搜索）初始(S(0))1(A1(3),D1(4))2(D1(4),B1(7),D2(8))3(E1(6),B1(7),D2(8),A2(9))4(B1(7),D2(8),A2(9),F1(10),B2(11))5(D2(8),A2(9),F1(10),B2(11),C1(11),E2(12))6(A2(9),F1(10),E3(10),B2(11),C1(11),E2(12))7(F1(10),E3(10),B2(11),C1(11),E2(12),B3(13))8(E3(10),B2(11),C1(11),E2(12),B3(13),T1(13))9(B2(11),C1(11),E2(12),B3(13),T1(13),F2(14),B4(15))10(C1(11),E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15))11(E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15))12(B3(13),T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16))13(T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16),C3(17))14T1(13)為目標(biāo)節(jié)點(diǎn)，結(jié)束。Open表（代價(jià)樹的廣度優(yōu)先搜索）11算法討論存在問題改進(jìn)方法算法討論存在問題12動(dòng)態(tài)規(guī)劃法基本思想搜索過程實(shí)例動(dòng)態(tài)規(guī)劃法基本思想13基本思想當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價(jià)最小的路徑基本思想當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價(jià)最小的路徑14搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)，若新出現(xiàn)的節(jié)點(diǎn)是多條路徑都到達(dá)的節(jié)點(diǎn)，則只選代價(jià)最小的路徑，其余刪去，并按各個(gè)節(jié)點(diǎn)的代價(jià)對表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順），然后轉(zhuǎn)（2）步。搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=015例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用動(dòng)態(tài)規(guī)劃.pptSADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中16動(dòng)態(tài)規(guī)劃法（例）123456710118914S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)E2(12)34445555423B2(11)動(dòng)態(tài)規(guī)劃法（例）123456710118914S(0)D1(17Open表（動(dòng)態(tài)規(guī)劃法）初始(S(0))1(A1(3),D1(4))2(D1(4),B1(7),D2(8))（刪除）3(E1(6),B1(7),A2(9))4(B1(7),F1(10),B2(11))5(F1(10),C1(11),E2(12))6(C1(11),T1(13))7(T1(13))8結(jié)束Open表（動(dòng)態(tài)規(guī)劃法）18代價(jià)樹的深度優(yōu)先搜索基本思想搜索過程實(shí)例算法討論代價(jià)樹的深度優(yōu)先搜索基本思想19基本思想：在剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，即表的首部存放剛擴(kuò)展的所有子節(jié)點(diǎn)（按代價(jià)從小到大排序）搜索過程：1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按代價(jià)從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步?；舅枷耄涸趧倲U(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，20例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用SADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中21代價(jià)樹的深度優(yōu)先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E1(12)D3(14)F1(16)3444552410T1(19)代價(jià)樹的深度優(yōu)先搜索（例）123456789S(0)D1(422Open表（代價(jià)樹的深度優(yōu)先搜索）初始(S(0))1(A1(3),D1(4))2(B1(7),D2(8),D1(4))3(C1(11),E2(12),D2(8),D1(4))4(E1(12),D2(8),D1(4))5(D3(14),F1(16),D2(8),D1(4))6(F1(16),D2(8),D1(4))7(T1(19),D2(8),D1(4))8T1(19）為目標(biāo)節(jié)點(diǎn)結(jié)束Open表（代價(jià)樹的深度優(yōu)先搜索）23283147652831476523184765283147652831647583214765283714651（0）3(1)4(1)5(1)7(2)例2代價(jià)樹的深度優(yōu)先搜索（括號中為代價(jià)）2（1）6(2)832147659(4)832147658132476510(4)8(3)283283232832838248132476513824765813724651238476515(6)（例2續(xù)）11(5)解的路徑：1-2-6-8-10-11-14-16-1814(6)1382476517(8)1382476516(7)813247658132647512(5)13(5)18(8)8131381312315(6)（例2續(xù)2528314765283147652318476528314765283164751（0）3(1)4(1)5(1)例2換一條路徑2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）26算法討論存在的問題解決方法算法討論存在的問題27代價(jià)樹的有界深度優(yōu)先搜索基本思想搜索過程實(shí)例代價(jià)樹的有界深度優(yōu)先搜索基本思想28基本思想當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一個(gè)子節(jié)點(diǎn)計(jì)算估值，并選擇其中最小的先擴(kuò)展?；舅枷氘?dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一個(gè)子節(jié)點(diǎn)計(jì)算估值29代價(jià)樹的有界深度優(yōu)先搜索過程1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.IFd(n)=規(guī)定深度THENGO(2)7.擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并將其子節(jié)點(diǎn)按估價(jià)值從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步。代價(jià)樹的有界深度優(yōu)先搜索過程1.將初始節(jié)點(diǎn)放入OPEN表，令30例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用SADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中31代價(jià)樹的有界深度優(yōu)先搜索（例）dm=412345131467101516891114S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E3(6)F3(10)T1(13)C1(11)E2(10)E1(12)12D3(14)F1(16)B2(15)F2(14)3444555254224543B3(11)代價(jià)樹的有界深度優(yōu)先搜索（例）dm=4123451314632代價(jià)樹搜索的總結(jié)優(yōu)點(diǎn)不足：局限性代價(jià)樹搜索的總結(jié)優(yōu)點(diǎn)3328314765283147652318476528314765283164751（0）3(1)4(1)5(1)九宮問題使用代價(jià)的局限性2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）342.4.2A算法啟發(fā)性函數(shù)A算法A*算法算法討論2.4.2A算法啟發(fā)性函數(shù)35啟發(fā)性函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)表示：f(x)=g(x)+h(x)g(x)是從初始結(jié)點(diǎn)S0到x實(shí)際代價(jià)h(x)是從x到目標(biāo)結(jié)點(diǎn)Sg的最佳路徑的估計(jì)代價(jià),啟發(fā)性信息的函數(shù)描述。例重排九宮問題啟發(fā)性函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)36例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿足條件則空格左移R2:如果滿足條件則空格上移R3:如果滿足條件則空格右移R4:如果滿足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號28314765

12384765例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八37解：f(n)=d(n)+W(n)取g(n)=d(n)，h(n)=W(n)。d(n)表示節(jié)點(diǎn)n在搜索樹中的深度它說明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，W(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)，作為啟發(fā)信息。一般來說，某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多，說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。對初始節(jié)點(diǎn)S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sg解：f(n)=d(n)+W(n)取g(n)=d(38希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。希望：39A算法概述概念：在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。類型：可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。全局擇優(yōu)：從Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。局部擇優(yōu)：僅從剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。A算法概述概念：40局部擇優(yōu)A算法基本思想：當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一個(gè)子節(jié)點(diǎn)計(jì)算估值，并選擇其中最小的先擴(kuò)展。搜索過程：1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并將其子節(jié)點(diǎn)按估價(jià)值從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步。局部擇優(yōu)A算法基本思想：當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一41局部擇優(yōu)A算法例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿足條件則空格左移R2:如果滿足條件則空格上移R3:如果滿足條件則空格右移R4:如果滿足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號28314765

12384765局部擇優(yōu)A算法例：重排九宮問題例：重排九宮問題。在3×3的方42

f(n)=d(n)+W(n)。d(n)表示節(jié)點(diǎn)n在搜索樹中的深度它說明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，W(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)，作為啟發(fā)信息。對初始節(jié)點(diǎn)S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sgf(n)=d(n)+W(n)。2843283147652831476523184765283147652831647583214765283714651（3）3(4)4(5)5(5)7(6)局部擇優(yōu)A算法，例2（4）6(5)832147659(8)832147658132476510(7)8(6)283283232832838448132476513824765813724651238476515(10)局部擇優(yōu)A算法，例(續(xù)）11(8)解的路徑：1-2-6-8-10-11-14-16-1814(9)1382476517(10)1382476516(8)813247658132647512(9)13(9)18(8)8131381312315(10)局部擇45算法討論局部擇優(yōu)A算法存在的問題解決方法算法討論局部擇優(yōu)A算法存在的問題46限界局部擇優(yōu)A算法法1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.IFd(n)=規(guī)定深度THENGO(2)7.擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并將其子節(jié)點(diǎn)按估價(jià)值從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步。限界局部擇優(yōu)A算法法1.將初始節(jié)點(diǎn)放入OPEN表，令g(s047限界局部擇優(yōu)：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿足條件則空格左移R2:如果滿足條件則空格上移R3:如果滿足條件則空格右移R4:如果滿足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號f(x)=d(x)+h(x)d(x):節(jié)點(diǎn)x的深度，深度=4h(x):節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。28314765

12384765限界局部擇優(yōu)：重排九宮問題例：重排九宮問題。在3×3的方格棋48283147652831476523184765283147652831647583214765283714651（3）3(4)4(5)5(5)7(6)限界局部擇優(yōu)搜索（例）d=42（4）6(5)832147659(9)832147658132476510(8)8(6)231847652318476514(4)1238476512384765123784652837146511(8)283746152837146512(9)13(10)15(6)18(6)16(4)17(4)28328323283283849Open表的變化(限界局部擇優(yōu)搜索法）初始(1(3))1(2(4),3(4),4(5),5(5))2(6(5),7(6),3(4),4(5),5(5))3(8(6),7(6),3(4),4(5),5(5))4(10(8),9(9),7(6),3(4),4(5),5(5))d=45(7(6),3(4),4(5),5(5))d=26(11(8),3(4),4(5),5(5))d=37(12(9),13(10),3(4),4(5),5(5))d=48(3(4),4(5),5(5))d=19(14(4),15(6),4(5),5(5))d=27(16(4),15(10),3(4),4(5),5(5))d=38(17(4),18(6),15(10),3(4),4(5),5(5))d=4917(4)為目標(biāo)節(jié)點(diǎn)，結(jié)束

Open表的變化(限界局部擇優(yōu)搜索法）50算法討論局部擇優(yōu)搜索方法評價(jià)與深度優(yōu)先搜索比較缺陷算法討論局部擇優(yōu)搜索方法評價(jià)51全局擇優(yōu)搜索A算法描述(1)把初始節(jié)點(diǎn)S0放入Open表中，f(S0)=g(S0)+h(S0)；

(2)如果Open表為空，則問題無解

，失敗退出；

(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；

(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到問題的解，成功退出；

(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；

(6)擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)ni(i=1,2,…)，計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值f(ni)(i=1,2,…)，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后將這些子節(jié)點(diǎn)放入Open表中；

(7)根據(jù)各節(jié)點(diǎn)的估價(jià)函數(shù)值，對Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序；

(8)轉(zhuǎn)第(2)步。

全局擇優(yōu)搜索A算法描述(1)把初始節(jié)點(diǎn)S0放入Open表中，52例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿足條件則空格左移R2:如果滿足條件則空格上移R3:如果滿足條件則空格右移R4:如果滿足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號f(x)=d(x)+h(x)d(x):節(jié)點(diǎn)x的深度，h(x):節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。28314765

12384765例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八5328314765283147652318476528314765283164758321476528371465231847652318476512384765123847651（3）3(4)4(5)5(5)7(6)A算法（例）2（4）解的路徑：1－3－8－10－116(5)8(4)9(6)10(4)1237846511(4)12(6)28328323283283854Open表的變化(A算法）初始(1(3))1(2(4),3(4),4(5),5(5))2(3(4),4(5),5(5),6(5),7(6))3(8(4),4(5),5(5),6(5),7(6),9(6))4(10(4),4(5),5(5),6(5),7(6),9(6))5(11(4),4(5),5(5),6(5),7(6),9(6),12(6))611(4)為目標(biāo)節(jié)點(diǎn)，結(jié)束

Open表的變化(A算法）55算法討論全局擇優(yōu)搜索A算法評價(jià)：如何找到最優(yōu)解.算法討論全局擇優(yōu)搜索A算法評價(jià)：56目標(biāo)尋找最佳全局搜索算法A*A*算法總能找到最優(yōu)解使擴(kuò)展結(jié)點(diǎn)數(shù)盡量少方法：對啟發(fā)式函數(shù)進(jìn)行限制目標(biāo)尋找最佳全局搜索算法A*57目標(biāo)1：算法的可采納性在問題有解的情況下，若一個(gè)搜索過程總能找到最優(yōu)解，則稱該算法具有可采納性。可采納性的衡量：f*(n)=g*(n)+h*(n)例重排九宮問題f(x)=d(x)+h(x)

h1(x)=0

h2(x):錯(cuò)位棋牌的個(gè)數(shù)h3(x):每個(gè)將牌與其目標(biāo)位置之間的距離和2831476512384765目標(biāo)1：算法的可采納性在問題有解的情況下，若一個(gè)搜索過程總能5823184765283147652831647583214765283714652318476523184765281437652831457683214765283714651238476523418765281437652831457628364175283167548321476581324765283746152837146512384765345283164752831647567891011121314151617181920212324252622234185762341876528143765248137652831457628315746281437652481376528316754281637548342176581324765832147658132476528374615237846152837461528371654解的路徑：1－3－8－16－26283147652272829303132333435363738394041424344283147651A*算法（例h1(x)=0<=h*(n))擴(kuò)展節(jié)點(diǎn)數(shù)：25生成節(jié)點(diǎn)數(shù)：44232832838328325928314765283147652318476528314765283164758321476528371465231847652318476512384765123847651（3）3(4)4(5)5(5)7(6)A*算法(例)h2(x)=w(x）<=h*(n)2（4）解的路徑：1－3－8－10－116(5)8(4)9(6)10(4)1237846511(4)12(6)擴(kuò)展節(jié)點(diǎn)數(shù)：10生成節(jié)點(diǎn)數(shù)：12283283232832838602831476528314765231847652831476528316475231847652318476512384765123847651（4）3(4)4(6)5(6)A*算法(例)h3(x)=p(x)<=h(n)2（6）解的路徑：1－3－6－8－96(4)7(6)8(4)123784659(4)10(6)擴(kuò)展節(jié)點(diǎn)數(shù)：4生成節(jié)點(diǎn)數(shù)：10283283232832832612831476528314765231847652831476528316475231847652318476512384765123847651h*=4,g*=1W=3P=3,f=4啟發(fā)式函數(shù)比較(例)h2(x)=w(x)h3(x)=p(x)W=3P=5,f=6h*=2,g*=2W=3

P=2f=4h*=1,g*=3W=1P=1,f=412378465h*=4,g*=0W=3P=4,f=436289h*=0,g*=4W=0P=0,f=44W=4P=5,f=65W=4P=5,f=67W=4P=4,f=610W=2P=2,f=6擴(kuò)展節(jié)點(diǎn)數(shù)：4生成節(jié)點(diǎn)數(shù)：928328323283283262看出規(guī)律了嗎？看出規(guī)律了嗎？63最佳全局搜索算法A*A*算法含義在A算法中，如果滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。最佳全局搜索算法A*A*算法含義64A*算法的采納性證明定理(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。證明見書定理4.1、定理4.2、定理4.3A*算法的采納性證明定理(可采納性定理)：65A*算法效率問題A*算法評價(jià)如何設(shè)計(jì)搜索算法找到最優(yōu)解并使擴(kuò)展的節(jié)點(diǎn)數(shù)盡可能少.A*算法效率問題A*算法評價(jià)66s(10)A(1)B(5)C(8)G目標(biāo)631118另一個(gè)例子(有h(n)<h*(n)函數(shù)）：OPEN表CLOSED表s(10)s(10)SA(7)SB(8)SC(9)SA(7)s(10)SB(8)SC(9)SAG(14)SBA(5)SC(9)SAG(14)SC(9)SBAG(12)SAG(14)SCB(7)SBAG(12)SAG(14)

SCBA(4)SBAG(12)SAG(14)SCBAG(11)SBAG(12)SAG(14)SB(8)SA(7)s(10)SBA(5)SB(8)SA(7)s(10)SC(9)SBA(5)SA(7)s(10)SCB(7)SC(9)SBA(5)SA(7)s(10)SCBA(4)SCB(7)SC(9)

SBA(5)SA(7)s(10)SCBAG(11)s(10)A(1)B(5)C(8)G目標(biāo)631118另一個(gè)67sABCG目標(biāo)631118一個(gè)例子(無H函數(shù)）：OPEN表CLOSED表s(10)s(10)SC(1)SB(3)SA(6)SC(1)s(10)SCB(2)SB(3)SA(6)SCBA(3)SB(3)SA(6)SB(3)SA(6)SCBAG(11)SBA(4)SA(6)SCBAG(11)

SA(6)SCBAG(11)SBAG(12)SCBAG(11)SBAG(12)SAG(14)SCB(2)SC(1)s(10)SCBA(3)SCB(2)SC(1)s(10)SB(3)SCBA(3)SCB(2)SC(1)s(10)SBA(4)SB(3)SCBA(3)SCB(2)SC(1)s(10)SA(6)SBA(4)SB(3)SCBA(3)SCB(2)SC(1)s(10)sABCG目標(biāo)631118一個(gè)例子(無H函數(shù)）：OPEN表68目標(biāo)2：A*算法效率討論A*算法評價(jià)如何設(shè)計(jì)搜索算法找到最優(yōu)解并使擴(kuò)展的節(jié)點(diǎn)數(shù)盡可能少.目標(biāo)2：A*算法效率討論A*算法評價(jià)69出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)631118出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到70解決的途徑對h加以限制能否對h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。解決的途徑對h加以限制71改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性改進(jìn)的條件可采納性不變72對h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對所有節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)，滿足 h(ni)-h(nj)≤c(ni,nj) h(t)=0(t為目標(biāo)節(jié)點(diǎn)） 或h(ni)≤c(ni,nj)+h(nj) h(t)=0則稱h是單調(diào)的。njh(nj)h(ni)nic(ni,nj)h(n)t對h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對所有節(jié)點(diǎn)ni和nj，73實(shí)例證明：例1修改h(n)s(10)A(1)B(5)C(8)G目標(biāo)631118C(9)B(8)A(7)G(0)實(shí)例證明：例1修改h(n)s(10)A(1)B(5)C(8)74s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子(修改后h(n))：OPEN表CLOSED表s(10)s(10)SC(10)SB(11)SA(13)

SC(10)s(10)SCB(10)SB(11)SA(13)SCBA(10)SB(11)SA(13)

SCBAG(11)SB(11)SA(13)SCBAG(11)

SCB(10)SC(10)s(10)SCBA(10)SCB(10)SC(10)s(10)

C(9)A(7)B(8)s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例75理論證明定理4.5如果h滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點(diǎn)n時(shí)，該節(jié)點(diǎn)就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。在h(n)滿足單調(diào)性限制下的A*算法常被稱為改進(jìn)的A*算法。理論證明定理4.5如果h滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點(diǎn)76例2：修改h(n)SADBTC1119163146181h=20h=14h=8h=1h=4h=19h=18h=17h=16h=0例2：修改h(n)SADBTC1119163146181h=77總結(jié)：實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵算法的完備性算法的可采納性啟發(fā)函數(shù)強(qiáng)弱對結(jié)果的影響總結(jié)：實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵算法的完備性78算法的完備性

對于一類可解的問題和一個(gè)搜索過程，如果運(yùn)用該搜索過程一定能求得該類問題得解，則稱該搜索過程為完備的，否則為不完備的。算法的完備性對于一類可解的問題和一個(gè)搜索過程，如果運(yùn)用79算法的可采納性可納性的含義：對任一狀態(tài)空間圖，當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí)，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。算法的可采納性可納性的含義：80啟發(fā)函數(shù)強(qiáng)弱對結(jié)果的影響1

啟發(fā)函數(shù)強(qiáng)弱的衡量：h(n)接近h*(n)的程度理想情況：h(n)＝h*(n)，實(shí)際上:h(n)<=h*(n)(越接近越好)原因：A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。啟發(fā)函數(shù)強(qiáng)弱對結(jié)果的影響1啟發(fā)函數(shù)強(qiáng)弱的衡量：h(n)接近81啟發(fā)函數(shù)強(qiáng)弱對結(jié)果的影響2

h(n)滿足單調(diào)性限制下的A*算法更好原因：能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑。在h(n)滿足單調(diào)性限制下的A*算法常被稱為改進(jìn)的A*算法。啟發(fā)函數(shù)強(qiáng)弱對結(jié)果的影響2h(n)滿足單調(diào)性限制下的A*算822.5圖搜索策略總結(jié)基本思想圖搜索分類2.5圖搜索策略總結(jié)基本思想83狀態(tài)空間搜索的基本思想先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。狀態(tài)空間搜索的基本思想先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)84圖搜索分類無信息搜索搜索按預(yù)定的規(guī)則進(jìn)行，不使用與問題有關(guān)的啟發(fā)式信息啟發(fā)式搜索搜索中使用與問題有關(guān)的啟發(fā)式信息,并以這些啟發(fā)式信息指導(dǎo)搜索過程(可以提高效率)圖搜索分類無信息搜索85本章小結(jié)搜索策略狀態(tài)空間搜索無信息搜索啟發(fā)式搜索搜索方法的關(guān)系參考第4.1,4.2,4.3節(jié)本章小結(jié)搜索策略86283147652318476528314765283164758321476528371465231847652318476528143765283145768321476528371465123847652341876528143765283145762836417528316754832147658132476528374615283714651238476513452831647528316475678910111213141516171819202123242526寬度優(yōu)先搜索圖22234185762341876528143765248137652831457628315746281437652481376528316754281637548342176581324765832147658132476528374615237846152837461528371654解的路徑：1－3－8－16－26283147652272829303132333435363738394041424344283232832838328872831476528314765231847652831476528316475832147652837146583214765832147658132476513456789102深度優(yōu)先搜索圖28328323283283888834217651183421765834215768342176584231765834261753482176583472165121314191815163482176517深度優(yōu)先搜索圖（續(xù)）8341183483483484889283147652831476523184765283147652831647583214765283714652318476583214765283714651238476583214765813247652837461528371465123847651345671481116910121317有界深度優(yōu)先搜索圖dm=4go22解的路徑：1－3－14－16－17283283232832838902.4啟發(fā)式搜索搜索技術(shù)的應(yīng)用－智能搜索引擎啟發(fā)式搜索涉及的基本概念基本的啟發(fā)式搜索方法代價(jià)樹的廣度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹廣度優(yōu)先搜索)代價(jià)樹的深度優(yōu)先搜索(局部優(yōu)先搜索)代價(jià)樹有界深度優(yōu)先搜索局部擇優(yōu)A算法A算法(全局優(yōu)先搜索)2.4啟發(fā)式搜索搜索技術(shù)的應(yīng)用－智能搜索引擎91啟發(fā)式搜索概念啟發(fā)式搜索與無信息搜索無信息（盲目）搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中 獲得的中間信息并不改變控制策略。81

啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo) 搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并 找到最優(yōu)解。啟發(fā)性信息評估函數(shù)啟發(fā)式搜索概念啟發(fā)式搜索與無信息搜索92評估函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)表示：f(x)=g(x)+h(x)g(x)是從初始結(jié)點(diǎn)S0到x實(shí)際代價(jià)h(x)是從x到目標(biāo)結(jié)點(diǎn)Sg的最佳路徑的估計(jì)代價(jià),啟發(fā)性信息的函數(shù)描述。例重排九宮問題f(x)=d(x)+h(x)評估函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)93代價(jià)的計(jì)算邊代價(jià)：從父節(jié)點(diǎn)到子節(jié)點(diǎn)的代價(jià)表示：c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)例：c(s0,A)=2c(A,C)=4代價(jià)：從一個(gè)節(jié)點(diǎn)經(jīng)過一條支路到另一個(gè)節(jié)點(diǎn)所支付的代價(jià)。表示：g(x)表示從初始節(jié)點(diǎn)s0到節(jié)點(diǎn)x的代價(jià)例:g(A)=g(s0)+c(s0,A)=0+2=2

g(C)=g(A)+c(A,C)=2+4=6代價(jià)樹：邊上標(biāo)有代價(jià)的搜索樹s0ACB324s0ABC234代價(jià)的計(jì)算邊代價(jià)：從父節(jié)點(diǎn)到子節(jié)點(diǎn)的代價(jià)s0ACB324s0942.4.1代價(jià)驅(qū)動(dòng)的搜索策略代價(jià)樹的廣度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹廣度優(yōu)先搜索)代價(jià)樹的深度優(yōu)先搜索2.4.1代價(jià)驅(qū)動(dòng)的搜索策略代價(jià)樹的廣度優(yōu)先搜索95代價(jià)樹的廣度優(yōu)先搜索基本思想搜索過程實(shí)例存在問題解決方法(動(dòng)態(tài)規(guī)劃法）代價(jià)樹的廣度優(yōu)先搜索基本思想96基本思想open表的節(jié)點(diǎn)順序按的節(jié)點(diǎn)代價(jià)排列（從小到大）基本思想open表的節(jié)點(diǎn)順序按的節(jié)點(diǎn)代價(jià)排列（從小到大）97搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)，并按各個(gè)節(jié)點(diǎn)的代價(jià)對表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順序），然后轉(zhuǎn)（2）步。搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=098例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用代寬演示.pptSADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中99代價(jià)樹的廣度優(yōu)先搜索（例）1234567101112138919202115171814S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)B2(11)B3(13)E3(10)E2(12)16D3(14)F3(16)B4(15)F2(14)C3(17)A3(15)C2(15)34445552454224544443代價(jià)樹的廣度優(yōu)先搜索（例）12345671011121389100Open表（代價(jià)樹的廣度優(yōu)先搜索）初始(S(0))1(A1(3),D1(4))2(D1(4),B1(7),D2(8))3(E1(6),B1(7),D2(8),A2(9))4(B1(7),D2(8),A2(9),F1(10),B2(11))5(D2(8),A2(9),F1(10),B2(11),C1(11),E2(12))6(A2(9),F1(10),E3(10),B2(11),C1(11),E2(12))7(F1(10),E3(10),B2(11),C1(11),E2(12),B3(13))8(E3(10),B2(11),C1(11),E2(12),B3(13),T1(13))9(B2(11),C1(11),E2(12),B3(13),T1(13),F2(14),B4(15))10(C1(11),E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15))11(E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15))12(B3(13),T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16))13(T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16),C3(17))14T1(13)為目標(biāo)節(jié)點(diǎn)，結(jié)束。Open表（代價(jià)樹的廣度優(yōu)先搜索）101算法討論存在問題改進(jìn)方法算法討論存在問題102動(dòng)態(tài)規(guī)劃法基本思想搜索過程實(shí)例動(dòng)態(tài)規(guī)劃法基本思想103基本思想當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價(jià)最小的路徑基本思想當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價(jià)最小的路徑104搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)，若新出現(xiàn)的節(jié)點(diǎn)是多條路徑都到達(dá)的節(jié)點(diǎn)，則只選代價(jià)最小的路徑，其余刪去，并按各個(gè)節(jié)點(diǎn)的代價(jià)對表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順），然后轉(zhuǎn)（2）步。搜索過程1.將初始節(jié)點(diǎn)s0放入OPEN表,令g(s0)=0105例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用動(dòng)態(tài)規(guī)劃.pptSADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中106動(dòng)態(tài)規(guī)劃法（例）123456710118914S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E1(6)F1(10)T1(13)C1(11)E2(12)34445555423B2(11)動(dòng)態(tài)規(guī)劃法（例）123456710118914S(0)D1(107Open表（動(dòng)態(tài)規(guī)劃法）初始(S(0))1(A1(3),D1(4))2(D1(4),B1(7),D2(8))（刪除）3(E1(6),B1(7),A2(9))4(B1(7),F1(10),B2(11))5(F1(10),C1(11),E2(12))6(C1(11),T1(13))7(T1(13))8結(jié)束Open表（動(dòng)態(tài)規(guī)劃法）108代價(jià)樹的深度優(yōu)先搜索基本思想搜索過程實(shí)例算法討論代價(jià)樹的深度優(yōu)先搜索基本思想109基本思想：在剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，即表的首部存放剛擴(kuò)展的所有子節(jié)點(diǎn)（按代價(jià)從小到大排序）搜索過程：1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按代價(jià)從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步?；舅枷耄涸趧倲U(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，110例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用SADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中111代價(jià)樹的深度優(yōu)先搜索（例）123456789S(0)D1(4)A1(3)B1(7)D2(8)C1(11)E1(12)D3(14)F1(16)3444552410T1(19)代價(jià)樹的深度優(yōu)先搜索（例）123456789S(0)D1(4112Open表（代價(jià)樹的深度優(yōu)先搜索）初始(S(0))1(A1(3),D1(4))2(B1(7),D2(8),D1(4))3(C1(11),E2(12),D2(8),D1(4))4(E1(12),D2(8),D1(4))5(D3(14),F1(16),D2(8),D1(4))6(F1(16),D2(8),D1(4))7(T1(19),D2(8),D1(4))8T1(19）為目標(biāo)節(jié)點(diǎn)結(jié)束Open表（代價(jià)樹的深度優(yōu)先搜索）113283147652831476523184765283147652831647583214765283714651（0）3(1)4(1)5(1)7(2)例2代價(jià)樹的深度優(yōu)先搜索（括號中為代價(jià)）2（1）6(2)832147659(4)832147658132476510(4)8(3)2832832328328381148132476513824765813724651238476515(6)（例2續(xù)）11(5)解的路徑：1-2-6-8-10-11-14-16-1814(6)1382476517(8)1382476516(7)813247658132647512(5)13(5)18(8)8131381312315(6)（例2續(xù)11528314765283147652318476528314765283164751（0）3(1)4(1)5(1)例2換一條路徑2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）116算法討論存在的問題解決方法算法討論存在的問題117代價(jià)樹的有界深度優(yōu)先搜索基本思想搜索過程實(shí)例代價(jià)樹的有界深度優(yōu)先搜索基本思想118基本思想當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一個(gè)子節(jié)點(diǎn)計(jì)算估值，并選擇其中最小的先擴(kuò)展?；舅枷氘?dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對每一個(gè)子節(jié)點(diǎn)計(jì)算估值119代價(jià)樹的有界深度優(yōu)先搜索過程1.將初始節(jié)點(diǎn)放入OPEN表，令g(s0)=02.如果OPEN表為空，則問題無解，退出3.把OPEN表的第一個(gè)節(jié)點(diǎn)（記為n節(jié)點(diǎn)）取出放入CLOSED表4.考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。5.若節(jié)點(diǎn)n不可擴(kuò)展轉(zhuǎn)（2）步。6.IFd(n)=規(guī)定深度THENGO(2)7.擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并將其子節(jié)點(diǎn)按估價(jià)值從小到大放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（2）步。代價(jià)樹的有界深度優(yōu)先搜索過程1.將初始節(jié)點(diǎn)放入OPEN表，令120例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。求從S到T的最小交通費(fèi)用SADEBFTC344525443例如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中121代價(jià)樹的有界深度優(yōu)先搜索（例）dm=412345131467101516891114S(0)D1(4)A1(3)B1(7)D2(8)A2(9)E3(6)F3(10)T1(13)C1(11)E2(10)E1(12)12D3(14)F1(16)B2(15)F2(14)3444555254224543B3(11)代價(jià)樹的有界深度優(yōu)先搜索（例）dm=41234513146122代價(jià)樹搜索的總結(jié)優(yōu)點(diǎn)不足：局限性代價(jià)樹搜索的總結(jié)優(yōu)點(diǎn)12328314765283147652318476528314765283164751（0）3(1)4(1)5(1)九宮問題使用代價(jià)的局限性2（1）23184765231847656(2)1238476512384765123784657(2)10(4)8(3)9(4)283283232832831（0）1242.4.2A算法啟發(fā)性函數(shù)A算法A*算法算法討論2.4.2A算法啟發(fā)性函數(shù)125啟發(fā)性函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)表示：f(x)=g(x)+h(x)g(x)是從初始結(jié)點(diǎn)S0到x實(shí)際代價(jià)h(x)是從x到目標(biāo)結(jié)點(diǎn)Sg的最佳路徑的估計(jì)代價(jià),啟發(fā)性信息的函數(shù)描述。例重排九宮問題啟發(fā)性函數(shù)的表示含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)126例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿足條件則空格左移R2:如果滿足條件則空格上移R3:如果滿足條件則空格右移R4:如果滿足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號28314765

12384765例：重排九宮問題例：重排九宮問題。在3×3的方格棋盤上放置八127解：f(n)=d(n)+W(n)取g(n)=d(n)，h(n)=W(n)。d(n)表示節(jié)點(diǎn)n在搜索樹中的深度它說明是用從S0到n的路徑上的單位代價(jià)表示實(shí)際代價(jià)，W(n)表示節(jié)點(diǎn)n中“不在位”的數(shù)碼個(gè)數(shù)，作為啟發(fā)信息。一般來說，某節(jié)點(diǎn)中的“不在位”的數(shù)碼個(gè)數(shù)越多，說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。對初始節(jié)點(diǎn)S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=32

831476512384765S0Sg解：f(n)=d(n)+W(n)取g(n)=d(128希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。希望：129A算法概述概念：在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。類型：可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。全局擇優(yōu)：從Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。局部擇優(yōu)：僅從剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)