【正文】 第三章 一般搜索原理? 盲目搜索? 啟發(fā)式搜索? 歸結(jié)原理2/27/2023 1人工智能講義盲目搜索? 圖搜索策略? 深度優(yōu)先搜索? 寬度優(yōu)先搜索? 等代價(jià)搜索2/27/2023 2人工智能講義一些基本概念? 節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度 =0其它節(jié)點(diǎn)深度 =父節(jié)點(diǎn)深度 +101232/27/2023 3人工智能講義一些基本概念（續(xù) 1）? 路徑設(shè)一節(jié)點(diǎn)序列為 (n0, n1,…,n k)，對(duì)于i=1,…,k ，若節(jié)點(diǎn) ni1具有一個(gè)后繼節(jié)點(diǎn) ni，則該序列稱為從 n0到 nk的路徑。? 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用 C(ni, nj)表示從ni到 nj的路徑的耗散值。2/27/2023 4人工智能講義一些基本概念（續(xù) 1）? 擴(kuò)展一個(gè)節(jié)點(diǎn)生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱為 “擴(kuò)展一個(gè)節(jié)點(diǎn) ”。2/27/2023 5人工智能講義一般的圖搜索算法（GRAPHSEARCH）1, G=G0 (G0=s), OPEN=(s)。2, CLOSED=( )。3, LOOP: IF OPEN=( ) EXIT(FAIL)。4, n=FIRST(OPEN), REMOVE(n, OPEN),ADD(n, CLOSED)。5, IF GOAL(n) EXIT(SUCCESS)。6, EXPAND(n)→{mi}, G=ADD(mi, G)。2/27/2023 6人工智能講義一般的圖搜索算法（續(xù)）7, 標(biāo)記和修改指針：ADD(mj, OPEN), 并標(biāo)記 mj到 n的指針；計(jì)算是否要修改 mk、 ml到 n的指針；計(jì)算是否要修改 ml到其后繼節(jié)點(diǎn)的指針；8, 對(duì) OPEN中的節(jié)點(diǎn)按 某種原則 重新排序；9, GO LOOP；2/27/2023 7人工智能講義深度優(yōu)先搜索? 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的 (最深的 )節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。 “最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展 ”2/27/2023 8人工智能講義深度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( )。2, LOOP: IF OPEN=( ) EXIT (FAIL)。3, n=FIRST(OPEN)。4, IF GOAL(n) EXIT (SUCCESS)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。6, IF DEPTH(n)≥Dm GO LOOP。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, GO LOOP。2/27/2023 9人工智能講義2 31 8 47 6 5 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 47 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 61234 567 89a bcd1 2 3 8 47 6 5目標(biāo)2/27/2023 10人工智能講義深度優(yōu)先搜索的性質(zhì)? 一般不能保證找到最優(yōu)解? 當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制? 最壞情況時(shí)，搜索空間等同于窮舉? 與回溯法的差別：圖搜索? 是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法2/27/2023 11人工智能講義寬度優(yōu)先搜索? 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索使逐層進(jìn)行的，在對(duì)下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 “先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展 ”2/27/2023 12人工智能講義寬度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( )。2, LOOP: IF OPEN=( ) EXIT (FAIL)。3, n=FIRST(OPEN)。4, IF GOAL(n) EXIT (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, GO LOOP。2/27/2023 13人工智能講義2 31 8 47 6 5 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 47 6 5125 6 731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 542/27/2023 14人工智能講義寬度優(yōu)先搜索的性質(zhì)? 當(dāng)問(wèn)題有解時(shí)，一定能找到解? 當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解? 方法與問(wèn)題無(wú)關(guān)，具有通用性? 效率較低? 屬于圖搜索方法2/27/2023 15人工智能講義等代價(jià)搜索? 寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)具有最小代價(jià)路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價(jià)搜索算法 。2/27/2023 16人工智能講義等代價(jià)搜索算法? 算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0。2, LOOP: IF OPEN=( ) EXIT (FAIL)。3, 從 OPEN表中選擇一個(gè)節(jié)點(diǎn) i,使其 g(i)為最小。如果有幾個(gè)節(jié)點(diǎn)都合格，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為 i(要是有目標(biāo)節(jié)點(diǎn)的話 )；否則，就從中選一個(gè)作為節(jié)點(diǎn) I。 REMOVE(i, OPEN), ADD(i, CLOSED)。4, IF GOAL(i) EXIT (SUCCESS)。5, EXPAND(i) →{j}, G=ADD(j, G)。6, 對(duì)每個(gè)后繼節(jié)點(diǎn) j,計(jì)算 g(j)=g(i)+c(i,j)且 ADD(OPEN, j), 并標(biāo)記 j到 i的指針 。7, GO LOOP。2/27/2023 17人工智能講義啟發(fā)式圖搜索? 利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。? 啟發(fā)信息的強(qiáng)度–強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解–弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解2/27/2023 18人工智能講義希望：? 引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。2/27/2023 19人工智能講義基本思想? 定義一個(gè)評(píng)價(jià)函數(shù) f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。2/27/2023 20人工智能講義1，啟發(fā)式搜索算法 A（ A算法）? 評(píng)價(jià)函數(shù)的格式：f(n) = g(n) + h(n)f(n)：評(píng)價(jià)函數(shù)h(n)：?jiǎn)l(fā)函數(shù)2/27/2023 21人工智能講義符號(hào)的意義? g*(n)：從 s到 n的最短路徑的耗散值? h*(n)：從 n到 g的最短路徑的耗散值? f*(n)=g*(n)+h*(n)： 從 s經(jīng)過(guò) n到 g的最短路徑的耗散值? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計(jì)值2/27/2023 22人工智能講義A算法1, OPEN=(s), f(s)=g(s)+h(s)。2, LOOP: IF OPEN=( ) EXIT(FAIL)。3, n=FIRST(OPEN)。4, IF GOAL(n) EXIT(SUCCESS)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。6, EXPAND(n) → {Mi}, 計(jì)算 f(n, mi)=g(n, mi)+h(mi)。 2/27/2023 23人工智能講義A算法（續(xù)）ADD(mj, OPEN), 標(biāo)記 mj到 n的指針；IF f(n, mk)f(mk) f(mk)=f(n, mk), 標(biāo)記 mk到 n的指針；IF f(n, ml)f(ml,) f(ml)=f(n, ml),標(biāo)記 ml到 n的指針 , ADD(ml, OPEN)。7, OPEN中的節(jié)點(diǎn)按 f值從小到大排序；8, GO LOOP；2/27/2023 24人工智能講義一個(gè) A算法的例子定義評(píng)價(jià)函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值h(n)為當(dāng)前節(jié)點(diǎn) “不在位 ”的將牌數(shù) 2 8 31 6 47 51 2 38 47 6 52/27/2023 25人工智能講義h計(jì)算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 82/27/2023 26人工智能講義2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6) B(4) C