1、2022-5-1人人 工工 智智 能能Artificial Intelligence (AI)許建華許建華南京師范大學(xué)計算機(jī)科學(xué)系南京師范大學(xué)計算機(jī)科學(xué)系2006年年9-12月月2022-5-12.1 知識表示的一般方法知識表示的一般方法2.1.1 狀態(tài)空間法狀態(tài)空間法2.1.2 問題歸約法問題歸約法2.2.3 謂詞邏輯法謂詞邏輯法2022-5-1用計算機(jī)技術(shù)解決實際問題的一般思路用計算機(jī)技術(shù)解決實際問題的一般思路:實際實際問題問題問題表達(dá)問題表達(dá)知識表達(dá)知識表達(dá)數(shù)學(xué)建模數(shù)學(xué)建模求解的方法求解的方法或者算法或者算法結(jié)果的解釋結(jié)果的解釋2022-5-1例：求側(cè)面積為例：求側(cè)面積為150平方米的體

2、積最大的長方體？平方米的體積最大的長方體？設(shè)長、寬、高分別為設(shè)長、寬、高分別為 x, y, z側(cè)面積為：側(cè)面積為：2(xy + yz + xz)體積為：體積為：xyz數(shù)學(xué)模型數(shù)學(xué)模型 max xyz s.t. 2(xy + yz + xz)=150 xyz2022-5-1利用最優(yōu)化技術(shù)中的算法，可以得到結(jié)果：利用最優(yōu)化技術(shù)中的算法，可以得到結(jié)果：x = y = z = 5.0解釋解釋：長、寬、高都等于：長、寬、高都等于5米時，體積最大米時，體積最大說明說明：在計算數(shù)學(xué)的課程中，主要關(guān)心求解的：在計算數(shù)學(xué)的課程中，主要關(guān)心求解的具體算法具體算法2022-5-1在人工智能中，重點(diǎn)關(guān)注兩個方面的內(nèi)容

3、在人工智能中，重點(diǎn)關(guān)注兩個方面的內(nèi)容：問題的表示問題的表示（知識的表示）（知識的表示）：即要找到問題的一：即要找到問題的一種合適的表示方法種合適的表示方法在符號主義的人工智能中，有：在符號主義的人工智能中，有：狀態(tài)空間法狀態(tài)空間法問題歸約法問題歸約法謂詞邏輯法謂詞邏輯法其它表示方法其它表示方法2022-5-1問題的求解問題的求解：從問題表示方法出發(fā)，找到一個：從問題表示方法出發(fā)，找到一個合理的辦法來求解合理的辦法來求解在符號主義的人工智能中，常有的方法有：在符號主義的人工智能中，常有的方法有：搜索法搜索法推理法推理法2022-5-12.1.1 狀態(tài)空間法狀態(tài)空間法 1 問題的狀態(tài)描述問題的狀態(tài)

4、描述2 狀態(tài)圖示法狀態(tài)圖示法3 例子例子2022-5-1在日常的一些智力游戲（八數(shù)碼、走八卦陣、走在日常的一些智力游戲（八數(shù)碼、走八卦陣、走迷宮等）中，我們采用的迷宮等）中，我們采用的策略策略：試著向前走，如試著向前走，如果走不通，則往后退，不停地試、試、試，直到果走不通，則往后退，不停地試、試、試，直到成功成功12457836123456782022-5-1類似地，在人工智能中，一種最基本的類似地，在人工智能中，一種最基本的求解方法求解方法就就是試探搜索法，即，通過在某個可能的是試探搜索法，即，通過在某個可能的解空間解空間（例（例如，所有可能的走法）中尋找一個解（如，一種走如，所有可能的走法

5、）中尋找一個解（如，一種走法）法）這種基于解空間的這種基于解空間的問題表示問題表示和和求解方法求解方法就是就是狀態(tài)空間法狀態(tài)空間法，其基礎(chǔ)是，其基礎(chǔ)是狀態(tài)狀態(tài)和和算符算符（算子）（算子）2022-5-11 問題的狀態(tài)描述問題的狀態(tài)描述狀態(tài)狀態(tài)：描述某一類不同事物間的描述某一類不同事物間的差別差別而引入的一而引入的一組組最少最少變量變量q0 ,q1 , qn的的有序有序集合集合2022-5-1例：例：描述在坐的同學(xué)描述在坐的同學(xué)變量可以有變量可以有年級年級專業(yè)專業(yè)姓名姓名性別性別學(xué)號學(xué)號2022-5-1矢量形式矢量形式： Q= q0, q1, , qn T 其中，元素其中，元素 qi ( i=0

6、, 1, n)為集合的分為集合的分量，稱為量，稱為狀態(tài)變量狀態(tài)變量。具體狀態(tài)具體狀態(tài)：給每一個狀態(tài)變量一個具體的：給每一個狀態(tài)變量一個具體的值（符號、數(shù)值等）。值（符號、數(shù)值等）。2022-5-1矩陣形式矩陣形式1111.nmmnqqQqq2022-5-1例：例：八數(shù)碼問題八數(shù)碼問題矢量形式的狀態(tài)表示：矢量形式的狀態(tài)表示：12347865矩陣形式的狀態(tài)表示：矩陣形式的狀態(tài)表示：1, 2, 3, 4, 7, 8, 6, 5, 01234786502022-5-1算符（操作符）算符（操作符）：使問題從一個狀態(tài)使問題從一個狀態(tài)變換到另一狀態(tài)的手段。變換到另一狀態(tài)的手段。例如：走步、規(guī)則、數(shù)學(xué)算子、運(yùn)

7、算例如：走步、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號等等。符號等等。2022-5-1例：例：描述在坐的同學(xué)（續(xù)）描述在坐的同學(xué)（續(xù)）狀態(tài)變量狀態(tài)變量可以有可以有年級年級專業(yè)專業(yè)姓名姓名性別性別學(xué)號學(xué)號操作符操作符入學(xué)入學(xué)正常升級正常升級畢業(yè)畢業(yè)2022-5-1例：例：八數(shù)碼問題八數(shù)碼問題12347865算符算符：1、數(shù)字的上、下、左、右移動、數(shù)字的上、下、左、右移動2、空格的上、下、左、右移動、空格的上、下、左、右移動2022-5-1問題的狀態(tài)空間問題的狀態(tài)空間：一個表示問題全部可能狀一個表示問題全部可能狀態(tài)及其關(guān)系的圖，它包含了三個集合：態(tài)及其關(guān)系的圖，它包含了三個集合：1. 所有可能的問題初始狀態(tài)集合所

8、有可能的問題初始狀態(tài)集合S2. 操作符集合操作符集合F3. 目標(biāo)狀態(tài)集合目標(biāo)狀態(tài)集合G狀態(tài)空間記作三元狀態(tài)（狀態(tài)空間記作三元狀態(tài)（S, F, G） 2022-5-1例：例：十五數(shù)碼問題十五數(shù)碼問題 123456789101112131415 119415131275861321014初始狀態(tài)初始狀態(tài)：左圖：左圖目標(biāo)狀態(tài)目標(biāo)狀態(tài)：右圖：右圖操作符集合操作符集合F空格的左移、上移、右移、下移空格的左移、上移、右移、下移 2022-5-1可能的求解過程可能的求解過程注注：在程序和圖示求解過程中，需要規(guī)定好操作符：在程序和圖示求解過程中，需要規(guī)定好操作符的使用順序的使用順序2022-5-1要完成某一個

9、具體問題的狀態(tài)描述，必須完要完成某一個具體問題的狀態(tài)描述，必須完成成三項工作三項工作：如何描述狀態(tài)，特別是初始狀態(tài)如何描述狀態(tài)，特別是初始狀態(tài)操作符集合及其對狀態(tài)描述的作用操作符集合及其對狀態(tài)描述的作用如何描述目標(biāo)狀態(tài)如何描述目標(biāo)狀態(tài)即定義好三元狀態(tài)（即定義好三元狀態(tài)（S, F, G）中的三個成分中的三個成分 2022-5-1狀態(tài)空間法狀態(tài)空間法：從某一個初始狀態(tài)開始，每次施加一個操作符，遞從某一個初始狀態(tài)開始，每次施加一個操作符，遞增地建立操作符序列，直到達(dá)到目標(biāo)狀態(tài)為止增地建立操作符序列，直到達(dá)到目標(biāo)狀態(tài)為止2022-5-1狀態(tài)空間法的問題狀態(tài)空間法的問題：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某一個

10、操作符序列尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某一個操作符序列狀態(tài)空間法的解狀態(tài)空間法的解：從初始狀態(tài)變換到目標(biāo)狀態(tài)的操作符序列從初始狀態(tài)變換到目標(biāo)狀態(tài)的操作符序列1194151312758613210 14123456789101112131415 2022-5-12 狀態(tài)圖示法狀態(tài)圖示法 圖圖是由節(jié)點(diǎn)（不一定是有限個的節(jié)點(diǎn)）的集合是由節(jié)點(diǎn)（不一定是有限個的節(jié)點(diǎn)）的集合構(gòu)成的構(gòu)成的注意注意：在圖論中，圖的定義中還包括邊的集合：在圖論中，圖的定義中還包括邊的集合狀態(tài)空間法（求解過程）的表示方法：用圖來表狀態(tài)空間法（求解過程）的表示方法：用圖來表示（借助于圖論中某些技術(shù)）示（借助于圖論中某些技術(shù)）2022

11、-5-1有向圖和無向圖：有向圖和無向圖：2022-5-1無向圖無向圖：一對節(jié)點(diǎn)可能互為后裔，邊用線段：一對節(jié)點(diǎn)可能互為后裔，邊用線段來表示來表示2022-5-1有向圖有向圖：一對節(jié)點(diǎn)用弧線連接起來，并且從一一對節(jié)點(diǎn)用弧線連接起來，并且從一個節(jié)點(diǎn)指向另一個節(jié)點(diǎn)個節(jié)點(diǎn)指向另一個節(jié)點(diǎn) 父輩節(jié)點(diǎn)或祖先父輩節(jié)點(diǎn)或祖先n i后繼節(jié)點(diǎn)或后裔后繼節(jié)點(diǎn)或后裔nj 2022-5-1對于某一個節(jié)點(diǎn)序列對于某一個節(jié)點(diǎn)序列（ni1, ni2, nij, , nik） 如果每一個節(jié)點(diǎn)如果每一個節(jié)點(diǎn)nij-1都有一個都有一個后繼節(jié)點(diǎn)后繼節(jié)點(diǎn) nij 存在，則將這一存在，則將這一序列稱為從節(jié)點(diǎn)序列稱為從節(jié)點(diǎn) ni1 到到 n

12、ik 的的長度為長度為 k 的路徑。的路徑。 nikni12022-5-1如果從節(jié)點(diǎn)如果從節(jié)點(diǎn) ni 到到 nj 存在存在一條路徑，則稱節(jié)點(diǎn)一條路徑，則稱節(jié)點(diǎn) nj 是是從節(jié)點(diǎn)從節(jié)點(diǎn) ni 可到達(dá)的節(jié)點(diǎn)，可到達(dá)的節(jié)點(diǎn)，或者稱或者稱 nj 是是 ni 的后裔節(jié)的后裔節(jié)點(diǎn)、稱點(diǎn)、稱 ni 是是 nj 的祖先。的祖先。 njni2022-5-1當(dāng)用有向圖來表示狀態(tài)空間法時，對應(yīng)關(guān)系：當(dāng)用有向圖來表示狀態(tài)空間法時，對應(yīng)關(guān)系：圖中的一個圖中的一個節(jié)點(diǎn)節(jié)點(diǎn)對應(yīng)于某一個對應(yīng)于某一個狀態(tài)狀態(tài)圖中的一個圖中的一個有向弧有向弧對應(yīng)于某一個對應(yīng)于某一個算符算符 注注：有向：有向弧的旁邊可以標(biāo)以具體算符弧的旁邊可以標(biāo)

13、以具體算符2022-5-1狀態(tài)狀態(tài)節(jié)點(diǎn)節(jié)點(diǎn)操作符操作符有向弧有向弧2022-5-1問題問題：尋找從初始狀態(tài)到目標(biāo)：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的某個操作符序列狀態(tài)的某個操作符序列問題問題：尋找圖中初始節(jié)點(diǎn)（對應(yīng)初：尋找圖中初始節(jié)點(diǎn)（對應(yīng)初始狀態(tài)）到目標(biāo)節(jié)點(diǎn)（對應(yīng)于目標(biāo)始狀態(tài)）到目標(biāo)節(jié)點(diǎn)（對應(yīng)于目標(biāo)狀態(tài)）的一條路徑狀態(tài)）的一條路徑轉(zhuǎn)化為轉(zhuǎn)化為2022-5-1c (ni , nj) 表示從節(jié)點(diǎn)表示從節(jié)點(diǎn) ni 指向節(jié)點(diǎn)指向節(jié)點(diǎn) nj （相鄰）的（相鄰）的那一段弧的代價那一段弧的代價 n jn i在某些情況下，每個操作符作用、成本是不在某些情況下，每個操作符作用、成本是不一樣的，需要引入一樣的，需要引入

14、代價代價的概念的概念2022-5-1（不相鄰的）兩個節(jié)點(diǎn)（不相鄰的）兩個節(jié)點(diǎn)間路徑的代價間路徑的代價等于等于連接連接該路徑的各個節(jié)點(diǎn)的所該路徑的各個節(jié)點(diǎn)的所有弧線的代價之和有弧線的代價之和 nkn0C(n0,n1)C(nk-1,nk)2022-5-1引入代價的概念后，我們的問題可能是：引入代價的概念后，我們的問題可能是：尋找初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的代價最小的尋找初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的代價最小的路徑路徑對應(yīng)的原始問題對應(yīng)的原始問題：尋找從初始狀態(tài)到目標(biāo)狀：尋找從初始狀態(tài)到目標(biāo)狀態(tài)的操作符代價之和最小的操作符序列態(tài)的操作符代價之和最小的操作符序列2022-5-1利用圖論的技術(shù)，我們要解決兩個問題

15、：利用圖論的技術(shù)，我們要解決兩個問題：第一、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑。對應(yīng)第一、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條路徑。對應(yīng)于于尋找初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列尋找初始狀態(tài)到目標(biāo)狀態(tài)的操作符序列第二、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條代價最小的第二、找出初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條代價最小的路徑。對應(yīng)于路徑。對應(yīng)于尋找將初始狀態(tài)變換到目標(biāo)狀態(tài)所用尋找將初始狀態(tài)變換到目標(biāo)狀態(tài)所用操作符代價之和最小的操作符序列操作符代價之和最小的操作符序列2022-5-13 例子例子 例例1：八數(shù)碼問題八數(shù)碼問題 八數(shù)碼的任何一種擺法是一個八數(shù)碼的任何一種擺法是一個狀態(tài)狀態(tài)，狀態(tài)總數(shù)，狀態(tài)總數(shù)為為9！。用一個長度為！。

16、用一個長度為9的一維數(shù)組來描述狀態(tài)：的一維數(shù)組來描述狀態(tài)：（q1, q2, ,q9）其中，其中，qi 取取0, 1, , 8個數(shù)，個數(shù)，0表示空格，且取值互表示空格，且取值互不相同。不相同。 算符算符是空格的上、下、左、右移動是空格的上、下、左、右移動2022-5-1 如果記空格的位置為如果記空格的位置為P，這時空格的，這時空格的移動規(guī)則移動規(guī)則是：是：12385674123856740PP-3P+1P+3P-1表示位置表示位置1 2 3 4 5 6 7 8 9P2022-5-1 代碼代碼規(guī)則規(guī)則前提條件前提條件應(yīng)用結(jié)果應(yīng)用結(jié)果1左移左移P1,4,7P 位置與位置與 P-1 位置上的元素互換位

17、置上的元素互換2上移上移P1,2,3 P-33右移右移P3,6,9 P+14下移下移P7,8,9 P+3空格移動規(guī)則空格移動規(guī)則123456789表示位置表示位置2022-5-1初始狀態(tài)：初始狀態(tài)：( (2，0，3，1，8，4，5，6，7）目標(biāo)狀態(tài)目標(biāo)狀態(tài): :（1，2，3，8，0，4，7，6，5） 狀態(tài)圖狀態(tài)圖2022-5-1注意注意：事先規(guī)定操作符的前后順序，便于編程事先規(guī)定操作符的前后順序，便于編程不要生成已有的狀態(tài)（節(jié)點(diǎn)），防止進(jìn)入死循環(huán)不要生成已有的狀態(tài)（節(jié)點(diǎn)），防止進(jìn)入死循環(huán)2022-5-1例例2：迷宮問題：迷宮問題 2022-5-1給圖上加一個坐標(biāo)系，定義每一個分叉路口給圖上加一

18、個坐標(biāo)系，定義每一個分叉路口為一個狀態(tài)。為一個狀態(tài)。2022-5-1操作符為人的上、操作符為人的上、下、左、右走動下、左、右走動初始狀態(tài)為（初始狀態(tài)為（1，1）目標(biāo)狀態(tài)為（目標(biāo)狀態(tài)為（4，4）2022-5-1狀態(tài)圖狀態(tài)圖2022-5-1例例3：梵塔問題梵塔問題（三個盤）（三個盤） 對于對于 n 個盤的問題，我們用個盤的問題，我們用 n 維向量維向量 （a1 a2an）表示問題的一個狀態(tài)表示問題的一個狀態(tài)其中其中ai = 1, 2, 3 表示第表示第i個盤位于第一、二、個盤位于第一、二、三個柱子上，三個柱子上，a1 an中盤的大小從中盤的大小從大到小大到小21.naaa2022-5-1初始狀態(tài)初

19、始狀態(tài)為（為（11），目標(biāo)狀態(tài)為（），目標(biāo)狀態(tài)為（33）操作符操作符m(i, j)：表示一個盤從表示一個盤從 i 根柱子搬到第根柱子搬到第 j 根根柱子。柱子。T(k)：表示第表示第 k 根柱子上（最上面）的盤的大小。根柱子上（最上面）的盤的大小。操作符集合為：操作符集合為： O=m( i , j ) | T( i )T( j ) 2022-5-1狀態(tài)圖狀態(tài)圖2022-5-1例例4：猴子與香蕉問題：猴子與香蕉問題 a c b2022-5-1用一個四元組用一個四元組（W，x, Y, z）來表示來表示問題的狀態(tài)問題的狀態(tài)W：猴子的水平位置猴子的水平位置x： 當(dāng)猴子爬到箱子頂上取當(dāng)猴子爬到箱子頂上取

20、1，否則取，否則取0Y： 箱子的水平位置箱子的水平位置z： 當(dāng)猴子摘到香蕉時取當(dāng)猴子摘到香蕉時取1，否則取，否則取0初始狀態(tài)初始狀態(tài)是（是（a, 0, b, 0），），目標(biāo)狀態(tài)目標(biāo)狀態(tài)是（是（c, 1, c, 1）2022-5-1操作符操作符：猴子當(dāng)前位置猴子當(dāng)前位置W走到水平位置走到水平位置U：goto(U)： （W, 0 , Y, z）(U, 0 , Y, z)說明說明：猴子不能在箱子上：猴子不能在箱子上 猴 子 將 箱 子 從猴 子 將 箱 子 從 W 位 置 推 到 水 平 位 置位 置 推 到 水 平 位 置 V ：pushbox(V)： （W, 0, W, z） (V, 0, V,

21、 z)說明說明：猴子與箱子的位置同時變化：猴子與箱子的位置同時變化2022-5-1操作符操作符：猴子爬到箱子上：猴子爬到箱子上：climbbox： （W, 0, W, z） (W，1, W, z)猴子摘到香蕉：猴子摘到香蕉：grasp： （c, 1, c, 0） (c, 1, c, 1)2022-5-1a c bpushbox(c)(a, 0, b, 0)(b, 0, b, 0)(c, 0, c, 0)(b, 1, b, 0)(c, 1, c, 0)(c, 1, c, 1)goto(b)climbboxclimbboxgrasp狀態(tài)空間圖狀態(tài)空間圖2022-5-12.1.2 問題歸約法問題歸約

22、法 例：求積分例：求積分 解法解法1：解法解法2：解法解法3：2(cos)xexxdx223(cos)cossin3xxxexxdxe dxxdxx dxxex2022-5-1問問 題題解法解法1解法解法2解法解法3解法解法4子子問題問題1子子問題問題2子子問題問題3變換變換分解分解2022-5-1問題歸約法問題歸約法：從已知問題的描述出發(fā)，通過一系列從已知問題的描述出發(fā)，通過一系列變換變換或或分解分解將問題最終變?yōu)橐粋€將問題最終變?yōu)橐粋€子問題集合子問題集合，這些子問題的，這些子問題的解可以直接得到，從而解決初始問題解可以直接得到，從而解決初始問題 2022-5-1問題歸約法由三個部分組成問題

23、歸約法由三個部分組成： 一個初始問題描述一個初始問題描述 一套將問題變換或分解為子問題的操作符一套將問題變換或分解為子問題的操作符 一套本原問題（一套本原問題（解可以直接得到的簡單問題解可以直接得到的簡單問題）描述描述2022-5-11 問題歸約描述問題歸約描述 例：例：梵塔問題梵塔問題（三個盤）（三個盤） (a) 初始配置初始配置(b) 目標(biāo)配置目標(biāo)配置圖圖2.6 梵塔難題梵塔難題2022-5-1解決問題的思路解決問題的思路：第一第一、要將所有盤從第一個柱子搬到第三個、要將所有盤從第一個柱子搬到第三個柱子，根據(jù)游戲規(guī)則，首先要搬最大的柱子，根據(jù)游戲規(guī)則，首先要搬最大的 C 盤盤到第三個柱子上

24、到第三個柱子上(a) 初始配初始配置置(b) 目標(biāo)配置目標(biāo)配置圖圖2.6 梵塔難題梵塔難題2022-5-1解決問題的思路解決問題的思路：第二第二、要能夠搬、要能夠搬 C 盤，條件是：第三個柱盤，條件是：第三個柱子是空的，子是空的，A、B必須在第二個柱子上（這必須在第二個柱子上（這里沒有考慮如何搬里沒有考慮如何搬A、B盤）盤）(a) 初始配初始配置置(b) 目標(biāo)配置目標(biāo)配置圖圖2.6 梵塔難題梵塔難題2022-5-1解決問題的思路解決問題的思路：第三第三、搬、搬C盤到第三個柱子，然后想辦法將盤到第三個柱子，然后想辦法將A、B盤搬到第三個柱子上盤搬到第三個柱子上 (a) 初始配初始配置置(b) 目

25、標(biāo)配置目標(biāo)配置圖圖2.6 梵塔難題梵塔難題2022-5-1將問題簡化為下列三個子問題：將問題簡化為下列三個子問題：1. 移動園盤移動園盤A和和B到柱子到柱子2的雙園盤難題的雙園盤難題2. 移動移動C盤到柱子盤到柱子3的單園盤難題的單園盤難題3. 移動移動A和和B到柱子到柱子3的雙園盤難題的雙園盤難題2022-5-1圖圖2.8 梵塔問題的歸約梵塔問題的歸約從左到右表示盤從左到右表示盤從大到從大到小，數(shù)字表示柱子號小，數(shù)字表示柱子號小小盤：盤：13中盤：中盤：12小盤：小盤：32小小盤：盤：21中盤：中盤：23小盤：小盤：13與與中小盤中小盤1到到2大盤大盤1到到3中小盤中小盤2到到32022-5

26、-1問題歸約法的問題歸約法的基本思路基本思路是：應(yīng)用一系列算符將原是：應(yīng)用一系列算符將原始問題的描述始問題的描述變換或分解變換或分解成為子問題的描述成為子問題的描述問題的描述問題的描述可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹、可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹、矢量、數(shù)組等矢量、數(shù)組等對于梵塔問題，問題及子問題描述：對于梵塔問題，問題及子問題描述： (113)(333)2022-5-1問題歸約法可以用一個三元組（問題歸約法可以用一個三元組（S, O, P）來表示，來表示，其中：其中： S：原始問題，即要解決的問題原始問題，即要解決的問題 P：本原問題集，其中的每一個問題是不用證本原問題集，其中的每一個問題是

27、不用證明的或自然成立的，例如公理、已知事實等明的或自然成立的，例如公理、已知事實等 O：操作算子集，用于將問題化為子問題操作算子集，用于將問題化為子問題2022-5-12 與或圖表示與或圖表示 例例：有一個問題：有一個問題A，它可以通過三種途徑來求解：它可以通過三種途徑來求解：(1)、求解問題、求解問題 B 和和 C(2)、求解問題求解問題 D 、E 和和 F(3)、求解求解 H2022-5-1與與或或引入中間節(jié)點(diǎn)引入中間節(jié)點(diǎn)2022-5-1好處好處：任何一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)要么全是任何一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)要么全是“與節(jié)與節(jié)點(diǎn)點(diǎn)”，要么全是，要么全是“或節(jié)點(diǎn)或節(jié)點(diǎn)”。2022-5-1與或圖的特例與

28、或圖的特例： 所有節(jié)點(diǎn)都是或節(jié)點(diǎn)，這時就是一般的所有節(jié)點(diǎn)都是或節(jié)點(diǎn)，這時就是一般的圖圖，即，即狀態(tài)空間法用到的圖狀態(tài)空間法用到的圖 除了起始節(jié)點(diǎn)外，所有節(jié)點(diǎn)只有一個父節(jié)點(diǎn)，除了起始節(jié)點(diǎn)外，所有節(jié)點(diǎn)只有一個父節(jié)點(diǎn)，此時稱為此時稱為與或樹與或樹，前面的圖，前面的圖2.11就是與或樹就是與或樹 2022-5-1問題歸約法、與或圖表示之間的對應(yīng)關(guān)系問題歸約法、與或圖表示之間的對應(yīng)關(guān)系：問題歸約法問題歸約法原始問題原始問題本原問題本原問題操作符操作符中間問題中間問題與或圖表示與或圖表示起始節(jié)點(diǎn)起始節(jié)點(diǎn)終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)與、或關(guān)系的弧線與、或關(guān)系的弧線非終葉節(jié)點(diǎn)非終葉節(jié)點(diǎn)2022-5-1在與或圖中，問題在與或圖中，問題有解的條件有解的條件是：起始節(jié)點(diǎn)是是：起始節(jié)點(diǎn)是可解可解的的 一般情況下：一般情況下：分解分解 操作符得到操作符得到 與節(jié)點(diǎn)與節(jié)點(diǎn)變換變換 操作符得到操作符得到 或節(jié)點(diǎn)或節(jié)點(diǎn)2022-5-1在