問(wèn)題歸約法(共9頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上教案名稱知識(shí)表示方法-問(wèn)題歸約法科目教學(xué)對(duì)象主講人課時(shí)一、教學(xué)目標(biāo)1. 通過(guò)梵塔難題重點(diǎn)掌握問(wèn)題歸約法的機(jī)理和問(wèn)題歸約描述方法2.學(xué)會(huì)用與或圖表示歸約問(wèn)題。二、教學(xué)流程（教學(xué)策略選擇與設(shè)計(jì)）一、引言 通過(guò)一個(gè)狀態(tài)空間法的例子，看出狀態(tài)空間法的局限性，從而引出問(wèn)題歸約法。 二、問(wèn)題歸約描述由上述說(shuō)明，給出一個(gè)具體的梵塔問(wèn)題。通過(guò)同學(xué)之間談?wù)撍伎己?，給出一個(gè)利用問(wèn)題歸約法的解題步驟，從而引出問(wèn)題歸約法的一些概念。再給出問(wèn)題歸約法的標(biāo)準(zhǔn)定義和具體細(xì)節(jié)。3、 與或圖表示 由上述梵塔問(wèn)題的解題過(guò)程初步了解了與或圖表示，本節(jié)通過(guò)一個(gè)具體的例子給出了與或圖表示的概念，同時(shí)思考問(wèn)題歸

2、約法、與或圖表示之間的對(duì)應(yīng)關(guān)系，并給出其的對(duì)應(yīng)關(guān)系。給出節(jié)點(diǎn)可解和不可解的定義，進(jìn)一步了解與或圖表示。給出例子讓同學(xué)們判斷節(jié)點(diǎn)是否可解?？偨Y(jié)問(wèn)題歸約法和與或圖表示，給出幾道題，讓同學(xué)們思考并解題，進(jìn)一步了解問(wèn)題歸約法和與或圖表示，并熟練掌握。4、 問(wèn)題歸約機(jī)理 以上內(nèi)容我們了解并學(xué)習(xí)了問(wèn)題歸約法和與或圖表示，為了進(jìn)一步了解其內(nèi)容。我們通過(guò)兩篇論文來(lái)討論分析。上節(jié)課老師給我們講了知識(shí)表示方法中的狀態(tài)空間法，本節(jié)課開(kāi)始我們先通過(guò)二階梵塔問(wèn)題再來(lái)復(fù)習(xí)一下?tīng)顟B(tài)空間法。教學(xué)過(guò)程（引言）教學(xué)過(guò)程（問(wèn)題歸約描述）通過(guò)介紹“梵塔難題”(Tower-of-Hanoi Puzzle)及其求解來(lái)討論問(wèn)題歸約描述,梵

3、塔難題為了說(shuō)明如何用問(wèn)題歸約法求解問(wèn)題,下面考慮著名的AI問(wèn)題-“梵塔難題”(Tower-of-Hanoi Puzzle),其提法如下:1>有3個(gè)柱子(1,2和3)和3個(gè)不同尺寸的圓盤(A,B和C).圓盤的中心有個(gè)孔,圓盤可以堆疊在柱子上.2>最初,全部3個(gè)圓盤都堆在柱子1上;最大的圓盤C在底部,最小的圓盤A在頂部。3>現(xiàn)要求把所有圓盤都移到柱子3上,每次只許移動(dòng)一個(gè),而且圓盤只能從上到下移動(dòng),且堆放只能從小到大.梵塔難題的初始配置和目標(biāo)配置如圖1所示. 思考此問(wèn)題，并由此問(wèn)題了解梵塔難題和問(wèn)題規(guī)約法（同學(xué)討論）（5分鐘）給出具體解： 梵塔難題可采用前一講的狀態(tài)空間法來(lái)求解.

4、 其狀態(tài)空間圖每個(gè)節(jié)點(diǎn)代表柱子上圓盤的一種狀態(tài),共含有27個(gè)節(jié)點(diǎn),其節(jié)點(diǎn)(狀態(tài))數(shù)、規(guī)則數(shù)多,求解較復(fù)雜. 本講討論對(duì)梵塔難題而言,問(wèn)題表述和求解更簡(jiǎn)潔的問(wèn)題歸約法. 狀態(tài)空間描述： 三個(gè)盤子的位置列表(a, b, c) a=1,2,3; b=1,2,3; c=1,2,3 初始狀態(tài)：S = (1, 1, 1) 目標(biāo)狀態(tài)：G = (3, 3, 3)算符集合：Move (x, i, j)： x = A,B,C; i= 1,2,3; j= 1,2,3上述論證允許把原始問(wèn)題歸約(簡(jiǎn)化)為下列3個(gè)子問(wèn)題;1. 移動(dòng)圓盤A和B至柱子2的雙圓盤問(wèn)題,如圖2(a)所示. 圖2(a) 移動(dòng)圓盤A和B至柱子22.

5、 移動(dòng)圓盤C至柱子3的單圓盤問(wèn)題,如圖2(b)所示. 圖2(b) 移動(dòng)圓盤C至柱子33. 移動(dòng)圓盤A和B至柱子3的雙圓盤問(wèn)題,如圖2(c)所示. 圖2(C) 移動(dòng)圓盤A和B至柱子3問(wèn)題歸約 雙圓盤問(wèn)題 : (111) (122) 單圓盤問(wèn)題 : (122) (322） 本原 雙圓盤問(wèn)題 : (322) (333）由于3個(gè)簡(jiǎn)化了的問(wèn)題都較小,都比原始問(wèn)題容易解決.子問(wèn)題2為本原問(wèn)題,因?yàn)樗慕庵话徊揭苿?dòng).應(yīng)用一系列相似的推理,子問(wèn)題1和子問(wèn)題3也可被歸約為本原問(wèn)題,如圖3a所示問(wèn)題歸約描述 由以上例子，我們給出了問(wèn)題歸約法的一些概念。（1） 問(wèn)題規(guī)約法的基本概念問(wèn)題規(guī)約是人類處理或求解大問(wèn)題

6、或復(fù)雜問(wèn)題的一種常用的方式。人們常常將大的問(wèn)題或復(fù)雜的問(wèn)題分解為一系列小的或簡(jiǎn)單的問(wèn)題，然后，分別加以處理或求解。一個(gè)大的問(wèn)題常常是由一些小的問(wèn)題構(gòu)成的，一個(gè)復(fù)雜的問(wèn)題常常是由一些簡(jiǎn)單問(wèn)題構(gòu)成的。這些小的問(wèn)題或簡(jiǎn)單的問(wèn)題就是大問(wèn)題或復(fù)雜問(wèn)題的子問(wèn)題。問(wèn)題規(guī)約方法模擬人類處理大問(wèn)題或復(fù)雜問(wèn)題的智能行為，將大問(wèn)題或復(fù)雜問(wèn)題分解為較小或較簡(jiǎn)單的問(wèn)題，將較小或較簡(jiǎn)單的問(wèn)題再分解為更小或更簡(jiǎn)單的問(wèn)題，直至所有的問(wèn)題都易于處理或求解為止。問(wèn)題規(guī)約法：從已知問(wèn)題的描述出發(fā)，通過(guò)一系列變換或分解將問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合，這些子問(wèn)題的解可以直接得到，從而解決初始問(wèn)題。問(wèn)題規(guī)約法的實(shí)質(zhì)：從目標(biāo)（要解決的問(wèn)題）

7、出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。最小的問(wèn)題或具有明顯解答的問(wèn)題被稱為本原問(wèn)題。例如，對(duì)于不定積分問(wèn)題，ò dx 就是一個(gè)本原問(wèn)題，其答案是顯而易見(jiàn)的，即 dx=x。一般地，本原問(wèn)題是原始問(wèn)題的子孫問(wèn)題。因此，問(wèn)題規(guī)約的過(guò)程就是在問(wèn)題空間中不斷搜索問(wèn)題的子問(wèn)題和子問(wèn)題的子問(wèn)題的過(guò)程，直至將原始問(wèn)題分解為本原問(wèn)題集合。本原問(wèn)題的解可以直接得到或通過(guò)一個(gè)"黑箱"操作得到。（2）問(wèn)題歸約表示可由下列3部分組成: 一個(gè)初始問(wèn)題描述; 將問(wèn)題變換為子問(wèn)題的操作集; 一系列本原問(wèn)題描述.問(wèn)題的歸約描述 初始問(wèn)題集合：初

8、始狀態(tài)集合 S 算符集合：將問(wèn)題分解為若干子問(wèn)題的變換集合F 本原問(wèn)題集合：目標(biāo)狀態(tài)集合G 三元組合：（S , F, G）（3）問(wèn)題規(guī)約法與狀態(tài)空間法 問(wèn)題歸約與前面狀態(tài)空間描述不同的是,主要其在問(wèn)題空間中展開(kāi)對(duì)問(wèn)題的描述和求解。 狀態(tài)空間法只是研究對(duì)問(wèn)題所陳述的事實(shí)狀態(tài)如何表示,以及如何搜索狀態(tài)空間求解;而問(wèn)題歸約法則是對(duì)問(wèn)題求解中如何將問(wèn)題逐步分解為一系列子問(wèn)題本原問(wèn)題的集合。 對(duì)實(shí)際問(wèn)題求解,可將這兩種方法有機(jī)結(jié)合,如后面討論到的與或圖表示與搜索。1 與或圖的概念用一個(gè)類似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，畫(huà)出歸約問(wèn)題圖。例：有一個(gè)問(wèn)題A，它可以通過(guò)三種途徑來(lái)求解： （1）、

9、求解問(wèn)題B和C （2）、求解問(wèn)題D、E和F （3）、求解問(wèn)題H這一問(wèn)題歸約為子問(wèn)題的替換集合關(guān)系可由圖4所示的結(jié)構(gòu)來(lái)表示.圖中各節(jié)點(diǎn)由它們所表示的問(wèn)題來(lái)標(biāo)記從該圖可讀得:問(wèn)題B和C構(gòu)成子問(wèn)題的一個(gè)集合;D、E和F構(gòu)成另一子問(wèn)題集合;而H則為第3個(gè)集合.對(duì)應(yīng)于某個(gè)給定集合的各節(jié)點(diǎn),用連接弧線的標(biāo)記來(lái)指明. 為了不出現(xiàn)既有與子節(jié)點(diǎn)又有或子節(jié)點(diǎn)的節(jié)點(diǎn),使得狀態(tài)圖更規(guī)范,更容易被計(jì)算機(jī)所存儲(chǔ)與處理,通常把某些附加節(jié)點(diǎn)引入此結(jié)構(gòu)圖.這樣便使含有一個(gè)以上子問(wèn)題的每個(gè)集合能夠聚集在它們各自的父節(jié)點(diǎn)之下.根據(jù)這一約定,圖4的結(jié)構(gòu)變?yōu)閳D5所示的結(jié)構(gòu). 其中,標(biāo)記為N和M的附加節(jié)點(diǎn)分別作為集合B,C和D,E,F的

10、唯一父節(jié)點(diǎn),具有輔助問(wèn)題描述的作用.對(duì)于圖5,問(wèn)題A被歸約為單一替換子問(wèn)題N、M和H.因此,把節(jié)點(diǎn)N、M和H叫做或節(jié)點(diǎn).然而,N被歸約為子問(wèn)題B和C的單一集合,要求解N就必須求解所有的子問(wèn)題.因此,把節(jié)點(diǎn)B和C叫做與節(jié)點(diǎn).定義： 父節(jié)點(diǎn)是一個(gè)初始問(wèn)題或是可分解為子問(wèn)題的問(wèn)題節(jié)點(diǎn)； 子節(jié)點(diǎn)是一個(gè)初始問(wèn)題或是子問(wèn)題分解的子問(wèn)題的節(jié)點(diǎn)； 或節(jié)點(diǎn)只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合； 與節(jié)點(diǎn)只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合； 弧線是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線； 終葉節(jié)點(diǎn)是對(duì)應(yīng)于本原問(wèn)題的本原節(jié)點(diǎn)。2 問(wèn)題歸約法、與或圖表示之間的對(duì)應(yīng)關(guān)系： 問(wèn)題歸約法 與或圖表示 原始問(wèn)題 起

11、始問(wèn)題 本原問(wèn)題 終葉節(jié)點(diǎn) 操作符 與、或關(guān)系的弧線 中間問(wèn)題 非終葉節(jié)點(diǎn)3 節(jié)點(diǎn)可解性和不可解性的定義在與或圖上執(zhí)行的搜索過(guò)程,其目的在于表明初始節(jié)點(diǎn)是有解的.下面給出可解節(jié)點(diǎn)的定義.定義1 與或圖中可解節(jié)點(diǎn)可以歸納定義如下:終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連).如果某個(gè)非終葉節(jié)點(diǎn)含有或子節(jié)點(diǎn),那么只有當(dāng)其子節(jié)點(diǎn)至少有一個(gè)是可解的時(shí),此非終葉節(jié)點(diǎn)才是可解的.如果某個(gè)非終葉節(jié)點(diǎn)含有與子節(jié)點(diǎn),那么只要當(dāng)其子節(jié)點(diǎn)全部為可解時(shí),此非終葉節(jié)點(diǎn)才是可解的.于是,一個(gè)解圖被定義為那些可解節(jié)點(diǎn)的子圖,這些節(jié)點(diǎn)能夠(按上述定義)證明其初始節(jié)點(diǎn)是可解的.定義2 與或圖中不可解節(jié)點(diǎn)的歸納定義于下:沒(méi)有子節(jié)點(diǎn)的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn).如果某個(gè)非終葉節(jié)點(diǎn)含有或子節(jié)點(diǎn),那么只有當(dāng)其全部子為不可解時(shí),此非終葉節(jié)點(diǎn)才是不可解的.如果某個(gè)非終葉節(jié)點(diǎn)含有與子節(jié)點(diǎn),那么只要當(dāng)其子節(jié)點(diǎn)至少有一個(gè)為不可解時(shí),此非終葉節(jié)點(diǎn)才是不可解的.圖6給出與或圖的一些例子.圖中,終葉節(jié)點(diǎn)用字母t標(biāo)示,有解節(jié)點(diǎn)用小圓點(diǎn)表示,而解圖用綠線分支表示.不可