1、Artificial Intelligence (AI)人工智能,第二章：知識表示與推理,內(nèi)容提要,第二章：知識表示與推理,1.推理的基本概念,2.搜索策略,3.自然演繹推理,4.消解演繹推理,5.基于規(guī)則的演繹推理,搜索策略,搜索策略 搜索的基本概念 狀態(tài)空間的搜索策略 與/或樹的搜索策略 搜索的完備性與效率,與/或樹的搜索策略,與/或樹的搜索策略 與/或樹的一般搜索過程 與/或樹的廣度優(yōu)先搜索 與/或樹的深度優(yōu)先搜索 與/或樹的啟發(fā)式搜索 博弈樹的啟發(fā)式搜索 -剪枝技術(shù),與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索 與/或樹的啟發(fā)式搜索過程實際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解

2、樹的過程。 算法的每一步都試圖找到一個最有希望成為最優(yōu)解樹的子樹。 最優(yōu)解樹是指代價最小的那棵解樹。 它涉及到解樹的代價與希望樹。,與/或樹的啟發(fā)式搜索,解樹的代價:解樹的代價可按如下規(guī)則計算 (1)若n為終止節(jié)點，則其代價h(n)=0； (2)若n為或節(jié)點，且子節(jié)點為n1, n2, ,nk，則n的代價為： 其中，c(n, ni)是節(jié)點n到其子節(jié)點ni的邊代價。 (3)若n為與節(jié)點，且子節(jié)點為n1, n2, ,nk，則n的代價可用和代價法或最大代價法。,與/或樹的啟發(fā)式搜索,解樹的代價:解樹的代價可按如下規(guī)則計算 若用和代價法，則其計算公式為： 若用最大代價法，則其計算公式為： (4)若n是端

3、節(jié)點，但又不是終止節(jié)點，則n不可擴展，其代價定義為h(n)=。 (5)根節(jié)點的代價即為解樹的代價。,與/或樹的啟發(fā)式搜索,解樹的代價: 設(shè)下圖是一棵與/或樹，它包括兩棵解樹 左邊的解樹由S0、A、t1、C及t2組成； 右邊的解樹由S0、B、t2、D及t4組成。 在此與或樹中，t1、t2、t3、t4為終止節(jié)點；E、F是端節(jié)點；邊上的數(shù)字是該邊的代價。 請計算解樹的代價。,與/或樹的啟發(fā)式搜索,解樹的代價: 解：先計算左邊的解樹 按和代價： h(S0)=2+4+6+2=14 按最大代價： h(S0)=(2+6)+2=10 再計算右邊的解樹 按和代價： h(S0)=1+5+3+2=11 按最大代價：

4、 h(S0)=(1+5)+2=8,與/或樹的啟發(fā)式搜索,希望樹：希望樹是指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。與/或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程，在該過程中，希望樹是不斷變化的。 希望樹的定義： (1) 初始節(jié)點S0在希望樹T中 (2) 如果節(jié)點n在希望樹中，則一定有： 如果n是具有子節(jié)點n1, n2, , nk的或節(jié)點，則具有 值的那個子節(jié)點ni也應(yīng)在T中。 如果n是與節(jié)點，則n的全部子節(jié)點都在希望樹T中。,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索過程 (1) 把初始節(jié)點S0放入OPEN表中； (2) 求出希望樹T，即根據(jù)當(dāng)前搜索樹中節(jié)點的代價h求出以S0為根的希

5、望樹T； (3) 依次在OPEN表中取出T的端節(jié)點放入CLOSED表，并記該節(jié)點為n；節(jié)點n有三種不同情況：n為終止節(jié)點，n不是終止節(jié)點，但可擴展，n不是終止節(jié)點，且不可擴展，對三種情況分別進(jìn)行步驟(4) (5) (6)的操作過程；,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索過程 (4)如果節(jié)點n為終止節(jié)點，則： 標(biāo)記節(jié)點n為可解節(jié)點； 在T上應(yīng)用可解標(biāo)記過程，對n的先輩節(jié)點中的所有可解解節(jié)點進(jìn)行標(biāo)記； 如果初始解節(jié)點S0能夠被標(biāo)記為可解節(jié)點，則T就是最優(yōu)解樹，成功退出； 否則，從OPEN表中刪去具有可解先輩的所有節(jié)點。 轉(zhuǎn)第(2)步。,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索過程 (5)

6、如果節(jié)點n不是終止節(jié)點，但可擴展，則： 擴展節(jié)點n，生成n的所有子節(jié)點； 把這些子節(jié)點都放入OPEN表中，并為每一個子節(jié)點設(shè)置指向父節(jié)點n的指針； 計算這些子節(jié)點及其先輩節(jié)點的h值； 轉(zhuǎn)第(2)步。,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索過程 (6) 如果節(jié)點n不是終止節(jié)點，且不可擴展，則： 標(biāo)記節(jié)點n為不可解節(jié)點； 在T上應(yīng)用不可解標(biāo)記過程，對n的先輩節(jié)點中的所有不可解解節(jié)點進(jìn)行標(biāo)記； 如果初始解節(jié)點S0能夠被標(biāo)記為不可解節(jié)點，則問題無解，失敗退出； 否則，從OPEN表中刪去具有不可解先輩的所有節(jié)點。 轉(zhuǎn)第(2)步。,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索： 設(shè)初始節(jié)點為S0，要求搜

7、索過程每次擴展節(jié)點時都同時擴展兩層，且按一層或節(jié)點、一層與節(jié)點的間隔方式進(jìn)行擴展。 S0經(jīng)過擴展后得到的與/或樹如右圖所示。其中，端節(jié)點B、C、E、F，下面的數(shù)字是用啟發(fā)函數(shù)估算出的h值；各個父節(jié)點到其子節(jié)點的代價為1。,h(B)=3，h(C)=3 h(E)=3，h(F)=2 按照和代價計算得到： h(A)=8，h(D)=7 h(S0)=8 此時S0的右子樹是希望樹,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索： 依次對當(dāng)前希望樹的端節(jié)點進(jìn)行擴展。對節(jié)點E擴展兩層后得到的與/或樹如右圖所示。節(jié)點S0、A、D、E、G、H旁邊的數(shù)字是按和代價法計算出來的節(jié)點代價。 此時，由右子樹求出的h(S0)=1

8、2，由左子樹求出的h(S0)=9。顯然，左子樹的代價小。因此，當(dāng)前的希望樹應(yīng)改為左子樹。,由子節(jié)點算出的值7代替原來的估計值3,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索： 對節(jié)點B進(jìn)行擴展，擴展兩層后得到的與/或樹如下圖所示。,2,由于節(jié)點N和O是可解節(jié)點，故調(diào)用可解標(biāo)記過程，得節(jié)點L、B也為可解節(jié)點，但不能標(biāo)記S0為可解節(jié)點，須繼續(xù)擴展。當(dāng)前的希望樹仍然是左子樹。,與/或樹的啟發(fā)式搜索,與/或樹的啟發(fā)式搜索： 對節(jié)點C進(jìn)行擴展，擴展兩層后得到的與/或樹如下圖所示。,調(diào)用可解標(biāo)記過程，可標(biāo)記S0為可解節(jié)點，這就得到了代價最小的解樹。按和代價法，該最優(yōu)解的代價為9。,搜索策略,搜索策略 搜索的

9、基本概念 狀態(tài)空間的搜索策略 與/或樹的搜索策略 搜索的完備性與效率,搜索的完備性與效率,完備性 對于一類可解的問題和一個搜索過程，如果運用該搜索過程一定能求得該類問題的解，則稱該搜索過程為完備的，否則為不完備的。 完備的搜索過程稱為“搜索算法”。不完備的搜索過程不是算法，稱為“過程”。 廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索、改進(jìn)后的有界深度優(yōu)先搜索以及A*算法都是完備的搜索過程，其它搜索過程都是不完備的。,搜索的完備性與效率,搜索效率 一個搜索過程的搜索效率不僅取決于過程自身的啟發(fā)能力，而且還與被解問題的有關(guān)屬性等多種因素有關(guān)。 為了比較求解同一問題的不同搜索方法的效率，常用以下兩種指標(biāo)來衡量

10、： 外顯率 有效分支因數(shù),搜索的完備性與效率,外顯率： 外顯率定義為： P=L/T L為從初始節(jié)點到目標(biāo)節(jié)點的路徑長度； T為整個搜索過程中所生成的節(jié)點總數(shù)。 外顯率反映了搜索過程中從初始節(jié)點向目標(biāo)節(jié)點前進(jìn)時搜索區(qū)域的寬度。當(dāng)T=L時，P=1，表示搜索過程中每次只生成一個節(jié)點，它恰好是解路徑上的節(jié)點，搜索效率最高。P越小表示搜索時產(chǎn)生的無用節(jié)點愈多，搜索效率愈低。,搜索的完備性與效率,有效分枝因數(shù)： 有效分枝因數(shù)B定義為： B+B2+BL=T B是有效分枝因數(shù)，它表示在整個搜索過程中每個節(jié)點平均生成的子節(jié)點數(shù)目； L為從初始節(jié)點到目標(biāo)節(jié)點的路徑長度； T為整個搜索過程中所生成的節(jié)點總數(shù)。 當(dāng)B1