西電人工智能10-確定性推理-part3課件

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理ArtificialIntelligence(AI)

人內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索策略搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對OPEN表中的節(jié)點進(jìn)行排序，則該搜索算法為A算法。

由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。A算法的類型：可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法：

從OPEN表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進(jìn)行擴(kuò)展。局部擇優(yōu)搜索算法：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進(jìn)行擴(kuò)展。A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價A算法全局擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步。(6)擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第2步。A算法全局擇優(yōu)搜索算法流程A算法局部擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步。(6)擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。A算法局部擇優(yōu)搜索算法流程A*算法A*算法：A*算法是對A算法的估價函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法。假設(shè)f*(n)是從初始節(jié)點出發(fā)經(jīng)過節(jié)點n達(dá)到目標(biāo)節(jié)點的最小代價，估價函數(shù)f(n)是對f*(n)的估計值。且

f*(n)=g*(n)+h*(n)g*(n)是從初始節(jié)點S0到節(jié)點n的最小代價。h*(n)是從節(jié)點n到目標(biāo)節(jié)點的最小代價，若有多個目標(biāo)節(jié)點，則為其中最小的一個。A*算法A*算法：A*算法是對A算法的估價函數(shù)f(n)=g(A*算法A*算法：A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g(n)和h(n)分別提出如下限制：第一，g(n)是對最小代價g*(n)的估計，且g(n)>0；第二，h(n)是最小代價h*(n)的下界，即對任意節(jié)點n均有h(n)≤h*(n)。即：滿足上述兩條限制的A算法稱為A*算法。A*算法A*算法：A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法A*算法在A*算法中，g(n)比較容易得到，它實際上就是從初始節(jié)點S0到節(jié)點n的路徑代價，恒有：

g(n)

≥

g*(n)在算法執(zhí)行過程中，隨著更多搜索信息的獲得，g(n)呈下降的趨勢。如右圖的例子：對S0擴(kuò)展后g(n1)=3，g(n2)=7對n1擴(kuò)展后g(n2)=6，g(n3)=5S0n137n2n332A*算法在A*算法中，g(n)比較容易得到，它實際上就是從A*算法A*算法的可納性：可納性的含義：對任一狀態(tài)空間圖，當(dāng)從初始節(jié)點到目標(biāo)節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可納的。A*算法是可納的，即它能在有限步內(nèi)終止，并找到問題的最優(yōu)解。證明：……A*算法A*算法的可納性：A*算法A*算法的可納性證明：

第一步：對于有限圖，A*算法一定會在有限步驟內(nèi)終止。第二步：對于無限圖，如果從初始節(jié)點S0到目標(biāo)節(jié)點Sg有路徑存在，則A*算法也必然會終止。第三步：

A*算法一定終止在最優(yōu)路徑上。A*算法A*算法的可納性證明：A*算法證明：

A*算法一定終止在最優(yōu)路徑上。假設(shè)最優(yōu)路徑存在，記為S0,x1,x2,...,xm,Sg*由于A*算法中的h(n)滿足h(n)≤h*(n)，則：f(S0),f(x1),f(x2),...,f(xm)均不大于,f(Sg*)，f(Sg*)=f*(S0)在A*算法結(jié)束之前，OPEN表中必然存在最優(yōu)路徑S0,x1,x2,...,xm,Sg*中的一些節(jié)點，記x'為其中最前面一個，則f(x')≤f*(S0)。假設(shè)：A*算法不是終止在最優(yōu)路徑上，而是在某個目標(biāo)節(jié)點t處終止，則有f(t)=g(t)

>f*(S0)。此時有f(x')<f(t)，按照A*算法的規(guī)則，應(yīng)該選擇x'進(jìn)行擴(kuò)展，而不會選擇t。與假設(shè)矛盾A*算法證明：A*算法一定終止在最優(yōu)路徑上。A*算法A*算法的最優(yōu)性：h(n)的確定依賴于具體問題領(lǐng)域的啟發(fā)性信息，其中h(n)≤h*(n)的限制是十分重要的，它可以保證A*算法能找到問題的最優(yōu)解。A*算法的搜索效率很大程度上取決于估價函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴(kuò)展的節(jié)點就越少，搜索效率就越高。A*算法A*算法的最優(yōu)性：A*算法h(n)的單調(diào)限制在A*算法中，每當(dāng)擴(kuò)展一個節(jié)點n時，都需要檢查其子節(jié)點是否已在OPEN表或CLOSED表中。對已在OPEN表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針；對已在CLOSED表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。如果能夠保證，每當(dāng)擴(kuò)展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，就沒有必要再去作上述檢查。A*算法h(n)的單調(diào)限制A*算法h(n)的單調(diào)限制為能夠保證，每當(dāng)擴(kuò)展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，我們需要對啟發(fā)函數(shù)h(n)增加單調(diào)性限制。如果啟發(fā)函數(shù)滿足以下兩個條件:(1)h(Sg)=0;(2)對任意節(jié)點ni及其任一子節(jié)點nj，都有0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調(diào)限制。A*算法h(n)的單調(diào)限制A*算法如果h(n)滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：設(shè)A*正要擴(kuò)展節(jié)點n，而節(jié)點序列S0=n0,n1,…,nk=n是由初始節(jié)點S0到節(jié)點n的最佳路徑。其中，ni是這個序列中最后一個位于CLOSED表中的節(jié)點，則上述節(jié)點序列中的ni+1節(jié)點必定在OPEN表中，由h(n)的單調(diào)條件可知：g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)所以：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)依此類推可得：g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)=g*(n)+h(n)由于節(jié)點ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因為這時A*擴(kuò)展節(jié)點n而不擴(kuò)展節(jié)點ni+1，則有：

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)

即g(n)≤g*(n)。g*(n)是最小代價值，所以有g(shù)(n)=g*(n)最佳路徑上的節(jié)點A*算法如果h(n)滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點n時，A*算法如果h(n)滿足單調(diào)限制，則A*算法擴(kuò)展的節(jié)點序列的f值是非遞減的，即f(ni)≤f(ni+1)。證明：假設(shè)節(jié)點ni+1在節(jié)點ni之后立即擴(kuò)展，由單調(diào)限制條件可知：h(ni)-h(ni+1)≤c(ni,ni+1)即：(f(ni)-g(ni))-(f(ni+1)-g(ni+1))≤c(ni,ni+1)亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以：f(ni)-f(ni+1)≤0即：f(ni)≤f(ni+1)以上兩個定理都是在h(n)滿足單調(diào)性限制的前提下才成立的。如果h(n)不滿足單調(diào)性限制，則它們不一定成立。A*算法如果h(n)滿足單調(diào)限制，則A*算法擴(kuò)展的節(jié)點序列的A*算法A*算法應(yīng)用：八數(shù)碼難題f(n)=g(n)+h(n)g(n)深度h(n)與目標(biāo)距離f*=g*+h*f(n)=g(n)+h(n)g(n)深度h(n)與目標(biāo)距離f*=g*+h*A*算法A*算法應(yīng)用：f(n)=g(n)+h(n)搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索策略搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的搜索策略：用與/或樹方法求解問題時，首先要定義問題的描述方法，及分解或變換問題的算符，然后就用它們通過搜索生成與/或樹，從而求得原始問題的解。在與/或樹中，一個節(jié)點是否為可解節(jié)點是由它的子節(jié)點確定的。由可解/不可解子節(jié)點來確定父節(jié)點、祖父節(jié)點等為可解/不可解節(jié)點的過程成為可解/不可解標(biāo)記過程。與/或樹的搜索過程是反復(fù)調(diào)用可解/不可解標(biāo)記過程，直到初始節(jié)點（原始問題）被標(biāo)記為可解/不可解節(jié)點為止。與/或樹的一般搜索過程與/或樹的搜索策略：與/或樹的一般搜索過程與/或樹的一般搜索過程如下：(1)把原始問題作為初始節(jié)點S0，并把它作為當(dāng)前節(jié)點；(2)應(yīng)用分解或等價變換操作對當(dāng)前節(jié)點進(jìn)行擴(kuò)展；(3)為每個子節(jié)點設(shè)置指向父節(jié)點的指針；(4)選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第(2)步和第(3)步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點被標(biāo)記為可解節(jié)點或不可解節(jié)點為止。上述搜索過程將形成一棵與/或樹，這種由搜索過程所形成的與/或樹稱為搜索樹。與/或樹的一般搜索過程與/或樹的一般搜索過程如下：與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索：與/或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標(biāo)識過程或不可解標(biāo)識過程。與/或樹的廣度優(yōu)先搜索算法如下：(1)把初始節(jié)點S0放入OPEN表中；(2)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(3)如果節(jié)點n可擴(kuò)展，則做下列工作：與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索：與/或樹的廣度優(yōu)先搜索①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針；②考察這些子節(jié)點中有否終止節(jié)點。若有，則標(biāo)記這些終止節(jié)點為可解節(jié)點，并用可解標(biāo)記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0能夠被標(biāo)記為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。與/或樹的廣度優(yōu)先搜索①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN與/或樹的廣度優(yōu)先搜索

(4)如果節(jié)點n不可擴(kuò)展，則作下列工作：

①標(biāo)記節(jié)點n為不可解節(jié)點；②應(yīng)用不可解標(biāo)記過程對節(jié)點n的先輩中不可解解的節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0也被標(biāo)記為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從Open表中刪去具有不可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。與/或樹的廣度優(yōu)先搜索(4)如果節(jié)點n不可擴(kuò)展，則作下列與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索的例子:設(shè)有下圖所示的與/或樹，節(jié)點按標(biāo)注順序進(jìn)行擴(kuò)展，其中表有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。123A4t15

t2Bt3C與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索的例子:12與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(1)先擴(kuò)展1號節(jié)點，生成2號節(jié)點和3號節(jié)點。(2)擴(kuò)展2號節(jié)點，生成A節(jié)點和4號節(jié)點。(3)擴(kuò)展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定3號節(jié)點是否可節(jié)。(4)擴(kuò)展節(jié)點A，由于A是端節(jié)點，因此不可擴(kuò)展。調(diào)用不可解標(biāo)記過程。與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(3)擴(kuò)展3號節(jié)點與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(5)擴(kuò)展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，標(biāo)記為可解節(jié)點，應(yīng)用可解標(biāo)記過程，可標(biāo)記2號節(jié)點為可解，但不能標(biāo)記1號節(jié)點為可解。(6)擴(kuò)展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，標(biāo)記它為可解節(jié)點，應(yīng)用可解標(biāo)記過程，可標(biāo)記1號節(jié)點為可解節(jié)點。(7)搜索成功，得到由1、2、3、4、5號節(jié)點和t1、t2、t3節(jié)點構(gòu)成的解樹。與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(6)擴(kuò)展5號節(jié)點與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索：與/或樹的深度優(yōu)先搜索和與/或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于OPEN表中節(jié)點的排列順序不同。在擴(kuò)展節(jié)點時，與/或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點放在OPEN表的首部。與/或樹的深度優(yōu)先搜索也可以帶有深度限制dm與/或樹的深度優(yōu)先搜索算法如下：(1)把初始節(jié)點S0放入OPEN表中；(2)把OPEN表第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；

與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索：與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索算法如下：(3)如果節(jié)點n的深度等于dm，則轉(zhuǎn)第(5)步的第①點；(4)如果節(jié)點n可擴(kuò)展，則做下列工作：

①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針；②考察這些子節(jié)點中是否有終止節(jié)點。若有，則標(biāo)記這些終止節(jié)點為可解節(jié)點，并用可解標(biāo)記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0能夠被標(biāo)記為可解節(jié)點，就得到了解樹，搜索成功；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索算法如下：與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索算法如下：③轉(zhuǎn)第(2)步。(5)如果節(jié)點n不可擴(kuò)展，則作下列工作：①標(biāo)記節(jié)點n為不可解節(jié)點；②應(yīng)用不可解標(biāo)記過程對節(jié)點n的先輩中不可解解的節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0也被標(biāo)記為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從Open表中刪去具有不可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。

與/或樹的深度優(yōu)先搜索與/或樹的深度優(yōu)先搜索算法如下：與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索的例子:設(shè)有下圖所示的與/或樹，其中表有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。若按有界深度優(yōu)先搜索，設(shè)dm=4，則其節(jié)點擴(kuò)展順序為：1，3，5，2，4。

123A4t15

t2Bt3C與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索的例子:12與/或樹的廣度優(yōu)先搜索深度優(yōu)先搜索過程：(1)先擴(kuò)展1號節(jié)點，生成2號節(jié)點和3號節(jié)點。(2)擴(kuò)展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定3號節(jié)點是否可解。

(3)擴(kuò)展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記3號節(jié)點為可解節(jié)點，但不能標(biāo)記1號為可解。與/或樹的廣度優(yōu)先搜索深度優(yōu)先搜索過程：(3)擴(kuò)展5號節(jié)點，與/或樹的廣度優(yōu)先搜索深度優(yōu)先搜索過程：(4)擴(kuò)展2號節(jié)點，生成A節(jié)點和4號節(jié)點。

(5)擴(kuò)展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記2號節(jié)點為可解，再往上又可標(biāo)記1號節(jié)點為可解。(6)搜索成功，得到由1、3、5、2、4號節(jié)點即t1、t2、t3節(jié)點構(gòu)成的解樹。與/或樹的廣度優(yōu)先搜索深度優(yōu)先搜索過程：(6)搜索成功，得與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略問題？問題？ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理ArtificialIntelligence(AI)

人內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索策略搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對OPEN表中的節(jié)點進(jìn)行排序，則該搜索算法為A算法。

由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。A算法的類型：可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法：

從OPEN表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進(jìn)行擴(kuò)展。局部擇優(yōu)搜索算法：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進(jìn)行擴(kuò)展。A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價A算法全局擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步。(6)擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第2步。A算法全局擇優(yōu)搜索算法流程A算法局部擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第2步。(6)擴(kuò)展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。A算法局部擇優(yōu)搜索算法流程A*算法A*算法：A*算法是對A算法的估價函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法。假設(shè)f*(n)是從初始節(jié)點出發(fā)經(jīng)過節(jié)點n達(dá)到目標(biāo)節(jié)點的最小代價，估價函數(shù)f(n)是對f*(n)的估計值。且

f*(n)=g*(n)+h*(n)g*(n)是從初始節(jié)點S0到節(jié)點n的最小代價。h*(n)是從節(jié)點n到目標(biāo)節(jié)點的最小代價，若有多個目標(biāo)節(jié)點，則為其中最小的一個。A*算法A*算法：A*算法是對A算法的估價函數(shù)f(n)=g(A*算法A*算法：A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g(n)和h(n)分別提出如下限制：第一，g(n)是對最小代價g*(n)的估計，且g(n)>0；第二，h(n)是最小代價h*(n)的下界，即對任意節(jié)點n均有h(n)≤h*(n)。即：滿足上述兩條限制的A算法稱為A*算法。A*算法A*算法：A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法A*算法在A*算法中，g(n)比較容易得到，它實際上就是從初始節(jié)點S0到節(jié)點n的路徑代價，恒有：

g(n)

≥

g*(n)在算法執(zhí)行過程中，隨著更多搜索信息的獲得，g(n)呈下降的趨勢。如右圖的例子：對S0擴(kuò)展后g(n1)=3，g(n2)=7對n1擴(kuò)展后g(n2)=6，g(n3)=5S0n137n2n332A*算法在A*算法中，g(n)比較容易得到，它實際上就是從A*算法A*算法的可納性：可納性的含義：對任一狀態(tài)空間圖，當(dāng)從初始節(jié)點到目標(biāo)節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標(biāo)節(jié)點的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可納的。A*算法是可納的，即它能在有限步內(nèi)終止，并找到問題的最優(yōu)解。證明：……A*算法A*算法的可納性：A*算法A*算法的可納性證明：

第一步：對于有限圖，A*算法一定會在有限步驟內(nèi)終止。第二步：對于無限圖，如果從初始節(jié)點S0到目標(biāo)節(jié)點Sg有路徑存在，則A*算法也必然會終止。第三步：

A*算法一定終止在最優(yōu)路徑上。A*算法A*算法的可納性證明：A*算法證明：

A*算法一定終止在最優(yōu)路徑上。假設(shè)最優(yōu)路徑存在，記為S0,x1,x2,...,xm,Sg*由于A*算法中的h(n)滿足h(n)≤h*(n)，則：f(S0),f(x1),f(x2),...,f(xm)均不大于,f(Sg*)，f(Sg*)=f*(S0)在A*算法結(jié)束之前，OPEN表中必然存在最優(yōu)路徑S0,x1,x2,...,xm,Sg*中的一些節(jié)點，記x'為其中最前面一個，則f(x')≤f*(S0)。假設(shè)：A*算法不是終止在最優(yōu)路徑上，而是在某個目標(biāo)節(jié)點t處終止，則有f(t)=g(t)

>f*(S0)。此時有f(x')<f(t)，按照A*算法的規(guī)則，應(yīng)該選擇x'進(jìn)行擴(kuò)展，而不會選擇t。與假設(shè)矛盾A*算法證明：A*算法一定終止在最優(yōu)路徑上。A*算法A*算法的最優(yōu)性：h(n)的確定依賴于具體問題領(lǐng)域的啟發(fā)性信息，其中h(n)≤h*(n)的限制是十分重要的，它可以保證A*算法能找到問題的最優(yōu)解。A*算法的搜索效率很大程度上取決于估價函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴(kuò)展的節(jié)點就越少，搜索效率就越高。A*算法A*算法的最優(yōu)性：A*算法h(n)的單調(diào)限制在A*算法中，每當(dāng)擴(kuò)展一個節(jié)點n時，都需要檢查其子節(jié)點是否已在OPEN表或CLOSED表中。對已在OPEN表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針；對已在CLOSED表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。如果能夠保證，每當(dāng)擴(kuò)展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，就沒有必要再去作上述檢查。A*算法h(n)的單調(diào)限制A*算法h(n)的單調(diào)限制為能夠保證，每當(dāng)擴(kuò)展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，我們需要對啟發(fā)函數(shù)h(n)增加單調(diào)性限制。如果啟發(fā)函數(shù)滿足以下兩個條件:(1)h(Sg)=0;(2)對任意節(jié)點ni及其任一子節(jié)點nj，都有0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調(diào)限制。A*算法h(n)的單調(diào)限制A*算法如果h(n)滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：設(shè)A*正要擴(kuò)展節(jié)點n，而節(jié)點序列S0=n0,n1,…,nk=n是由初始節(jié)點S0到節(jié)點n的最佳路徑。其中，ni是這個序列中最后一個位于CLOSED表中的節(jié)點，則上述節(jié)點序列中的ni+1節(jié)點必定在OPEN表中，由h(n)的單調(diào)條件可知：g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)所以：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)依此類推可得：g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)=g*(n)+h(n)由于節(jié)點ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因為這時A*擴(kuò)展節(jié)點n而不擴(kuò)展節(jié)點ni+1，則有：

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)

即g(n)≤g*(n)。g*(n)是最小代價值，所以有g(shù)(n)=g*(n)最佳路徑上的節(jié)點A*算法如果h(n)滿足單調(diào)條件，則當(dāng)A*算法擴(kuò)展節(jié)點n時，A*算法如果h(n)滿足單調(diào)限制，則A*算法擴(kuò)展的節(jié)點序列的f值是非遞減的，即f(ni)≤f(ni+1)。證明：假設(shè)節(jié)點ni+1在節(jié)點ni之后立即擴(kuò)展，由單調(diào)限制條件可知：h(ni)-h(ni+1)≤c(ni,ni+1)即：(f(ni)-g(ni))-(f(ni+1)-g(ni+1))≤c(ni,ni+1)亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以：f(ni)-f(ni+1)≤0即：f(ni)≤f(ni+1)以上兩個定理都是在h(n)滿足單調(diào)性限制的前提下才成立的。如果h(n)不滿足單調(diào)性限制，則它們不一定成立。A*算法如果h(n)滿足單調(diào)限制，則A*算法擴(kuò)展的節(jié)點序列的A*算法A*算法應(yīng)用：八數(shù)碼難題f(n)=g(n)+h(n)g(n)深度h(n)與目標(biāo)距離f*=g*+h*f(n)=g(n)+h(n)g(n)深度h(n)與目標(biāo)距離f*=g*+h*A*算法A*算法應(yīng)用：f(n)=g(n)+h(n)搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索策略搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的搜索策略：用與/或樹方法求解問題時，首先要定義問題的描述方法，及分解或變換問題的算符，然后就用它們通過搜索生成與/或樹，從而求得原始問題的解。在與/或樹中，一個節(jié)點是否為可解節(jié)點是由它的子節(jié)點確定的。由可解/不可解子節(jié)點來確定父節(jié)點、祖父節(jié)點等為可解/不可解節(jié)點的過程成為可解/不可解標(biāo)記過程。與/或樹的搜索過程是反復(fù)調(diào)用可解/不可解標(biāo)記過程，直到初始節(jié)點（原始問題）被標(biāo)記為可解/不可解節(jié)點為止。與/或樹的一般搜索過程與/或樹的搜索策略：與/或樹的一般搜索過程與/或樹的一般搜索過程如下：(1)把原始問題作為初始節(jié)點S0，并把它作為當(dāng)前節(jié)點；(2)應(yīng)用分解或等價變換操作對當(dāng)前節(jié)點進(jìn)行擴(kuò)展；(3)為每個子節(jié)點設(shè)置指向父節(jié)點的指針；(4)選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第(2)步和第(3)步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點被標(biāo)記為可解節(jié)點或不可解節(jié)點為止。上述搜索過程將形成一棵與/或樹，這種由搜索過程所形成的與/或樹稱為搜索樹。與/或樹的一般搜索過程與/或樹的一般搜索過程如下：與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的搜索策略與/或樹的搜索策略與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索：與/或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標(biāo)識過程或不可解標(biāo)識過程。與/或樹的廣度優(yōu)先搜索算法如下：(1)把初始節(jié)點S0放入OPEN表中；(2)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(3)如果節(jié)點n可擴(kuò)展，則做下列工作：與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索：與/或樹的廣度優(yōu)先搜索①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針；②考察這些子節(jié)點中有否終止節(jié)點。若有，則標(biāo)記這些終止節(jié)點為可解節(jié)點，并用可解標(biāo)記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0能夠被標(biāo)記為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。與/或樹的廣度優(yōu)先搜索①擴(kuò)展節(jié)點n，將其子節(jié)點放入OPEN與/或樹的廣度優(yōu)先搜索

(4)如果節(jié)點n不可擴(kuò)展，則作下列工作：

①標(biāo)記節(jié)點n為不可解節(jié)點；②應(yīng)用不可解標(biāo)記過程對節(jié)點n的先輩中不可解解的節(jié)點進(jìn)行標(biāo)記。如果初始解節(jié)點S0也被標(biāo)記為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從Open表中刪去具有不可解先輩的節(jié)點。③轉(zhuǎn)第(2)步。與/或樹的廣度優(yōu)先搜索(4)如果節(jié)點n不可擴(kuò)展，則作下列與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索的例子:設(shè)有下圖所示的與/或樹，節(jié)點按標(biāo)注順序進(jìn)行擴(kuò)展，其中表有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。123A4t15

t2Bt3C與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索的例子:12與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(1)先擴(kuò)展1號節(jié)點，生成2號節(jié)點和3號節(jié)點。(2)擴(kuò)展2號節(jié)點，生成A節(jié)點和4號節(jié)點。(3)擴(kuò)展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定3號節(jié)點是否可節(jié)。(4)擴(kuò)展節(jié)點A，由于A是端節(jié)點，因此不可擴(kuò)展。調(diào)用不可解標(biāo)記過程。與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(3)擴(kuò)展3號節(jié)點與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(5)擴(kuò)展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，標(biāo)記為可解節(jié)點，應(yīng)用可解標(biāo)記過程，可標(biāo)記2號節(jié)點為可解，但不能標(biāo)記1號節(jié)點為可解。(6)擴(kuò)展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，標(biāo)記它為可解節(jié)點，應(yīng)用可解標(biāo)記過程，可標(biāo)記1號節(jié)點為可解節(jié)點。(7)搜索成功，得到由1、2、3、4、5號節(jié)點和t1、t2、t3節(jié)點構(gòu)成的解樹。與/或樹的廣度優(yōu)先搜索廣度優(yōu)先搜索過程：(6)擴(kuò)展5號節(jié)點與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的