【正文】 – 對子句集使用歸結(jié)推理規(guī)則– 歸結(jié)式作為新子句參加歸結(jié)– 歸結(jié)式為空子句 □ ， S是不可滿足的（矛盾），原命題成立。如子句： C1= C1′ ∨L, C 2 = C2′ ∨ 歸結(jié)式： R(C1, C2) = C1′ ∨ C2′（ “數(shù)學(xué)定理機器證明 ”）? 本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題 。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。– 與演繹法完全不同，新的邏輯演算算法。 4 如果 m的可解性或代價值發(fā)生改變，則把 m的所有祖先節(jié)點添加到 S中。 4 建立含 n的單一節(jié)點集合 S ， S:＝ {n}2/27/2023 58人工智能講義 修改節(jié)點的可解性與代價值 重復(fù)以下步驟，直到 S為空：1 從 S中挑選一個子孫節(jié)點都不在 S中的節(jié)點 m 2 計算始于 m的每條連接線的代價，取其中最小值為m對應(yīng)的代價，并在對應(yīng)于最小代價的連接線上加指針。 3 擴展節(jié)點 n，如不能擴展，則標記為不可解，否則生成子節(jié)點集，如子節(jié)點為非終節(jié)點，計算其代價值，若為終節(jié)點，標注其可解。2/27/2023 56人工智能講義具體步驟Step1 建立一個僅由初始節(jié)點 s構(gòu)成的搜索圖G，計算 h(s) Step2 在以下兩過程間循環(huán)，直到 s標記為可解或不可解，或其代價值大于閾值： 選擇節(jié)點進行擴展 根據(jù)擴展情況修改節(jié)點的可解性與代價值2/27/2023 57人工智能講義 選擇節(jié)點進行擴展： 1 根據(jù)指針找出待擴展的局部解圖 G′。重復(fù)這一過程，直到初始節(jié)點 s為止。第二階段：自下而上的代價值計算過程設(shè) n為最新被擴展的節(jié)點，計算節(jié)點 n對應(yīng)的最小代價值，并標記一個指針指向?qū)?yīng)最小代價的邊。圖生成過程，就是從初始節(jié)點出發(fā)，按照該指針向下搜索，一直到找到一個未擴展的節(jié)點為止。 h(n)＜ h*(n)，滿足 A*算法的限制條件。解 ：確定估價函數(shù)。他們怎樣才能用這條船安全地把所有人都渡河過去？ 2/27/2023 51人工智能講義問題表示 ：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。該船的負載能力為兩人。4, …, 8: 同過程 A。2, LOOP: IF OPEN=( ) EXIT(FAIL)。–A*選作擴展的任一節(jié)點，定有 f(n)≤f*(s)。2/27/2023 45人工智能講義h單調(diào)的例子? 8數(shù)碼問題：–h為 “不在位 ”的將牌數(shù) 1h(ni) h(nj) = 0 (nj為 ni的后繼節(jié)點 ) 1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。即：當 A*選 n擴展時，有 g(n)=g*(n)。2/27/2023 41人工智能講義改進的條件? 可采納性不變? 不多擴展節(jié)點? 不增加算法的復(fù)雜性2/27/2023 42人工智能講義對 h加以限制? 定義：一個啟發(fā)函數(shù) h，如果對所有節(jié)點ni和 nj，其中 nj是 ni的子節(jié)點，滿足h(ni) h(nj) ≤ c(ni, nj)h(t) = 0則稱 h是單調(diào)的。2/27/2023 40人工智能講義解決的途徑? 對 h加以限制–能否對 h增加適當?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從 s到該節(jié)點的最短路徑。簡寫：如果 h2(n) h1(n), 則 A1擴展的節(jié)點數(shù) ≥A2擴展的節(jié)點數(shù)2/27/2023 37人工智能講義A*算法的改進? 問題的提出：因 A算法第 6步對 ml類節(jié)點可能要重新放回到 OPEN表中，因此可能會導(dǎo)致多次重復(fù)擴展同一個節(jié)點，導(dǎo)致搜索效率下降。2/27/2023 35人工智能講義A*算法的性質(zhì)（續(xù) 6）推論 ：A*選作擴展的任一節(jié)點 n，有 f(n)≤f*(s)。2/27/2023 33人工智能講義A*算法的性質(zhì)（續(xù) 4）推論 ：OPEN表上任一具有 f(n)f*(s)的節(jié)點 n，最終都將被 A*選作擴展的節(jié)點。2/27/2023 31人工智能講義A*算法的性質(zhì)（續(xù) 2）引理 ：A*結(jié)束前， OPEN表中必存在 f(n)≤f*(s)。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一定成功結(jié)束。 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)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。3, n=FIRST(OPEN)。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)。? 啟發(fā)信息的強度–強：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解–弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解2/27/2023 18人工智能講義希望：? 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。7, GO LOOP。5, EXPAND(i) →{j}, G=ADD(j, G)。 REMOVE(i, OPEN), ADD(i, CLOSED)。3, 從 OPEN表中選擇一個節(jié)點 i,使其 g(i)為最小。2/27/2023 16人工智能講義等代價搜索算法? 算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0。9, GO LOOP。7, IF 目標在 {mi}中 THEN EXIT(SUCCESS)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。3, n=FIRST(OPEN)。 “先產(chǎn)生的節(jié)點先擴展 ”2/27/2023 12人工智能講義寬度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( )。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)解? 當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制? 最壞情況時，搜索空間等同于窮舉? 與回溯法的差別：圖搜索? 是一個通用的與問題無關(guān)的方法2/27/2023 11人工智能講義寬度優(yōu)先搜索? 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。9, ADD(mj, OPEN), 并標記 mj到 n的指針 。7, EXPAND(n) →{mi}, G=ADD(mi, G)。5, REMOVE(n, OPEN), ADD(n, CLOSED)。3, n=FIRST(OPEN)。 “最晚產(chǎn)生的節(jié)點最先擴展 ”2/27/2023 8人工智能講義深度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( )。6, EXPAND(n)→{mi}, G=ADD(mi, G)。4, n=FIRST(OPEN), REMOVE(n, OPEN),ADD(n, CLOSED)。2, CLOSED=( )。這一過程稱為 “擴展一個節(jié)點 ”。用 C(ni, nj)表示從ni到 nj的路徑的耗散值。第三章 一般搜索原理? 盲目搜索? 啟發(fā)式搜索? 歸結(jié)原理2/27/2023 1人工智能講義盲目搜索? 圖搜索策略? 深度優(yōu)先搜索? 寬度優(yōu)先搜索? 等代價搜索2/27/2023 2人工智能講義一些基本概念? 節(jié)點深度：根節(jié)點深度 =0其它節(jié)點深度 =父節(jié)點深度 +101232/27/2023 3人工智能講義一些基本概念（續(xù) 1）? 路徑設(shè)一節(jié)點序列為 (n0, n1,…,n k)，對于i=1,…,k ，若節(jié)點 ni1具有一個后繼節(jié)點 ni，則該序列稱為從 n0到 nk的路徑。? 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。2/27/2023 4人工智能講義一些基本概念（續(xù) 1）? 擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。2/27/2023 5人工智能講義一般的圖搜索算法（GRAPHSEARCH）1, G=G0 (G0=s), OPEN=(s)。3, LOOP: IF OPEN=( ) EXIT(FAIL)。5, IF GOAL(n) EXIT(SUCCESS)。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é)點可以任意排列。2, LOOP: IF OPEN=( ) EXIT (FAIL)。4, IF GOAL(n) EXIT (SUCCESS)。6, IF DEPTH(n)≥Dm GO LOOP。8, IF 目標在 {mi}中 THEN EXIT(SUCCESS)。10, GO LOO