【正文】 數(shù)， b表示左岸船的數(shù)目。2/27/2023 49人工智能講義s(10)A(1)B(5)C(8)G 目標6311 18前面的例子：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) 2/27/2023 50人工智能講義例子： 傳教士與野人問題 設有 3個傳教士和 3個野人來到河邊，打算乘一只船從右岸渡到左岸去。2/27/2023 47人工智能講義改進的出發(fā)點OPEN = ( … … … … )f*(s)f值小于 f*(s)的節(jié)點 f值大于等于 f*(s)的節(jié)點fm： 到目前為止已擴展節(jié)點的最大 f值， 用 fm代替 f*(s)2/27/2023 48人工智能講義修正過程 A1, OPEN=(s), f(s)=g(s)+h(s), fm=0。2/27/2023 44人工智能講義h單調(diào)的性質(zhì)（續(xù)）? 定理 6：若 h(n)是單調(diào)的，則由 A*所擴展的節(jié)點序列其 f值是非遞減的。? 對算法加以改進–能否對算法加以改進，避免或減少節(jié)點的多次擴展。2/27/2023 36人工智能講義A*算法的性質(zhì)（續(xù) 7）定理 4：設對同一個問題定義了兩個 A*算法A1和 A2，若 A2比 A1有較多的啟發(fā)信息，即對所有非目標節(jié)點有 h2(n) h1(n)，則在具有一條從 s到 t的路徑的隱含圖上，搜索結束時，由 A2所擴展的每一個節(jié)點，也必定由 A1所擴展，即 A1擴展的節(jié)點數(shù)至少和 A2一樣多。2/27/2023 32人工智能講義A*算法的性質(zhì)（續(xù) 3）定理 2：對無限圖，若從初始節(jié)點 s到目標節(jié)點 t有路徑存在，則 A*一定成功結束。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(6)D(5) E(5) F(6)G(6) H(7)I(5) J(7)K(5)L(5) M(7)目標123 456定義評價函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點到當前節(jié)點的耗散值h(n)為當前節(jié)點 “不在位 ”的將牌數(shù)2/27/2023 27人工智能講義最佳圖搜索算法 A*（ A*算法）? 在 A算法中，如果滿足條件：h(n)≤h*(n)則 A算法稱為 A*算法。4, IF GOAL(n) EXIT(SUCCESS)。2/27/2023 19人工智能講義基本思想? 定義一個評價函數(shù) f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。6, 對每個后繼節(jié)點 j,計算 g(j)=g(i)+c(i,j)且 ADD(OPEN, j), 并標記 j到 i的指針 。如果有幾個節(jié)點都合格，那么就要選擇一個目標節(jié)點作為 i(要是有目標節(jié)點的話 )；否則，就從中選一個作為節(jié)點 I。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)先搜索的性質(zhì)? 當問題有解時，一定能找到解? 當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解? 方法與問題無關，具有通用性? 效率較低? 屬于圖搜索方法2/27/2023 15人工智能講義等代價搜索? 寬度優(yōu)先搜索可被推廣用來解決尋找從起始節(jié)點到目標節(jié)點具有最小代價路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價搜索算法 。6, EXPAND(n) →{mi}, G=ADD(mi, G)。2, LOOP: IF OPEN=( ) EXIT (FAIL)。10, GO LOOP。6, IF DEPTH(n)≥Dm GO LOOP。2, LOOP: IF OPEN=( ) EXIT (FAIL)。5, IF GOAL(n) EXIT(SUCCESS)。2/27/2023 5人工智能講義一般的圖搜索算法（GRAPHSEARCH）1, G=G0 (G0=s), OPEN=(s)。? 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用 C(ni, nj)表示從ni到 nj的路徑的耗散值。2, CLOSED=( )。6, EXPAND(n)→{mi}, G=ADD(mi, G)。3, n=FIRST(OPEN)。7, EXPAND(n) →{mi}, G=ADD(mi, G)。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)先搜索的性質(zhì)? 一般不能保證找到最優(yōu)解? 當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制? 最壞情況時，搜索空間等同于窮舉? 與回溯法的差別：圖搜索? 是一個通用的與問題無關的方法2/27/2023 11人工智能講義寬度優(yōu)先搜索? 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。3, n=FIRST(OPEN)。7, IF 目標在 {mi}中 THEN EXIT(SUCCESS)。2/27/2023 16人工智能講義等代價搜索算法? 算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0。 REMOVE(i, OPEN), ADD(i, CLOSED)。7, GO LOOP。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)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。2/27/2023 28人工智能講義A*條件舉例? 8數(shù)碼問題–h(n) = “不在位 ”的將牌數(shù)–h(n) = 將牌 “不在位 ”的距離和2 8 31 6 47 51 2 3457 6 8將牌 1： 1將牌 2： 1將牌 6： 1將牌 8： 22/27/2023 29人工智能講義A*算法的性質(zhì)定理 1：對有限圖，如果從初始節(jié)點 s到目標節(jié)點 t有路徑存在，則算法 A一定成功結束。2/27/2023 33人工智能講義A*算法的性質(zhì)（續(xù) 4）推論 ：OPEN表上任一具有 f(n)f*(s)的節(jié)點 n，最終都將被 A*選作擴展的節(jié)點。簡寫：如果 h2(n) h1(n), 則 A1擴展的節(jié)點數(shù) ≥A2擴展的節(jié)點數(shù)2/27/2023 37人工智能講義A*算法的改進? 問題的提出：因 A算法第 6步對 ml類節(jié)點可能要重新放回到 OPEN表中，因此可能會導致多次重復擴展同一個節(jié)點，導致搜索效率下降。2/27/2023 41人工智能講義改進的條件? 可采納性不變? 不多擴展節(jié)點? 不增加算法的復雜性2/27/2023 42人工智能講義對 h加以限制? 定義：一個啟發(fā)函數(shù) h，如果對所有節(jié)點ni和 nj，其中 nj是 ni的子節(jié)點，滿足h(ni) h(nj) ≤ c(ni, nj)h(