人工智能第2章(知識表示方法2-問題歸約法)

1、人工智能第2章(知識表示方法2-問題歸約法)第2章 知識表示方法2.1 狀態(tài)空間法2.2 問題歸約法2.3 謂詞邏輯法2.2 問題歸約法 例：求積分 解法1：解法2：解法3：問 題解法1解法2解法3解法4子問題1子問題2子問題3變換分解問題歸約法：從已知問題的描述出發(fā)，通過一系列變換或分解將問題最終變?yōu)橐粋€子問題集合，這些子問題的解可以直接得到，從而解決初始問題 問題歸約法由三個部分組成：一個初始問題描述一套將問題變換或分解為子問題的操作符一套本原問題（解可以直接得到的簡單問題）描述2.2.1 問題歸約描述 1、例子：梵塔問題（三個盤） 梵塔難題可采用前一講的狀態(tài)空間法來求解其狀態(tài)空間圖每個節(jié)

2、點代表柱子上圓盤的一種狀態(tài),共含有27個節(jié)點,其節(jié)點(狀態(tài))數(shù)、規(guī)則數(shù)多,求解較復(fù)雜.對梵塔難題而言,問題表述和求解更簡潔的問題歸約法.解決問題的思路：第一、要將所有盤從第一個柱子搬到第三個柱子，根據(jù)游戲規(guī)則，首先要搬最大的 C 盤到第三個柱子上(a) 初始配置(b) 目標配置圖2.7 梵塔難題解決問題的思路：第二、要能夠搬 C 盤，條件是：第三個柱子是空的，A、B必須在第二個柱子上（這里沒有考慮如何搬A、B盤）(a) 初始配置(b) 目標配置圖2.7 梵塔難題解決問題的思路：第三、搬C盤到第三個柱子，然后想辦法將A、B盤搬到第三個柱子上 (a) 初始配置(b) 目標配置圖2.7 梵塔難題將問

3、題簡化為下列三個子問題：移動園盤 A 和 B 到柱子 2 的雙圓盤難題 移動 C 盤到柱子 3 的單圓盤難題移動 A 和 B 到柱子 3 的雙圓盤難題左到右 表示 盤從大到小，數(shù)字 表示 盤所在柱子號 (111)(113) (113)(123) (111)(122) (122)(322) (322)(333) (111)(333) 梵塔問題歸約圖 (123)(122) (322)(321) (331)(333) (321)(331) 本原問題 這種圖式結(jié)構(gòu),叫做與或圖它能有效地說明如何由問題歸約法求得問題的解答 順序解讀與或圖,按問題歸約順序?qū)⑵浔驹瓎栴}及其解組合,即可得到原問題的解.對該梵塔

4、問題,從與或圖讀得的解為如下操作順序: 梵塔問題操作順序 (111)(113) (113)(123) (123)(122) (322)(321) (331)(333) (321)(331) (122)(322) 2、問題歸約的描述 問題歸約法的基本思路是：應(yīng)用一系列算符將原始問題的描述變換或分解成為子問題的描述問題的描述可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹、矢量、數(shù)組等對于梵塔問題，問題及子問題描述： (111)(333)問題歸約法可以用一個三元組（S, O, P）來表示，其中： S：原始問題，即要解決的問題 P：本原問題集，其中的每一個問題是不用證明的或自然成立的，例如公理、已知事實等 O：操作算

5、子集，用于將問題化為子問題2.2.2 與或圖表示 例：有一個問題A，它可以通過三種途徑來求解：1、求解問題 B 和 C2、求解問題 D 、E 和 F3、求解 H與或引入中間節(jié)點好處：任何一個節(jié)點的后繼節(jié)點要么全是“與節(jié)點”，要么全是“或節(jié)點”。與或與或圖的特例：所有節(jié)點都是或節(jié)點，這時就是一般的圖，即狀態(tài)空間法用到的圖除了起始節(jié)點外，所有節(jié)點只有一個父節(jié)點，此時稱為與或樹，前面的圖2.11就是與或樹 問題歸約法、與或圖表示之間的對應(yīng)關(guān)系：問題歸約法原始問題本原問題操作符中間問題與或圖表示起始節(jié)點終葉節(jié)點與、或關(guān)系的弧線非終葉節(jié)點在與或圖中，問題有解的條件是：起始節(jié)點是可解的 一般情況下：分解

6、操作符得到 與節(jié)點變換 操作符得到 或節(jié)點在與或圖中，一個可解節(jié)點的定義是（遞歸地）：1、終葉節(jié)點是可解的（因為它們與本原問題相關(guān)聯(lián)的）。一般情況，終葉節(jié)點用 t 來表示2、如果某一個非終葉節(jié)點含有“或”后繼節(jié)點，那么，只要有一個后繼節(jié)點是可解的，這一個非終葉節(jié)點就是可解的。一個節(jié)點可解可解3、如果某一個非終葉節(jié)點含有“與”后繼節(jié)點，那么，只要所有后繼節(jié)點是可解的，這一個非終葉節(jié)點才是可解的。所有節(jié)點可解可解與或圖中，一個不可解節(jié)點的定義（遞歸地）是：1、沒有后裔的非終葉節(jié)點是不可解節(jié)點。2、如果某一個非終葉節(jié)點含有“或”后繼節(jié)點，那么，只要當(dāng)所有的后繼節(jié)點都不可解時，這一個非終葉節(jié)點才是不可解的。所有節(jié)點不可解不可解3、如果某一個非終葉節(jié)點含有“與”后繼