人工智能第2章(知識(shí)表示方法2問(wèn)題歸約法)

1、人人 工工 智智 能能Artificial Intelligence (AI)第第2章章 知識(shí)表示方法知識(shí)表示方法2.1 狀態(tài)空間法狀態(tài)空間法2.2 問(wèn)題歸約法問(wèn)題歸約法2.3 謂詞邏輯法謂詞邏輯法2.2 問(wèn)題歸約法問(wèn)題歸約法 例：求積分例：求積分 解法解法1：解法解法2：解法解法3：2(cos)xexxdx223(cos)cossin3xxxexxdxe dxxdxx dxxex問(wèn)問(wèn) 題題解法解法1解法解法2解法解法3解法解法4子子問(wèn)題問(wèn)題1子子問(wèn)題問(wèn)題2子子問(wèn)題問(wèn)題3變換變換分解分解問(wèn)題歸約法問(wèn)題歸約法：從已知問(wèn)題的描述出發(fā)，通過(guò)一系列從已知問(wèn)題的描述出發(fā)，通過(guò)一系列變換變換或或分解分解將

2、問(wèn)題最終變?yōu)橐粋€(gè)將問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合子問(wèn)題集合，這些子問(wèn)題的，這些子問(wèn)題的解可以直接得到，從而解決初始問(wèn)題解可以直接得到，從而解決初始問(wèn)題 問(wèn)題歸約法由三個(gè)部分組成問(wèn)題歸約法由三個(gè)部分組成： 一個(gè)初始問(wèn)題描述一個(gè)初始問(wèn)題描述 一套將問(wèn)題變換或分解為子問(wèn)題的操作符一套將問(wèn)題變換或分解為子問(wèn)題的操作符 一套本原問(wèn)題（一套本原問(wèn)題（解可以直接得到的簡(jiǎn)單問(wèn)題解可以直接得到的簡(jiǎn)單問(wèn)題）描述描述2.2.1 問(wèn)題歸約描述問(wèn)題歸約描述 1 1、例子：、例子：梵塔問(wèn)題梵塔問(wèn)題（三個(gè)盤）（三個(gè)盤） 梵塔難題可采用前一講的狀態(tài)空間法來(lái)求解梵塔難題可采用前一講的狀態(tài)空間法來(lái)求解 其狀態(tài)空間圖每個(gè)節(jié)點(diǎn)代表柱子上

3、圓盤的一種其狀態(tài)空間圖每個(gè)節(jié)點(diǎn)代表柱子上圓盤的一種狀態(tài)狀態(tài),共含有共含有27個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn),其節(jié)點(diǎn)其節(jié)點(diǎn)(狀態(tài)狀態(tài))數(shù)、規(guī)則數(shù)數(shù)、規(guī)則數(shù)多多,求解較復(fù)雜求解較復(fù)雜. 對(duì)梵塔難題而言對(duì)梵塔難題而言,問(wèn)題表述和求解更簡(jiǎn)潔的問(wèn)問(wèn)題表述和求解更簡(jiǎn)潔的問(wèn)題歸約法題歸約法.解決問(wèn)題的思路解決問(wèn)題的思路：第一第一、要將所有盤從第一個(gè)柱子搬到第三個(gè)、要將所有盤從第一個(gè)柱子搬到第三個(gè)柱子，根據(jù)游戲規(guī)則，首先要搬最大的柱子，根據(jù)游戲規(guī)則，首先要搬最大的 C 盤盤到第三個(gè)柱子上到第三個(gè)柱子上(a) 初始配置初始配置(b) 目標(biāo)配置目標(biāo)配置圖圖2.7 梵塔難題梵塔難題解決問(wèn)題的思路解決問(wèn)題的思路：第二第二、要能夠搬、要

4、能夠搬 C 盤，條件是：第三個(gè)柱盤，條件是：第三個(gè)柱子是空的，子是空的，A、B必須在第二個(gè)柱子上（這必須在第二個(gè)柱子上（這里沒(méi)有考慮如何搬里沒(méi)有考慮如何搬A、B盤）盤）(a) 初始配置初始配置(b) 目標(biāo)配置目標(biāo)配置圖圖2.7 梵塔難題梵塔難題解決問(wèn)題的思路解決問(wèn)題的思路：第三第三、搬、搬C盤到第三個(gè)柱子，然后想辦法將盤到第三個(gè)柱子，然后想辦法將A、B盤搬到第三個(gè)柱子上盤搬到第三個(gè)柱子上 (a) 初始配置初始配置(b) 目標(biāo)配置目標(biāo)配置圖圖2.7 梵塔難題梵塔難題將問(wèn)題簡(jiǎn)化為下列三個(gè)子問(wèn)題將問(wèn)題簡(jiǎn)化為下列三個(gè)子問(wèn)題：1. 移動(dòng)園盤移動(dòng)園盤 A 和和 B 到柱子到柱子 2 的雙圓盤難題的雙圓盤難

5、題2.2. 移動(dòng)移動(dòng) C C 盤到柱子盤到柱子 3 3 的單圓盤難題的單圓盤難題3. 移動(dòng)移動(dòng) A 和和 B 到柱子到柱子 3 的雙圓盤難題的雙圓盤難題左到右左到右 表示表示 盤盤從大到從大到小，小，數(shù)字?jǐn)?shù)字 表示表示 盤所在柱子號(hào)盤所在柱子號(hào) (111)(113 ) (113)(123) (111)(122) (122)(322) (322)(333) (111)(333) 梵塔問(wèn)題歸約圖梵塔問(wèn)題歸約圖 (123)(122) (322)(321) (331)(333) (321)(331) 本原問(wèn)題本原問(wèn)題 這種圖式結(jié)構(gòu)這種圖式結(jié)構(gòu),叫做叫做與或圖與或圖它能有效地說(shuō)明如何由問(wèn)題歸約法求得問(wèn)題

6、的解答它能有效地說(shuō)明如何由問(wèn)題歸約法求得問(wèn)題的解答 順序解讀與或圖順序解讀與或圖,按問(wèn)題歸約順序?qū)⑵浔驹瓎?wèn)題及其解按問(wèn)題歸約順序?qū)⑵浔驹瓎?wèn)題及其解組合組合,即可得到原問(wèn)題的解即可得到原問(wèn)題的解.對(duì)該梵塔問(wèn)題對(duì)該梵塔問(wèn)題,從與或圖讀得的解為如下操作順序從與或圖讀得的解為如下操作順序: 梵塔問(wèn)題操作順序梵塔問(wèn)題操作順序 (111)(113 ) (113)(123) (123)(122) (322)(321) (331)(333) (321)(331) (122)(322) 2、問(wèn)題歸約的描述問(wèn)題歸約的描述 問(wèn)題歸約法的問(wèn)題歸約法的基本思路基本思路是：應(yīng)用一系列算符將原是：應(yīng)用一系列算符將原始問(wèn)題的

7、描述始問(wèn)題的描述變換或分解變換或分解成為子問(wèn)題的描述成為子問(wèn)題的描述問(wèn)題的描述問(wèn)題的描述可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹(shù)、可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹(shù)、矢量、數(shù)組等矢量、數(shù)組等對(duì)于梵塔問(wèn)題，問(wèn)題及子問(wèn)題描述：對(duì)于梵塔問(wèn)題，問(wèn)題及子問(wèn)題描述： (111)(333)問(wèn)題歸約法可以用一個(gè)三元組（問(wèn)題歸約法可以用一個(gè)三元組（S, O, P）來(lái)表示，來(lái)表示，其中：其中： S：原始問(wèn)題，即要解決的問(wèn)題原始問(wèn)題，即要解決的問(wèn)題 P：本原問(wèn)題集，其中的每一個(gè)問(wèn)題是不用證本原問(wèn)題集，其中的每一個(gè)問(wèn)題是不用證明的或自然成立的，例如公理、已知事實(shí)等明的或自然成立的，例如公理、已知事實(shí)等 O：操作算子集，用于將問(wèn)題化

8、為子問(wèn)題操作算子集，用于將問(wèn)題化為子問(wèn)題2.2.2 與或圖表示與或圖表示 例例：有一個(gè)問(wèn)題：有一個(gè)問(wèn)題A，它可以通過(guò)三種途徑來(lái)求解：它可以通過(guò)三種途徑來(lái)求解：1、求解問(wèn)題、求解問(wèn)題 B 和和 C2、求解問(wèn)題求解問(wèn)題 D 、E 和和 F3、求解求解 H與與或或引入中間節(jié)點(diǎn)引入中間節(jié)點(diǎn)好處好處：任何一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)要么全是任何一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)要么全是“與節(jié)與節(jié)點(diǎn)點(diǎn)”，要么全是，要么全是“或節(jié)點(diǎn)或節(jié)點(diǎn)”。與與或或與或圖的特例與或圖的特例： 所有節(jié)點(diǎn)都是或節(jié)點(diǎn)，這時(shí)就是一般的所有節(jié)點(diǎn)都是或節(jié)點(diǎn)，這時(shí)就是一般的圖圖，即，即狀態(tài)空間法用到的圖狀態(tài)空間法用到的圖 除了起始節(jié)點(diǎn)外，所有節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，

9、除了起始節(jié)點(diǎn)外，所有節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，此時(shí)稱為此時(shí)稱為與或樹(shù)與或樹(shù)，前面的圖，前面的圖2.11就是與或樹(shù)就是與或樹(shù) 問(wèn)題歸約法、與或圖表示之間的對(duì)應(yīng)關(guān)系問(wèn)題歸約法、與或圖表示之間的對(duì)應(yīng)關(guān)系：?jiǎn)栴}歸約法問(wèn)題歸約法原始問(wèn)題原始問(wèn)題本原問(wèn)題本原問(wèn)題操作符操作符中間問(wèn)題中間問(wèn)題與或圖表示與或圖表示起始節(jié)點(diǎn)起始節(jié)點(diǎn)終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)與、或關(guān)系的弧線與、或關(guān)系的弧線非終葉節(jié)點(diǎn)非終葉節(jié)點(diǎn)在與或圖中，問(wèn)題在與或圖中，問(wèn)題有解的條件有解的條件是：起始節(jié)點(diǎn)是是：起始節(jié)點(diǎn)是可解可解的的 一般情況下：一般情況下：分解分解 操作符得到操作符得到 與節(jié)點(diǎn)與節(jié)點(diǎn)變換變換 操作符得到操作符得到 或節(jié)點(diǎn)或節(jié)點(diǎn)在與或圖中，一個(gè)在

10、與或圖中，一個(gè)可解節(jié)點(diǎn)的定義可解節(jié)點(diǎn)的定義是（遞歸地）：是（遞歸地）：1、終葉節(jié)點(diǎn)是可解的（因?yàn)樗鼈兣c本原問(wèn)題相關(guān)聯(lián)、終葉節(jié)點(diǎn)是可解的（因?yàn)樗鼈兣c本原問(wèn)題相關(guān)聯(lián)的）。一般情況，終葉節(jié)點(diǎn)用的）。一般情況，終葉節(jié)點(diǎn)用 t 來(lái)表示來(lái)表示2、如果某一個(gè)非終葉節(jié)點(diǎn)含有、如果某一個(gè)非終葉節(jié)點(diǎn)含有“或或”后繼節(jié)點(diǎn)，那后繼節(jié)點(diǎn)，那么，只要有一個(gè)后繼節(jié)點(diǎn)是可解的，這一個(gè)非終么，只要有一個(gè)后繼節(jié)點(diǎn)是可解的，這一個(gè)非終葉節(jié)點(diǎn)就是可解的。葉節(jié)點(diǎn)就是可解的。一個(gè)節(jié)點(diǎn)可解一個(gè)節(jié)點(diǎn)可解可解可解3、如果某一個(gè)非終葉節(jié)點(diǎn)含有、如果某一個(gè)非終葉節(jié)點(diǎn)含有“與與”后繼節(jié)點(diǎn)，后繼節(jié)點(diǎn)，那么，只要所有后繼節(jié)點(diǎn)是可解的，這一個(gè)那么，只要所

11、有后繼節(jié)點(diǎn)是可解的，這一個(gè)非終葉節(jié)點(diǎn)才是可解的非終葉節(jié)點(diǎn)才是可解的。所有節(jié)點(diǎn)可解所有節(jié)點(diǎn)可解可解可解與或圖中，一個(gè)與或圖中，一個(gè)不可解節(jié)點(diǎn)的定義不可解節(jié)點(diǎn)的定義（遞歸地）是：（遞歸地）是：1、沒(méi)有后裔的非終葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)。、沒(méi)有后裔的非終葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)。2、如果某一個(gè)非終葉節(jié)點(diǎn)含有、如果某一個(gè)非終葉節(jié)點(diǎn)含有“或或”后繼節(jié)點(diǎn)，后繼節(jié)點(diǎn)，那么，只要當(dāng)所有的后繼節(jié)點(diǎn)都不可解時(shí)，這那么，只要當(dāng)所有的后繼節(jié)點(diǎn)都不可解時(shí)，這一個(gè)非終葉節(jié)點(diǎn)才是不可解的。一個(gè)非終葉節(jié)點(diǎn)才是不可解的。所有節(jié)點(diǎn)不可解所有節(jié)點(diǎn)不可解不可解不可解3、如果某一個(gè)非終葉節(jié)點(diǎn)含有、如果某一個(gè)非終葉節(jié)點(diǎn)含有“與與”后繼節(jié)點(diǎn)，后繼節(jié)點(diǎn)，那么，只要有一個(gè)后繼