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