ArtificialIntelligence(AI)

人工智能第二章：知識表示與推理ArtificialIntelligence(AI)

人內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略3.自然演繹推理4.消解演繹推理5.基于規(guī)則的演繹推理二、確定性推理內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略搜索策略搜索策略搜索的基本概念狀態(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)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定OPEN表：未擴展節(jié)點表，用于存放剛生成節(jié)點CLOSED表：已擴展節(jié)點表，用于存放已經(jīng)擴展或?qū)⒁獢U展的節(jié)點S：用表示問題的初始狀態(tài)G：表示搜索過程所得到的搜索圖M：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集狀態(tài)空間的搜索策略狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定狀態(tài)空間的搜索策略圖搜索的一般過程(1)把初始節(jié)點S放入未擴展節(jié)點表OPEN表，并建立目前僅包含S的圖G；(2)檢查OPEN表是否為空，若為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入已擴展節(jié)點表CLOSED表，并記該節(jié)點為節(jié)點n；(4)考察節(jié)點n是否為目標節(jié)點。若是則得到了問題的解，成功退出。此時的解為追蹤圖G中沿著指針（步驟6中設(shè)置的指針）從n到初始節(jié)點S的路徑。狀態(tài)空間的搜索策略圖搜索的一般過程狀態(tài)空間的搜索策略圖搜索的一般過程(5)擴展節(jié)點n，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n先輩的那部分子節(jié)點記入集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中(6)針對M中子節(jié)點的不同情況，分別作如下處理：①對那些沒有在G中出現(xiàn)過的M成員設(shè)置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入OPEN表。（新生成的）②對那些原來已在G中出現(xiàn)過，但還沒有被擴展的M成員，確定是否需要修改它指向父節(jié)點的指針。（原生成但未擴展的）③對于那些先前已在G中出現(xiàn)過，并已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。（原生成也擴展過的）狀態(tài)空間的搜索策略圖搜索的一般過程圖搜索的一般過程(7)按某種策略對OPEN表中的節(jié)點進行排序。(8)轉(zhuǎn)第(2)步。狀態(tài)空間的搜索策略圖搜索的一般過程狀態(tài)空間的搜索策略廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想：從初始節(jié)點S開始逐層向下擴展，在第n層節(jié)點還沒有全部搜索完之前，不進入第n+1層節(jié)點的搜索。未擴展節(jié)點表OPEN表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索的例子：八數(shù)碼難題在3×3的方格棋盤上，分別放置了表有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標狀態(tài)Sg，如下圖所示。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑。1238476528314765S0Sg廣度優(yōu)先搜索廣度優(yōu)先搜索的例子：八數(shù)碼難題123847652廣度優(yōu)先搜索八數(shù)碼難題的寬度優(yōu)先搜索樹廣度優(yōu)先搜索八數(shù)碼難題的寬度優(yōu)先搜索樹廣度優(yōu)先搜索在上述廣度優(yōu)先算法中需要注意兩個問題：對于任意一個可擴展的節(jié)點，總是按照固定的操作符的順序?qū)ζ溥M行擴展（空格左移、上移、右移、下移）。在對任一節(jié)點進行擴展的時候，如果所得的某個子節(jié)點（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復畫出（不送入OPEN表）。因此，廣度優(yōu)先搜索的本質(zhì)是，以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。廣度優(yōu)先搜索在上述廣度優(yōu)先算法中需要注意兩個問題：廣度優(yōu)先搜索廣度優(yōu)先搜索的特點：優(yōu)點：只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點：廣度優(yōu)先搜索盲目性較大，當目標節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。廣度優(yōu)先搜索廣度優(yōu)先搜索的特點：狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索的基本思想：從初始節(jié)點S開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索算法流程：

(1)把初始節(jié)點S放入OPEN表中；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索：八數(shù)碼難題八數(shù)碼難題的深度優(yōu)先搜索如右圖首先擴展最新產(chǎn)生的(最深的)節(jié)點如果目標節(jié)點不在當前搜索的分支上？深度優(yōu)先搜索深度優(yōu)先搜索：深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。深度優(yōu)先搜索本質(zhì)：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先有界深度優(yōu)先搜索有界深度優(yōu)先搜索：動機：為了防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度，即深度界限。思想：對狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限，設(shè)為dm，當搜索深度達到了深度界限而仍未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。有界深度優(yōu)先搜索有界深度優(yōu)先搜索：有界深度優(yōu)先搜索八數(shù)碼難題：dm=4有界深度優(yōu)先搜索八數(shù)碼難題：dm=4有界深度優(yōu)先搜索有界深度優(yōu)先搜索：問題：如果問題有解，且其路徑長度≤dm

，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。有界深度優(yōu)先搜索有界深度優(yōu)先搜索：狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略代價樹搜索代價樹：邊上標有代價(或費用)的樹稱為代價樹在代價樹中，若用g(x)表示從初始節(jié)點S到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)代價樹搜索：考慮邊的代價的搜索方法，代價樹搜索的目的是為了找到一條代價最小的解路徑。代價樹搜索方法包括：代價樹的廣度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹搜索代價樹：邊上標有代價(或費用)的樹稱為代價樹代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索基本思想：每次從OPEN表中選擇節(jié)點往CLOSED表傳送時，總是選擇其中代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置上。如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。該算法應(yīng)用的條件：該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉(zhuǎn)換為代價樹。代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標。若是，則找到了問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；否則轉(zhuǎn)第(6)步；(6)擴展節(jié)點n，為每一個子節(jié)點都配置指向父節(jié)點的指針，計算各子節(jié)點的代價，并將各子節(jié)點放入OPEN表中。并根據(jù)各子結(jié)點的代價對OPEN表中的全部結(jié)點按由小到大的順序排序。然后轉(zhuǎn)第(2)步。代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法流程：代價樹的廣度優(yōu)先搜索例子：城市交通問題。設(shè)有5個城市，它們之間的交通線路如下方左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從A市出發(fā)到E市，費用最小的交通路線。ABCDE434523城市交通圖代價樹的廣度優(yōu)先搜索例子：城市交通問題。設(shè)有5個城市，它們之代價樹的廣度優(yōu)先搜索解：首先將交通圖轉(zhuǎn)化為代價樹。具體轉(zhuǎn)化方法如下：從起始節(jié)點A開始，把與它直接相鄰的節(jié)點作為它的子節(jié)點對其他節(jié)點也做相同的處理若一個節(jié)點已經(jīng)為某節(jié)點的直系先輩節(jié)點時，就不能作為這個節(jié)點的子節(jié)點。圖中除了起始節(jié)點A之外，其它節(jié)點都可能要在代價樹中出現(xiàn)多次，為了區(qū)分它們的多次出現(xiàn)，分別用下標1,2，……標出城市交通圖的代價樹245AC1B1D1D2E1E2B2C2E3E43434235ABCDE434523代價樹的廣度優(yōu)先搜索解：首先將交通圖轉(zhuǎn)化為代價樹。具體轉(zhuǎn)化方代價樹的廣度優(yōu)先搜索解：對此代價樹進行廣度優(yōu)先搜索，可得到最優(yōu)解，如圖紅線部分為最優(yōu)解，其代價為8ABCDE434523245AC1B1D1D2E1E2B2C2E3E43434235代價樹的廣度優(yōu)先搜索解：對此代價樹進行廣度優(yōu)先搜索，可得到最代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索基本思想：與代價樹的廣度優(yōu)先搜索不同，代價樹的深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選擇一個代價最小的節(jié)點送入CLOSED表進行考察，而不是在整個OPEN表中選擇代價最小的。代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，生成其子節(jié)點，將這些子節(jié)點按邊代價由小到大放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法流程：狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索上述幾種搜索方法的本質(zhì)是，以初始節(jié)點為根節(jié)點，按照既定的策略對狀態(tài)空間圖進行遍歷，并希望能夠盡早發(fā)現(xiàn)目標節(jié)點。由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點較多，效率不高。狀態(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)空間的搜索策略啟發(fā)性信息和估價函數(shù)啟發(fā)式搜索：采用問題自身的特性信息，以指導搜索朝著最有希望的方向前進。啟發(fā)性信息的概念：啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的，并可指導搜索過程朝著最有希望方向前進的控制信息。啟發(fā)信息的啟發(fā)能力越強，擴展的無用結(jié)點越少。啟發(fā)性信息的種類有效地幫助確定擴展節(jié)點的信息有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息啟發(fā)性信息和估價函數(shù)啟發(fā)式搜索：采用問題自身的特性信息，以指啟發(fā)性信息和估價函數(shù)估價函數(shù)：用于評估節(jié)點重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)的一般形式為：f(x)=g(x)+h(x)g(x)表示從初始節(jié)點S0到節(jié)點x的代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的代價的估計，它體現(xiàn)了問題的啟發(fā)性信息。h(x)稱為啟發(fā)函數(shù)。啟發(fā)性信息和估價函數(shù)估價函數(shù)：用于評估節(jié)點重要性的函數(shù)稱為估啟發(fā)性信息和估價函數(shù)例子：八數(shù)碼難題設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示估價函數(shù)為：f(n)=d(n)+W(n)d(n)：表示節(jié)點n在搜索樹中的深度W(n)：表示節(jié)點n中“錯放”的棋子個數(shù)請計算初始狀態(tài)S0的估價函數(shù)值f(S0)1238476528314765S0Sg啟發(fā)性信息和估價函數(shù)例子：八數(shù)碼難題123847652831啟發(fā)性信息和估價函數(shù)計算初始狀態(tài)S0的估價函數(shù)值f(S0)解：取g(n)=d(n)，h(n)=W(n)它說明是用從S0到n的路徑上的單位代價表示實際代價用結(jié)點n中“錯放”的棋子個數(shù)作為啟發(fā)信息。一般來說，某節(jié)點中的“錯放”的棋子個數(shù)越多，說明它離目標節(jié)點越遠（代價的估計）。對初始節(jié)點S0，d(S0)=0，W(S0)=3。因此，f(S0)=0+3=3

1238476528314765S0Sg啟發(fā)性信息和估價函數(shù)計算初始狀態(tài)S0的估價函數(shù)值f(S0)1狀態(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é)點進行排序，則該搜索算法為A算法。

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

從OPEN表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。局部擇優(yōu)搜索算法：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。A算法A算法：在圖搜索算法中，如果能在搜索的每一步都利用估價A算法全局擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴展，則轉(zhuǎn)第2步。(6)擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉(zhuǎn)第2步。A算法全局擇優(yōu)搜索算法流程A算法全局擇優(yōu)搜索算法：八數(shù)碼難題設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示估價函數(shù)為：f(n)=d(n)+W(n)d(n)：表示節(jié)點n在搜索樹中的深度W(n)：表示節(jié)點n中“不在位”的數(shù)碼個數(shù)用全局擇優(yōu)搜索解決該問題1238476528314765S0SgA算法全局擇優(yōu)搜索算法：八數(shù)碼難題1238476528314啟發(fā)性信息和估價函數(shù)用全局擇優(yōu)搜索求解八數(shù)碼難題解：該問題的全局擇優(yōu)搜索樹如右圖所示在該圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值該問題的解為：S0→S1→S2→S3→Sg啟發(fā)性信息和估價函數(shù)用全局擇優(yōu)搜索求解八數(shù)碼難題A算法局部擇優(yōu)搜索算法流程(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴展，則轉(zhuǎn)第2步。(6)擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。A算法局部擇優(yōu)搜索算法流程狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略問題？問題？ArtificialIntelligence(AI)

人工智能第二章：知識表示與推理ArtificialIntelligence(AI)

人內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略3.自然演繹推理4.消解演繹推理5.基于規(guī)則的演繹推理二、確定性推理內(nèi)容提要第二章：知識表示與推理1.推理的基本概念2.搜索策略搜索策略搜索策略搜索的基本概念狀態(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)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定OPEN表：未擴展節(jié)點表，用于存放剛生成節(jié)點CLOSED表：已擴展節(jié)點表，用于存放已經(jīng)擴展或?qū)⒁獢U展的節(jié)點S：用表示問題的初始狀態(tài)G：表示搜索過程所得到的搜索圖M：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集狀態(tài)空間的搜索策略狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定狀態(tài)空間的搜索策略圖搜索的一般過程(1)把初始節(jié)點S放入未擴展節(jié)點表OPEN表，并建立目前僅包含S的圖G；(2)檢查OPEN表是否為空，若為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入已擴展節(jié)點表CLOSED表，并記該節(jié)點為節(jié)點n；(4)考察節(jié)點n是否為目標節(jié)點。若是則得到了問題的解，成功退出。此時的解為追蹤圖G中沿著指針（步驟6中設(shè)置的指針）從n到初始節(jié)點S的路徑。狀態(tài)空間的搜索策略圖搜索的一般過程狀態(tài)空間的搜索策略圖搜索的一般過程(5)擴展節(jié)點n，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n先輩的那部分子節(jié)點記入集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中(6)針對M中子節(jié)點的不同情況，分別作如下處理：①對那些沒有在G中出現(xiàn)過的M成員設(shè)置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入OPEN表。（新生成的）②對那些原來已在G中出現(xiàn)過，但還沒有被擴展的M成員，確定是否需要修改它指向父節(jié)點的指針。（原生成但未擴展的）③對于那些先前已在G中出現(xiàn)過，并已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。（原生成也擴展過的）狀態(tài)空間的搜索策略圖搜索的一般過程圖搜索的一般過程(7)按某種策略對OPEN表中的節(jié)點進行排序。(8)轉(zhuǎn)第(2)步。狀態(tài)空間的搜索策略圖搜索的一般過程狀態(tài)空間的搜索策略廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想：從初始節(jié)點S開始逐層向下擴展，在第n層節(jié)點還沒有全部搜索完之前，不進入第n+1層節(jié)點的搜索。未擴展節(jié)點表OPEN表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索的例子：八數(shù)碼難題在3×3的方格棋盤上，分別放置了表有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標狀態(tài)Sg，如下圖所示。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑。1238476528314765S0Sg廣度優(yōu)先搜索廣度優(yōu)先搜索的例子：八數(shù)碼難題123847652廣度優(yōu)先搜索八數(shù)碼難題的寬度優(yōu)先搜索樹廣度優(yōu)先搜索八數(shù)碼難題的寬度優(yōu)先搜索樹廣度優(yōu)先搜索在上述廣度優(yōu)先算法中需要注意兩個問題：對于任意一個可擴展的節(jié)點，總是按照固定的操作符的順序?qū)ζ溥M行擴展（空格左移、上移、右移、下移）。在對任一節(jié)點進行擴展的時候，如果所得的某個子節(jié)點（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復畫出（不送入OPEN表）。因此，廣度優(yōu)先搜索的本質(zhì)是，以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。廣度優(yōu)先搜索在上述廣度優(yōu)先算法中需要注意兩個問題：廣度優(yōu)先搜索廣度優(yōu)先搜索的特點：優(yōu)點：只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點：廣度優(yōu)先搜索盲目性較大，當目標節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。廣度優(yōu)先搜索廣度優(yōu)先搜索的特點：狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索的基本思想：從初始節(jié)點S開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索算法流程：

(1)把初始節(jié)點S放入OPEN表中；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索：八數(shù)碼難題八數(shù)碼難題的深度優(yōu)先搜索如右圖首先擴展最新產(chǎn)生的(最深的)節(jié)點如果目標節(jié)點不在當前搜索的分支上？深度優(yōu)先搜索深度優(yōu)先搜索：深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。深度優(yōu)先搜索本質(zhì)：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先有界深度優(yōu)先搜索有界深度優(yōu)先搜索：動機：為了防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度，即深度界限。思想：對狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限，設(shè)為dm，當搜索深度達到了深度界限而仍未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。有界深度優(yōu)先搜索有界深度優(yōu)先搜索：有界深度優(yōu)先搜索八數(shù)碼難題：dm=4有界深度優(yōu)先搜索八數(shù)碼難題：dm=4有界深度優(yōu)先搜索有界深度優(yōu)先搜索：問題：如果問題有解，且其路徑長度≤dm

，則上述搜索過程一定能求得解。但是，若解的路徑長度>dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。有界深度優(yōu)先搜索有界深度優(yōu)先搜索：狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想圖搜索的一般過程狀態(tài)空間的盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)A算法和A*算法狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略代價樹搜索代價樹：邊上標有代價(或費用)的樹稱為代價樹在代價樹中，若用g(x)表示從初始節(jié)點S到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)代價樹搜索：考慮邊的代價的搜索方法，代價樹搜索的目的是為了找到一條代價最小的解路徑。代價樹搜索方法包括：代價樹的廣度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹搜索代價樹：邊上標有代價(或費用)的樹稱為代價樹代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索基本思想：每次從OPEN表中選擇節(jié)點往CLOSED表傳送時，總是選擇其中代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置上。如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。該算法應(yīng)用的條件：該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉(zhuǎn)換為代價樹。代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標。若是，則找到了問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；否則轉(zhuǎn)第(6)步；(6)擴展節(jié)點n，為每一個子節(jié)點都配置指向父節(jié)點的指針，計算各子節(jié)點的代價，并將各子節(jié)點放入OPEN表中。并根據(jù)各子結(jié)點的代價對OPEN表中的全部結(jié)點按由小到大的順序排序。然后轉(zhuǎn)第(2)步。代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索算法流程：代價樹的廣度優(yōu)先搜索例子：城市交通問題。設(shè)有5個城市，它們之間的交通線路如下方左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的廣度優(yōu)先搜索，求從A市出發(fā)到E市，費用最小的交通路線。ABCDE434523城市交通圖代價樹的廣度優(yōu)先搜索例子：城市交通問題。設(shè)有5個城市，它們之代價樹的廣度優(yōu)先搜索解：首先將交通圖轉(zhuǎn)化為代價樹。具體轉(zhuǎn)化方法如下：從起始節(jié)點A開始，把與它直接相鄰的節(jié)點作為它的子節(jié)點對其他節(jié)點也做相同的處理若一個節(jié)點已經(jīng)為某節(jié)點的直系先輩節(jié)點時，就不能作為這個節(jié)點的子節(jié)點。圖中除了起始節(jié)點A之外，其它節(jié)點都可能要在代價樹中出現(xiàn)多次，為了區(qū)分它們的多次出現(xiàn)，分別用下標1,2，……標出城市交通圖的代價樹245AC1B1D1D2E1E2B2C2E3E43434235ABCDE434523代價樹的廣度優(yōu)先搜索解：首先將交通圖轉(zhuǎn)化為代價樹。具體轉(zhuǎn)化方代價樹的廣度優(yōu)先搜索解：對此代價樹進行廣度優(yōu)先搜索，可得到最優(yōu)解，如圖紅線部分為最優(yōu)解，其代價為8ABCDE434523245AC1B1D1D2E1E2B2C2E3E43434235代價樹的廣度優(yōu)先搜索解：對此代價樹進行廣度優(yōu)先搜索，可得到最代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索基本思想：與代價樹的廣度優(yōu)先搜索不同，代價樹的深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選擇一個代價最小的節(jié)點送入CLOSED表進行考察，而不是在整個OPEN表中選擇代價最小的。代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法流程：(1)把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；(2)如果OPEN表為空，則問題無解，失敗退出；(3)把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，生成其子節(jié)點，將這些子節(jié)點按邊代價由小到大放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索算法流程：狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索上述幾種搜索方法的本質(zhì)是，以初始節(jié)點為根節(jié)點，按照既定的策略對狀態(tài)空間圖進行遍歷，并希望能夠盡早發(fā)現(xiàn)目標節(jié)點。由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點較多，效率不高。狀態(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)空間的搜索策略啟發(fā)性信息和估價函數(shù)啟發(fā)式搜索：采用問題自身的特性信息，以指導搜索朝著最有希望的方向前進。啟發(fā)性信息的概念：啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的，并可指導搜索過程朝著最有希望方向前進的控制信息。啟發(fā)信息的啟發(fā)能力越強，擴展的無用結(jié)點越少。啟發(fā)性信息的種類有效地幫助確定擴展節(jié)點的信息有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息啟發(fā)性信息和估價函數(shù)啟發(fā)式搜索：采用問題自身的特性信息，以指啟發(fā)性信息和估價函數(shù)估價函數(shù)：用于評估節(jié)點重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)的一般形式為：f(x)=g(x)+h(x)g(x)表示從初始節(jié)點S0到節(jié)點x的代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的代價的估計，它體現(xiàn)了問題的啟發(fā)性信息。h(x)稱為啟發(fā)函數(shù)。啟發(fā)性信息和估價函數(shù)估價函數(shù)：用于評估節(jié)點重要性的函數(shù)稱為估啟發(fā)性信息和估價函數(shù)例子：八數(shù)碼難題設(shè)問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示估價函數(shù)為：f(n)=d(n)+W(n)d(n)：表示節(jié)點n在搜索樹中的深度W(n)：表示節(jié)點n中“錯放”的棋子個數(shù)請計算初始狀態(tài)S0的估價函數(shù)值f(S0)1238476528314765S0Sg啟發(fā)性信息和估價函數(shù)例子：八數(shù)碼難題123847652831啟發(fā)性信息和估價函數(shù)計算初始狀態(tài)S0的估價函數(shù)值f(S0)解：取g(n)=d(n)，h(n)=W(n)它說明是用從S