【正文】 (6)D(5) E(5) F(6)G(6) H(7)I(5) J(7)K(5)L(5) M(7)目標(biāo)123 456定義評(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/27/2023 27人工智能講義最佳圖搜索算法 A*（ A*算法）? 在 A算法中，如果滿足條件：h(n)≤h*(n)則 A算法稱為 A*算法。2/27/2023 28人工智能講義A*條件舉例? 8數(shù)碼問(wèn)題–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：對(duì)有限圖，如果從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則算法 A一定成功結(jié)束。2/27/2023 30人工智能講義A*算法的性質(zhì)（續(xù) 1）引理 ：對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t的路徑，則 A*不結(jié)束時(shí)，在 OPEN表中即使最小的一個(gè) f值也將增到任意大，或有f(n)f*(s)。2/27/2023 31人工智能講義A*算法的性質(zhì)（續(xù) 2）引理 ：A*結(jié)束前， OPEN表中必存在 f(n)≤f*(s)。2/27/2023 32人工智能講義A*算法的性質(zhì)（續(xù) 3）定理 2：對(duì)無(wú)限圖，若從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則 A*一定成功結(jié)束。2/27/2023 33人工智能講義A*算法的性質(zhì)（續(xù) 4）推論 ：OPEN表上任一具有 f(n)f*(s)的節(jié)點(diǎn) n，最終都將被 A*選作擴(kuò)展的節(jié)點(diǎn)。2/27/2023 34人工智能講義A*算法的性質(zhì)（續(xù) 5）定理 3 (可采納性定理 )：若存在從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑，則A*必能找到最佳解結(jié)束。2/27/2023 35人工智能講義A*算法的性質(zhì)（續(xù) 6）推論 ：A*選作擴(kuò)展的任一節(jié)點(diǎn) n，有 f(n)≤f*(s)。2/27/2023 36人工智能講義A*算法的性質(zhì)（續(xù) 7）定理 4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè) A*算法A1和 A2，若 A2比 A1有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)有 h2(n) h1(n)，則在具有一條從 s到 t的路徑的隱含圖上，搜索結(jié)束時(shí)，由 A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由 A1所擴(kuò)展，即 A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和 A2一樣多。簡(jiǎn)寫：如果 h2(n) h1(n), 則 A1擴(kuò)展的節(jié)點(diǎn)數(shù) ≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)2/27/2023 37人工智能講義A*算法的改進(jìn)? 問(wèn)題的提出：因 A算法第 6步對(duì) ml類節(jié)點(diǎn)可能要重新放回到 OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。2/27/2023 38人工智能講義s(10)A(1)B(5)C(8)G 目標(biāo)6311 18一個(gè)例子：OPEN表 CLOSED表s(10) s(10)A(7) B(8) C(9) A(7) s(10)B(8) C(9) G(14)A(5) C(9) G(14)C(9) G(12)B(7) G(12)A(4) G(12)G(11)A(7)B(8) s(10)A(5) B(8) s(10)C(9) A(5)B(8) s(10)A(5)B(7) C(9) s(10)A(4) B(7) C(9) s(10)2/27/2023 39人工智能講義出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因? 在前面的擴(kuò)展中，并沒(méi)有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn) A。2/27/2023 40人工智能講義解決的途徑? 對(duì) h加以限制–能否對(duì) h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從 s到該節(jié)點(diǎn)的最短路徑。? 對(duì)算法加以改進(jìn)–能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。2/27/2023 41人工智能講義改進(jìn)的條件? 可采納性不變? 不多擴(kuò)展節(jié)點(diǎn)? 不增加算法的復(fù)雜性2/27/2023 42人工智能講義對(duì) h加以限制? 定義：一個(gè)啟發(fā)函數(shù) h，如果對(duì)所有節(jié)點(diǎn)ni和 nj，其中 nj是 ni的子節(jié)點(diǎn)，滿足h(ni) h(nj) ≤ c(ni, nj)h(t) = 0則稱 h是單調(diào)的。 h(ni)ninjh(nj)c(ni,nj)2/27/2023 43人工智能講義h單調(diào)的性質(zhì)? 定理 5：若 h(n)是單調(diào)的，則 A*擴(kuò)展了節(jié)點(diǎn) n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn) n的最佳路徑。即：當(dāng) A*選 n擴(kuò)展時(shí)，有 g(n)=g*(n)。2/27/2023 44人工智能講義h單調(diào)的性質(zhì)（續(xù)）? 定理 6：若 h(n)是單調(diào)的，則由 A*所擴(kuò)展的節(jié)點(diǎn)序列其 f值是非遞減的。2/27/2023 45人工智能講義h單調(diào)的例子? 8數(shù)碼問(wèn)題：–h為 “不在位 ”的將牌數(shù) 1h(ni) h(nj) = 0 (nj為 ni的后繼節(jié)點(diǎn) ) 1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。 2/27/2023 46人工智能講義對(duì)算法加以改進(jìn)? 一些結(jié)論：–OPEN表上任一具有 f(n) f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。–A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有 f(n)≤f*(s)。2/27/2023 47人工智能講義改進(jìn)的出發(fā)點(diǎn)OPEN = ( … … … … )f*(s)f值小于 f*(s)的節(jié)點(diǎn) f值大于等于 f*(s)的節(jié)點(diǎn)fm： 到目前為止已擴(kuò)展節(jié)點(diǎn)的最大 f值， 用 fm代替 f*(s)2/27/2023 48人工智能講義修正過(guò)程 A1, OPEN=(s), f(s)=g(s)+h(s), fm=0。2, LOOP: IF OPEN=( ) EXIT(FAIL)。3, NEST={ni|f(ni)fm}IF NEST ≠ ( ) n=NEST中 g最小的節(jié)點(diǎn) ELSE n=FIRST(OPEN), fm=f(n)。4, …, 8: 同過(guò)程 A。2/27/2023 49人工智能講義s(10)A(1)B(5)C(8)G 目標(biāo)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人工智能講義例子： 傳教士與野人問(wèn)題 設(shè)有 3個(gè)傳教士和 3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡河過(guò)去？ 2/27/2023 51人工智能講義問(wèn)題表示 ：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。用三元式表示狀態(tài)： S= (m, c, b)其中， m表示左岸修道士人數(shù)， c表示左岸野人人數(shù)， b表示左岸船的數(shù)目。解 ：確定估價(jià)函數(shù)。 f(n) = g(n) ＋ h(n) = d(n) ＋ m ＋ c － 2b其中， d(n)為節(jié)點(diǎn)深度。 h(n)＜ h*(n)，滿足 A*算法的限制條件。2/27/2023 52人工智能講義(3,2,0) (3,1,0) (2,2,0)(3,3,1) h=4,f=4f(n)=d(n)+m+c2bhh=5,f=6 h=4,f=5 h=4,f=5(3,2,1) h=3,f=5(2,1,0) (3,0,0) h=3,f=6h=3,f=6(2,2,1) (3,1,1) h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問(wèn)題的 A*搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0) (1,1,0)2/27/2023 53人工智能講義 AO*算法? 搜索 與或圖 的 A*算法? 節(jié)點(diǎn)評(píng)價(jià)方法 A*算法中，對(duì)節(jié)點(diǎn) n的評(píng)價(jià)，實(shí)際上是對(duì) “初始節(jié)點(diǎn) 節(jié)點(diǎn) n目標(biāo)節(jié)點(diǎn) ”這一條路徑的評(píng)價(jià) AO*算法中，由于與節(jié)點(diǎn)的存在，解對(duì)應(yīng)的不是一條路徑，而是一個(gè)子圖，因此對(duì)節(jié)點(diǎn)的評(píng)價(jià)，實(shí)際是對(duì)局部解圖 的評(píng)價(jià) 2/27/2023 54人工智能講義 A (6) B C D(3) (4) (5)f(A) = min {(B)+(C)+2, (D)+1} G H E F(4) (4)(5) (7)(10)(9)(6)(11)與或圖節(jié)點(diǎn)擴(kuò)展與評(píng)價(jià)2/27/2023 55人工智能講義算法的兩個(gè)階段第一階段：自上而下的圖生成過(guò)程對(duì)于每一個(gè)已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)， 都對(duì)應(yīng)一個(gè)指針，指向該節(jié)點(diǎn)后繼節(jié)點(diǎn)中，代價(jià)值小的那條邊。圖生成過(guò)程，就是從初始節(jié)點(diǎn)出發(fā)，按照該指針向下搜索，一直到找到一個(gè)未擴(kuò)展的節(jié)點(diǎn)為止。然后擴(kuò)展該節(jié)點(diǎn)。第二階段：自下而上的代價(jià)值計(jì)算過(guò)程設(shè) n為最新被擴(kuò)展的節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn) n對(duì)應(yīng)的最小代價(jià)值，并標(biāo)記一個(gè)指針指向?qū)?yīng)最小代價(jià)的邊。對(duì)于 n的父節(jié)點(diǎn)，進(jìn)行同樣的計(jì)算。重復(fù)這一過(guò)程，直到初始節(jié)點(diǎn) s為止。這時(shí)，從 s出發(fā)，選擇那些指針?biāo)赶虻倪叺玫降木植繄D，為當(dāng)前代價(jià)值最小的局部圖。2/27/2023 56人工智能講義具體步驟Step1 建立一個(gè)僅由初始節(jié)點(diǎn) s構(gòu)成的搜索圖G，計(jì)算 h(s) Step2 在以下兩過(guò)程間循環(huán)，直到 s標(biāo)記為可解或不可解，或其代價(jià)值大于閾值： 選擇節(jié)點(diǎn)進(jìn)行擴(kuò)展 根據(jù)擴(kuò)展情況修改節(jié)點(diǎn)的可解性與代價(jià)值2/27/2023 57人工智能講義 選擇節(jié)點(diǎn)進(jìn)行擴(kuò)展： 1 根據(jù)指針找出待擴(kuò)展的局部解圖 G′。 2 選擇 G′中的一個(gè)非終節(jié)點(diǎn) n作為當(dāng)前節(jié)點(diǎn)。 3 擴(kuò)展節(jié)點(diǎn) n，如不能擴(kuò)展，則標(biāo)記為不可解，否則生成子節(jié)點(diǎn)集，如子節(jié)點(diǎn)為非終節(jié)點(diǎn)，計(jì)算其代價(jià)值，若為終節(jié)點(diǎn)，標(biāo)注其可解。將所有子節(jié)點(diǎn)添加到 G中。 4 建立含 n的單一節(jié)點(diǎn)集合 S ， S:＝ {n}2/27/2023 58人工智能講義 修改節(jié)點(diǎn)的可解性與代價(jià)值 重復(fù)以下步驟，直到 S為空：1 從 S中挑選一個(gè)子孫節(jié)點(diǎn)都不在 S中的節(jié)點(diǎn) m 2 計(jì)算始于 m的每條連接線的代價(jià)，取其中最小值為m對(duì)應(yīng)的代價(jià)，并在對(duì)應(yīng)于最小代價(jià)的連接線上加指針。 3 如果連接于最小代價(jià)連接線上的所有節(jié)點(diǎn)都可解，則標(biāo)注 m可解。 4 如果 m的可解性或代價(jià)值發(fā)生改變，則把 m的所有祖先節(jié)點(diǎn)添加到 S中。2/27/2023 59人工智能講義AO*算法舉例目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8 h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0連接線的代價(jià)=后繼節(jié)點(diǎn)個(gè)數(shù)2/27/2023 60人工智能講義n0n1 n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)紅色代價(jià) ： 4藍(lán)色 代價(jià) ： 32/27/2023 61人工智能講義n0n1n2n3n4n5n6n7n8n4(1)n5(1)紅色代價(jià) ： 4藍(lán)色 代價(jià) ： 6n1 (25)n2(4)n3(4)n0(3)n0(34)2/27/2023 62人工智能講義n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(12)2/27/2023 63人工智能講義n0n1n2n3n4n5n