西電人工智能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)空間的搜索策略與/或樹(shù)的搜索策略搜索的完備性與效率搜索策略搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

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

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

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

g(n)

≥

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

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

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

A*算法一定終止在最優(yōu)路徑上。假設(shè)最優(yōu)路徑存在，記為S0,x1,x2,...,xm,Sg*由于A*算法中的h(n)滿(mǎ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é)點(diǎn)，記x'為其中最前面一個(gè)，則f(x')≤f*(S0)。假設(shè)：A*算法不是終止在最優(yōu)路徑上，而是在某個(gè)目標(biāo)節(jié)點(diǎn)t處終止，則有f(t)=g(t)

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

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

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

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

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

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

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

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

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

123A4t15

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

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

(5)擴(kuò)展4號(hào)節(jié)點(diǎn)，生成t2節(jié)點(diǎn)和B節(jié)點(diǎn)。由于t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過(guò)程，可標(biāo)記2號(hào)節(jié)點(diǎn)為可解，再往上又可標(biāo)記1號(hào)節(jié)點(diǎn)為可解。(6)搜索成功，得到由1、3、5、2、4號(hào)節(jié)點(diǎn)即t1、t2、t3節(jié)點(diǎn)構(gòu)成的解樹(shù)。與/或樹(shù)的廣度優(yōu)先搜索深度優(yōu)先搜索過(guò)程：(6)搜索成功，得與/或樹(shù)的搜索策略與/或樹(shù)的搜索策略與/或樹(shù)的一般搜索過(guò)程與/或樹(shù)的廣度優(yōu)先搜索與/或樹(shù)的深度優(yōu)先搜索與/或樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹(shù)的搜索策略與/或樹(shù)的搜索策略問(wèn)題？問(wèn)題？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)空間的搜索策略與/或樹(shù)的搜索策略搜索的完備性與效率搜索策略搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價(jià)函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法。

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

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

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

g(n)

≥

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

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

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

A*算法一定終止在最優(yōu)路徑上。假設(shè)最優(yōu)路徑存在，記為S0,x1,x2,...,xm,Sg*由于A*算法中的h(n)滿(mǎ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é)點(diǎn)，記x'為其中最前面一個(gè)，則f(x')≤f*(S0)。假設(shè)：A*算法不是終止在最優(yōu)路徑上，而是在某個(gè)目標(biāo)節(jié)點(diǎn)t處終止，則有f(t)=g(t)

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

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

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

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

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

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