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

1、人 工 智 能 Artificial Intelligence (AI),許建華 南京師范大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 2011年秋季,第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.2.1 問題歸約描述,1、例子：梵塔問題（三個盤）,解決問題的思路： 第一、要將所有盤從第一個柱子搬到第三個柱子，根據(jù)游戲規(guī)則，首先要搬最大的 C 盤到第三個柱子上,解決問題的思路： 第二、要能夠搬 C 盤，條件是：第三個柱子是空的，A、B必須在第二個柱子上（這里沒有考慮如何搬A、B盤）,(a) 初始配置,(b) 目標(biāo)配置,圖2.6 梵塔難題,解決問題的思路： 第三、搬C盤到第三個柱子，然后想辦法將A、B盤搬到第三個柱子上,將問題簡化為下列三個子問題： 移動園盤 A 和 B 到柱子 2 的雙園盤難題 移動 C 盤到柱子 3 的單園盤難題 移動 A 和 B 到柱子 3 的

3、雙園盤難題,圖2.8 梵塔問題的歸約,左到右 表示 盤從大到小，數(shù)字 表示 盤所在柱子號,小盤：13 中盤：12 小盤：32,小盤：21 中盤：23 小盤：13,與,中小盤1到2,中小盤2到3,大盤1到3,2、問題歸約的描述,問題歸約法的基本思路是：應(yīng)用一系列算符將原始問題的描述變換或分解成為子問題的描述 問題的描述可以采用各種數(shù)據(jù)結(jié)構(gòu)，如表、樹、矢量、數(shù)組等,對于梵塔問題，問題及子問題描述： (113)(333),問題歸約法可以用一個三元組（S, O, P）來表示，其中： S：原始問題，即要解決的問題 P：本原問題集，其中的每一個問題是不用證明的或自然成立的，例如公理、已知事實等 O：操作算

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

5、始節(jié)點是可解的,一般情況下： 分解 操作符得到 與節(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é)點含有“與”后繼節(jié)點，那么，只要有一個后繼節(jié)點是不可解的，這一個非終葉節(jié)點就是不可解的。,有一個節(jié)點不可解,不可解,與或圖的解圖：