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

1、人 工 智 能 Artificial Intelligence (AI),許建華 南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 2011年秋季,第2章 知識(shí)表示方法,2.1 狀態(tài)空間法 2.2 問(wèn)題歸約法 2.3 謂詞邏輯法,2.2 問(wèn)題歸約法,例：求積分,解法1：,解法2： 解法3：,問(wèn) 題,解法1,解法2,解法3,解法4,子問(wèn)題1,子問(wèn)題2,子問(wèn)題3,變換,分解,問(wèn)題歸約法： 從已知問(wèn)題的描述出發(fā)，通過(guò)一系列變換或分解將問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合，這些子問(wèn)題的解可以直接得到，從而解決初始問(wèn)題,問(wèn)題歸約法由三個(gè)部分組成： 一個(gè)初始問(wèn)題描述 一套將問(wèn)題變換或分解為子問(wèn)題的操作符 一套本原問(wèn)題（解可以直接得

2、到的簡(jiǎn)單問(wèn)題）描述,2.2.1 問(wèn)題歸約描述,1、例子：梵塔問(wèn)題（三個(gè)盤）,解決問(wèn)題的思路： 第一、要將所有盤從第一個(gè)柱子搬到第三個(gè)柱子，根據(jù)游戲規(guī)則，首先要搬最大的 C 盤到第三個(gè)柱子上,解決問(wèn)題的思路： 第二、要能夠搬 C 盤，條件是：第三個(gè)柱子是空的，A、B必須在第二個(gè)柱子上（這里沒(méi)有考慮如何搬A、B盤）,(a) 初始配置,(b) 目標(biāo)配置,圖2.6 梵塔難題,解決問(wèn)題的思路： 第三、搬C盤到第三個(gè)柱子，然后想辦法將A、B盤搬到第三個(gè)柱子上,將問(wèn)題簡(jiǎn)化為下列三個(gè)子問(wèn)題： 移動(dòng)園盤 A 和 B 到柱子 2 的雙園盤難題 移動(dòng) C 盤到柱子 3 的單園盤難題 移動(dòng) A 和 B 到柱子 3 的

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

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

5、始節(jié)點(diǎn)是可解的,一般情況下： 分解 操作符得到 與節(jié)點(diǎn) 變換 操作符得到 或節(jié)點(diǎn),在與或圖中，一個(gè)可解節(jié)點(diǎn)的定義是（遞歸地）： 1、終葉節(jié)點(diǎn)是可解的（因?yàn)樗鼈兣c本原問(wèn)題相關(guān)聯(lián)的）。一般情況，終葉節(jié)點(diǎn)用 t 來(lái)表示,2、如果某一個(gè)非終葉節(jié)點(diǎn)含有“或”后繼節(jié)點(diǎn)，那么，只要有一個(gè)后繼節(jié)點(diǎn)是可解的，這一個(gè)非終葉節(jié)點(diǎn)就是可解的。,一個(gè)節(jié)點(diǎn)可解,可解,3、如果某一個(gè)非終葉節(jié)點(diǎn)含有“與”后繼節(jié)點(diǎn)，那么，只要所有后繼節(jié)點(diǎn)是可解的，這一個(gè)非終葉節(jié)點(diǎn)才是可解的。,所有節(jié)點(diǎn)可解,可解,與或圖中，一個(gè)不可解節(jié)點(diǎn)的定義（遞歸地）是： 1、沒(méi)有后裔的非終葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)。,2、如果某一個(gè)非終葉節(jié)點(diǎn)含有“或”后繼節(jié)點(diǎn)，那么，只要當(dāng)所有的后繼節(jié)點(diǎn)都不可解時(shí)，這一個(gè)非終葉節(jié)點(diǎn)才是不可解的。,所有節(jié)點(diǎn)不可解,不可解,3、如果某一個(gè)非終葉節(jié)點(diǎn)含有“與”后繼節(jié)點(diǎn)，那么，只要有一個(gè)后繼節(jié)點(diǎn)是不可解的，這一個(gè)非終葉節(jié)點(diǎn)就是不可解的。,有一個(gè)節(jié)點(diǎn)不可解,不可解,與或圖的解圖：