人工智能系統(tǒng)的基本結(jié)構(gòu)專業(yè)課件_第1頁
人工智能系統(tǒng)的基本結(jié)構(gòu)專業(yè)課件_第2頁
人工智能系統(tǒng)的基本結(jié)構(gòu)專業(yè)課件_第3頁
人工智能系統(tǒng)的基本結(jié)構(gòu)專業(yè)課件_第4頁
人工智能系統(tǒng)的基本結(jié)構(gòu)專業(yè)課件_第5頁
已閱讀5頁,還剩30頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、 人工智能系統(tǒng)的基本結(jié)構(gòu)人工智能系統(tǒng)的基本結(jié)構(gòu) 產(chǎn)生式系統(tǒng)(產(chǎn)生式系統(tǒng)(Production SystemProduction System),),也稱作基于規(guī)則的系統(tǒng),是人工智能也稱作基于規(guī)則的系統(tǒng),是人工智能系統(tǒng)中最典型、最普遍的結(jié)構(gòu)。系統(tǒng)中最典型、最普遍的結(jié)構(gòu)。第二章第二章 人工智能系統(tǒng)結(jié)構(gòu)人工智能系統(tǒng)結(jié)構(gòu) 2.1 2.1 產(chǎn)生式系統(tǒng)概述產(chǎn)生式系統(tǒng)概述 2.2 2.2 問題的表示問題的表示 2.3 2.3 控制策略分類控制策略分類 2.4 2.4 產(chǎn)生式系統(tǒng)的類型產(chǎn)生式系統(tǒng)的類型 2.1 2.1 產(chǎn)生式系統(tǒng)概述產(chǎn)生式系統(tǒng)概述 產(chǎn)生式,也稱作規(guī)則,或產(chǎn)生式規(guī)則,用于描述各種產(chǎn)生式,也稱作規(guī)

2、則,或產(chǎn)生式規(guī)則,用于描述各種知識單元間廣泛存在的因果關(guān)系,即前提和結(jié)論之間知識單元間廣泛存在的因果關(guān)系,即前提和結(jié)論之間的關(guān)系。的關(guān)系。 在產(chǎn)生式系統(tǒng)中,待描述系統(tǒng)的知識被分為兩部分:在產(chǎn)生式系統(tǒng)中,待描述系統(tǒng)的知識被分為兩部分: 事實(shí):事實(shí):表示已知事實(shí),如事物、事件及其之間關(guān)系,也可表示已知事實(shí),如事物、事件及其之間關(guān)系,也可以看作是無前提條件的產(chǎn)生式。以看作是無前提條件的產(chǎn)生式。 產(chǎn)生式規(guī)則:產(chǎn)生式規(guī)則:前提和結(jié)論之間的關(guān)系式,表示推理過程和前提和結(jié)論之間的關(guān)系式,表示推理過程和行為。行為。2.1.1 2.1.1 產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu) 三個(gè)基本部分:綜合數(shù)據(jù)庫(事實(shí)

3、庫)、規(guī)則庫(規(guī)則集)、控制三個(gè)基本部分:綜合數(shù)據(jù)庫(事實(shí)庫)、規(guī)則庫(規(guī)則集)、控制器(規(guī)則解釋)。器(規(guī)則解釋)。1 1、綜合數(shù)據(jù)庫是產(chǎn)生式系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu),存儲有關(guān)問題狀綜合數(shù)據(jù)庫是產(chǎn)生式系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu),存儲有關(guān)問題狀態(tài)、性質(zhì)等事實(shí)(敘述型知識),包括推理過程中形成的中間結(jié)態(tài)、性質(zhì)等事實(shí)(敘述型知識),包括推理過程中形成的中間結(jié)論,對應(yīng)問題的表示信息。論,對應(yīng)問題的表示信息。2 2、規(guī)則庫是產(chǎn)生式規(guī)則的集合,存儲有關(guān)問題的狀態(tài)轉(zhuǎn)移、性質(zhì)、規(guī)則庫是產(chǎn)生式規(guī)則的集合,存儲有關(guān)問題的狀態(tài)轉(zhuǎn)移、性質(zhì)變化等規(guī)則(過程型知識),規(guī)則形式變化等規(guī)則(過程型知識),規(guī)則形式: :if if

4、 條件條件 then then 行動行動 if if 前提前提 then then 結(jié)論結(jié)論 如果某規(guī)則的前件能夠被事實(shí)庫中的事實(shí)滿足,則該規(guī)則被激活。如果某規(guī)則的前件能夠被事實(shí)庫中的事實(shí)滿足,則該規(guī)則被激活。3 3、控制器是規(guī)則的解釋程序或執(zhí)行程序,它規(guī)定選擇一條可用規(guī)、控制器是規(guī)則的解釋程序或執(zhí)行程序,它規(guī)定選擇一條可用規(guī)則的原則和規(guī)則使用的方式則的原則和規(guī)則使用的方式 ( (推理方向推理方向) ),并根據(jù)綜合數(shù)據(jù)庫的,并根據(jù)綜合數(shù)據(jù)庫的信息,控制求解問題的過程(控制策略信息,控制求解問題的過程(控制策略, ,推理引擎)。通常從選推理引擎)。通常從選擇規(guī)則到執(zhí)行操作分擇規(guī)則到執(zhí)行操作分三步

5、:三步: 匹配。匹配。 判斷規(guī)則的前件是否成立判斷規(guī)則的前件是否成立? 可能有多條規(guī)則的前件能夠與綜合數(shù)據(jù)庫中的事實(shí)匹配可能有多條規(guī)則的前件能夠與綜合數(shù)據(jù)庫中的事實(shí)匹配! 沖突解決,選擇可調(diào)用的規(guī)則。沖突解決,選擇可調(diào)用的規(guī)則。 從匹配滿足的規(guī)則集中選擇一條規(guī)則。從匹配滿足的規(guī)則集中選擇一條規(guī)則。 執(zhí)行規(guī)則,并在滿足結(jié)束條件時(shí)終止產(chǎn)生式系統(tǒng)的運(yùn)行執(zhí)行規(guī)則,并在滿足結(jié)束條件時(shí)終止產(chǎn)生式系統(tǒng)的運(yùn)行。 如果規(guī)則的后件是結(jié)論,把該結(jié)論加入綜合數(shù)據(jù)庫;如果規(guī)則的后件是結(jié)論,把該結(jié)論加入綜合數(shù)據(jù)庫; 如果規(guī)則的后件是動作,執(zhí)行該動作;如果規(guī)則的后件是動作,執(zhí)行該動作;4 4、產(chǎn)生式系統(tǒng)的特點(diǎn):、產(chǎn)生式系統(tǒng)

6、的特點(diǎn): 數(shù)據(jù)、知識和控制相互獨(dú)立。數(shù)據(jù)、知識和控制相互獨(dú)立。 知識具有相對固定的格式:均由左、右兩部分組成。知識具有相對固定的格式:均由左、右兩部分組成。 知識無序性與模塊化:知識的補(bǔ)充和修改非常容易。知識無序性與模塊化:知識的補(bǔ)充和修改非常容易。 控制系統(tǒng)與問題無關(guān)??刂葡到y(tǒng)與問題無關(guān)。2.1.2 2.1.2 產(chǎn)生式系統(tǒng)的基本過程產(chǎn)生式系統(tǒng)的基本過程 基本算法如下基本算法如下 : 過程過程PRODUCTIONPRODUCTION 1 1DATA DATA 初始數(shù)據(jù)庫初始數(shù)據(jù)庫 2 2Until DATA Until DATA 滿足結(jié)束條件滿足結(jié)束條件( (匹配)之前匹配)之前, do:,

7、do: 3 3從規(guī)則集中選一條可應(yīng)用于從規(guī)則集中選一條可應(yīng)用于DATADATA的規(guī)則的規(guī)則R R(選擇)(選擇) 4 4綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫 R R 應(yīng)用到應(yīng)用到 DATA DATA 得到結(jié)果得到結(jié)果 (執(zhí)行)(執(zhí)行) 上述過程是上述過程是 “匹配、選擇、執(zhí)行匹配、選擇、執(zhí)行”的循環(huán)過程的循環(huán)過程。 2.2 2.2 問題的表示問題的表示 用產(chǎn)生式系統(tǒng)求解問題,就是把一個(gè)問題的描述轉(zhuǎn)化成產(chǎn)生式系統(tǒng)的三個(gè)部用產(chǎn)生式系統(tǒng)求解問題,就是把一個(gè)問題的描述轉(zhuǎn)化成產(chǎn)生式系統(tǒng)的三個(gè)部分。其中問題的表示(即綜合數(shù)據(jù)庫和規(guī)則集的描述)對問題的求解有很大分。其中問題的表示(即綜合數(shù)據(jù)庫和規(guī)則集的描述)對問題的求解有

8、很大的影響。的影響。 狀態(tài)空間法狀態(tài)空間法。所求問題的已知事實(shí)及中間結(jié)論,稱為狀態(tài)。狀態(tài)的集合及。所求問題的已知事實(shí)及中間結(jié)論,稱為狀態(tài)。狀態(tài)的集合及狀態(tài)間的轉(zhuǎn)移規(guī)則構(gòu)成問題的表示?;谶@種表示的問題求解稱為狀態(tài)間的轉(zhuǎn)移規(guī)則構(gòu)成問題的表示。基于這種表示的問題求解稱為狀態(tài)空狀態(tài)空間法間法。求解過程是,通過對可能的狀態(tài)空間的搜索求得一個(gè)解。求解過程是,通過對可能的狀態(tài)空間的搜索求得一個(gè)解。(PRODUCTIONPRODUCTION過程)過程) 問題歸約法問題歸約法。待求問題分解為一些較為簡單的子問題,且子問題也可以分。待求問題分解為一些較為簡單的子問題,且子問題也可以分解,所以可得到若干子問題。包

9、含問題、子問題的集合與問題分解的規(guī)則解,所以可得到若干子問題。包含問題、子問題的集合與問題分解的規(guī)則一起構(gòu)成問題的表示?;谶@種表示的問題求解稱為一起構(gòu)成問題的表示?;谶@種表示的問題求解稱為問題歸約法問題歸約法。求解過。求解過程是,通過對各個(gè)子問題解答的搜索求得原問題的解答。程是,通過對各個(gè)子問題解答的搜索求得原問題的解答。 (SPLITSPLIT過程)過程) 2.2.1 2.2.1 狀態(tài)空間法狀態(tài)空間法狀態(tài)空間可用三元組(狀態(tài)空間可用三元組(S,O,G)來描述)來描述 S是狀態(tài)集合。狀態(tài)是表示某種事實(shí)的符號或數(shù)據(jù)。問題的狀態(tài)可以用任何類型的是狀態(tài)集合。狀態(tài)是表示某種事實(shí)的符號或數(shù)據(jù)。問題的

10、狀態(tài)可以用任何類型的數(shù)據(jù)結(jié)構(gòu)描述。起始狀態(tài)數(shù)據(jù)結(jié)構(gòu)描述。起始狀態(tài)S0是是S的一個(gè)非空子集,描述問題的初始狀態(tài)。的一個(gè)非空子集,描述問題的初始狀態(tài)。 G是目標(biāo)狀態(tài)。是目標(biāo)狀態(tài)。 G是是S的一個(gè)非空子集,它可以是一個(gè)或多個(gè)要達(dá)到的狀態(tài),也可的一個(gè)非空子集,它可以是一個(gè)或多個(gè)要達(dá)到的狀態(tài),也可以是對某些狀態(tài)性質(zhì)的描述。以是對某些狀態(tài)性質(zhì)的描述。 O是規(guī)則集合。集合中的每個(gè)元素稱作操作算子,將一個(gè)狀態(tài)轉(zhuǎn)化為另一個(gè)狀態(tài)。是規(guī)則集合。集合中的每個(gè)元素稱作操作算子,將一個(gè)狀態(tài)轉(zhuǎn)化為另一個(gè)狀態(tài)。問題求解:從問題求解:從S S0 0出發(fā),經(jīng)過一系列操作變換達(dá)到出發(fā),經(jīng)過一系列操作變換達(dá)到G G, 即狀態(tài)空間搜索

11、問題。狀態(tài)空間的一個(gè)解是一個(gè)有限的規(guī)則序列,即狀態(tài)空間搜索問題。狀態(tài)空間的一個(gè)解是一個(gè)有限的規(guī)則序列, 即為狀態(tài)空間的一個(gè)解,解不一定唯一。即為狀態(tài)空間的一個(gè)解,解不一定唯一。GSSSkOOO21021kOO,12.2.2 2.2.2 問題歸約法問題歸約法 問題歸約法也可用一個(gè)三元組(問題歸約法也可用一個(gè)三元組(S0,O,P)來描述)來描述 S0是初始問題,即要求解的問題;是初始問題,即要求解的問題; P是本原問題集,其中的每一個(gè)問題是自然成立的,不需證明的;是本原問題集,其中的每一個(gè)問題是自然成立的,不需證明的; O是操作算子集,一個(gè)操作算子可把一個(gè)問題化成若干個(gè)子問題。是操作算子集,一個(gè)操

12、作算子可把一個(gè)問題化成若干個(gè)子問題。該方法由問題出發(fā),運(yùn)用操作算子產(chǎn)生一些子問題,對子問題再運(yùn)用操該方法由問題出發(fā),運(yùn)用操作算子產(chǎn)生一些子問題,對子問題再運(yùn)用操作算子產(chǎn)生子問題的子問題,一直進(jìn)行到產(chǎn)生的問題均為本原問題,則作算子產(chǎn)生子問題的子問題,一直進(jìn)行到產(chǎn)生的問題均為本原問題,則問題得解。問題歸約的最終目的是產(chǎn)生本原問題。問題得解。問題歸約的最終目的是產(chǎn)生本原問題。問題歸約法是比狀態(tài)空間法更一般的問題求解方法,如果在歸約法中,問題歸約法是比狀態(tài)空間法更一般的問題求解方法,如果在歸約法中,每運(yùn)用一次操作算子,只產(chǎn)生一個(gè)子問題,則就是狀態(tài)空間法。每運(yùn)用一次操作算子,只產(chǎn)生一個(gè)子問題,則就是狀態(tài)

13、空間法。 9、 人的價(jià)值,在招收誘惑的一瞬間被決定。2022-3-62022-3-6Sunday, March 06, 202210、低頭要有勇氣,抬頭要有低氣。2022-3-62022-3-62022-3-63/6/2022 8:06:53 PM11、人總是珍惜為得到。2022-3-62022-3-62022-3-6Mar-226-Mar-2212、人亂于心,不寬余請。2022-3-62022-3-62022-3-6Sunday, March 06, 202213、生氣是拿別人做錯(cuò)的事來懲罰自己。2022-3-62022-3-62022-3-62022-3-63/6/202214、抱最大的希

14、望,作最大的努力。2022年3月6日星期日2022-3-62022-3-62022-3-615、一個(gè)人炫耀什么,說明他內(nèi)心缺少什么。2022年3月2022-3-62022-3-62022-3-63/6/202216、業(yè)余生活要有意義,不要越軌。2022-3-62022-3-6March 6, 202217、一個(gè)人即使已登上頂峰,也仍要自強(qiáng)不息。2022-3-62022-3-62022-3-62022-3-62.2.3 2.2.3 產(chǎn)生式系統(tǒng)舉例產(chǎn)生式系統(tǒng)舉例 圖圖2-1 2-1 八數(shù)碼游戲八數(shù)碼游戲 問題描述:給定一種初始布局(初始狀態(tài))和一個(gè)目標(biāo)的布問題描述:給定一種初始布局(初始狀態(tài))和一

15、個(gè)目標(biāo)的布局(目標(biāo)狀態(tài)),問如何移動將牌,實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)局(目標(biāo)狀態(tài)),問如何移動將牌,實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。狀態(tài)的轉(zhuǎn)變。 一個(gè)合理的走步序列是問題的一個(gè)解。一個(gè)合理的走步序列是問題的一個(gè)解。2834 5716123456789、 人的價(jià)值,在招收誘惑的一瞬間被決定。2022-3-62022-3-6Sunday, March 06, 202210、低頭要有勇氣,抬頭要有低氣。2022-3-62022-3-62022-3-63/6/2022 8:06:54 PM11、人總是珍惜為得到。2022-3-62022-3-62022-3-6Mar-226-Mar-2212、人亂于心,不寬

16、余請。2022-3-62022-3-62022-3-6Sunday, March 06, 202213、生氣是拿別人做錯(cuò)的事來懲罰自己。2022-3-62022-3-62022-3-62022-3-63/6/202214、抱最大的希望,作最大的努力。2022年3月6日星期日2022-3-62022-3-62022-3-615、一個(gè)人炫耀什么,說明他內(nèi)心缺少什么。2022年3月2022-3-62022-3-62022-3-63/6/202216、業(yè)余生活要有意義,不要越軌。2022-3-62022-3-6March 6, 202217、一個(gè)人即使已登上頂峰,也仍要自強(qiáng)不息。2022-3-6202

17、2-3-62022-3-62022-3-6 1 1綜合數(shù)據(jù)庫:選擇一種數(shù)據(jù)結(jié)構(gòu)表示將牌布局。綜合數(shù)據(jù)庫:選擇一種數(shù)據(jù)結(jié)構(gòu)表示將牌布局。 本例選用二維數(shù)組來表示布局較直觀,其數(shù)組元素用本例選用二維數(shù)組來表示布局較直觀,其數(shù)組元素用 表示,其中表示,其中 且互不相等。且互不相等。 這樣每個(gè)具體取值矩陣就代表了一個(gè)棋局狀態(tài)。顯然,這樣每個(gè)具體取值矩陣就代表了一個(gè)棋局狀態(tài)。顯然,該問題有該問題有 個(gè)狀態(tài)。個(gè)狀態(tài)。 ijS8 , 1 , 0, 3,1ijSji362880! 9111213141516171819CCCCCCCCC 2. 2. 規(guī)則集:移動一塊將牌(即走一步)就使?fàn)钜?guī)則集:移動一塊將牌(

18、即走一步)就使?fàn)顟B(tài)發(fā)生一次轉(zhuǎn)變。有四種走法:空格左移、空格態(tài)發(fā)生一次轉(zhuǎn)變。有四種走法:空格左移、空格上移、空格右移、空格下移。上移、空格右移、空格下移。記數(shù)組第記數(shù)組第 i i 行第行第 j j 列的元素為列的元素為 空格所在的行、列分別記為空格所在的行、列分別記為 ,則,則 則空格左移一格、空格上移一格、空格右移一則空格左移一格、空格上移一格、空格右移一格、空格下移一格可用如下格、空格下移一格可用如下4 4條規(guī)則來描述:條規(guī)則來描述:ijS 1i j3,00, ji000jiS 規(guī)則規(guī)則1: 1: (空格左移一格)(空格左移一格) 規(guī)則規(guī)則2: 2: (空格上移一格)(空格上移一格) 規(guī)則規(guī)

19、則3: 3: (空格右移一格)(空格右移一格) 規(guī)則規(guī)則4: 4: (空格下移一格)(空格下移一格) 0 000000i jij1ij1ifj2thenSS S0()(),;0 000000i ji1 ji1 jifi2thenSS S0()(),;0 000000i jij1ij1ifj2thenSS S0()(),;0 000000i ji1 ji1 jifi2thenSS S0()(),; 3.3.控制策略:從規(guī)則集中選擇規(guī)則并作用于狀控制策略:從規(guī)則集中選擇規(guī)則并作用于狀態(tài)的一種廣義選取函數(shù)。態(tài)的一種廣義選取函數(shù)。確定某一策略后,可以用算法的形式給出確定某一策略后,可以用算法的形式給出

20、程序。使用該策略從初始狀態(tài)出發(fā),通過不斷程序。使用該策略從初始狀態(tài)出發(fā),通過不斷尋求滿足一定條件的問題狀態(tài),最后到達(dá)目標(biāo)尋求滿足一定條件的問題狀態(tài),最后到達(dá)目標(biāo)狀態(tài)。狀態(tài)。 2.3 2.3 控制策略分類控制策略分類 對當(dāng)前的狀態(tài),只要某一條規(guī)則作用之后能生成合法的新狀態(tài),對當(dāng)前的狀態(tài),只要某一條規(guī)則作用之后能生成合法的新狀態(tài),那么,這條規(guī)則就是可用規(guī)則。那么,這條規(guī)則就是可用規(guī)則。 產(chǎn)生式系統(tǒng)的運(yùn)行表現(xiàn)出一種搜索過程,在每一個(gè)循環(huán)中選一產(chǎn)生式系統(tǒng)的運(yùn)行表現(xiàn)出一種搜索過程,在每一個(gè)循環(huán)中選一條規(guī)則試用,直到找到某一個(gè)序列能產(chǎn)生滿足結(jié)束條件的狀態(tài)條規(guī)則試用,直到找到某一個(gè)序列能產(chǎn)生滿足結(jié)束條件的狀

21、態(tài)為止。為止。 不同的控制策略產(chǎn)生不同的解,高效率的控制策略能夠走較少不同的控制策略產(chǎn)生不同的解,高效率的控制策略能夠走較少的步驟達(dá)到目標(biāo),但需要問題求解的足夠知識。的步驟達(dá)到目標(biāo),但需要問題求解的足夠知識。 控制策略分為兩類:控制策略分為兩類:不可撤回方式(不可撤回方式(IrrevocableIrrevocable)和試探方)和試探方式(式(TentativeTentative)。1 1)不可撤回方式:)不可撤回方式: 思想思想: : 利用問題給出的局部知識決定如何選取規(guī)則,利用問題給出的局部知識決定如何選取規(guī)則,已用過的規(guī)則不能撤回。優(yōu)點(diǎn)是控制簡單。已用過的規(guī)則不能撤回。優(yōu)點(diǎn)是控制簡單。

22、例:爬山問題。登山過程中,登山人的目標(biāo)是爬上例:爬山問題。登山過程中,登山人的目標(biāo)是爬上峰頂,如何一步一步地向目標(biāo)前進(jìn)就是一個(gè)策略問峰頂,如何一步一步地向目標(biāo)前進(jìn)就是一個(gè)策略問題。通常,人們利用高度隨位置變化的函數(shù)題。通常,人們利用高度隨位置變化的函數(shù)H(P)來來引導(dǎo)爬山,這是一種不可撤回方式。引導(dǎo)爬山,這是一種不可撤回方式。利用利用 H(P)可以計(jì)算朝不同方向邁出一步后高度的可以計(jì)算朝不同方向邁出一步后高度的變化情況。即變化情況。即 向東:向東:z1=H(P0+x)-H(P0) 向西:向西:z2=H( P0 -x)- H(P0) 向北:向北:z3=H( P0+ y)- H(P0) 向南:向南

23、:z4=H( P0 -y)- H(P0) 選擇選擇z變化最大的那一步攀登,到達(dá)新的位置變化最大的那一步攀登,到達(dá)新的位置P;從從P開始重復(fù)這一過程,直到到達(dá)山頂。開始重復(fù)這一過程,直到到達(dá)山頂。圖圖2-2 2-2 爬山過程示意圖爬山過程示意圖 假設(shè)登山人當(dāng)前所處的位置為假設(shè)登山人當(dāng)前所處的位置為P0,如果只有四個(gè)方向可供選,如果只有四個(gè)方向可供選擇擇 :向東(向東(x)、向西()、向西(-x )、向北()、向北(y)、向南()、向南(-y),分別記為規(guī)則,分別記為規(guī)則1、2、3、4。 爬山算法爬山算法1. 1. 開始狀態(tài)作為一個(gè)可能狀態(tài)。開始狀態(tài)作為一個(gè)可能狀態(tài)。2. 2. 從一個(gè)可能狀態(tài),從

24、一個(gè)可能狀態(tài),應(yīng)用可用規(guī)則集生成所有新的可能狀態(tài)集應(yīng)用可用規(guī)則集生成所有新的可能狀態(tài)集。3. 3. 對該狀態(tài)集中每一狀態(tài):對該狀態(tài)集中每一狀態(tài): (1 1)進(jìn)行狀態(tài)測試,檢查其是否為目標(biāo):)進(jìn)行狀態(tài)測試,檢查其是否為目標(biāo): (2 2)如果是目標(biāo)則程序停止。)如果是目標(biāo)則程序停止。 (3 3)如果不是目標(biāo),計(jì)算該狀態(tài)的好壞或者比較各狀態(tài)的好壞。)如果不是目標(biāo),計(jì)算該狀態(tài)的好壞或者比較各狀態(tài)的好壞。4. 4. 取狀態(tài)集中最好狀態(tài),作為下一個(gè)可能狀態(tài)取狀態(tài)集中最好狀態(tài),作為下一個(gè)可能狀態(tài)。5. 5. 回到第回到第2 2步。步。 爬山算法缺點(diǎn):有時(shí)到達(dá)某一狀態(tài)后,盡管它不是目標(biāo)狀態(tài),但在測試過爬山算法

25、缺點(diǎn):有時(shí)到達(dá)某一狀態(tài)后,盡管它不是目標(biāo)狀態(tài),但在測試過中又找不到比該狀態(tài)更好的狀態(tài),如圖中又找不到比該狀態(tài)更好的狀態(tài),如圖2-32-3。 局部極大點(diǎn)(多峰時(shí)處于非主峰):它比周圍鄰居狀態(tài)都好,但不是目標(biāo)。局部極大點(diǎn)(多峰時(shí)處于非主峰):它比周圍鄰居狀態(tài)都好,但不是目標(biāo)。 平頂:它與全部鄰居狀態(tài)都有同一個(gè)值。平頂:它與全部鄰居狀態(tài)都有同一個(gè)值。 山脊:如果搜索方向與山脊的走向不一致,則有可能會停留在山脊處。山脊:如果搜索方向與山脊的走向不一致,則有可能會停留在山脊處。所以,用不可撤回方式來求解登山問題,需要對狀態(tài)測試函數(shù)進(jìn)行選擇:所以,用不可撤回方式來求解登山問題,需要對狀態(tài)測試函數(shù)進(jìn)行選擇:

26、這個(gè)函數(shù)應(yīng)具有單極值,且這個(gè)極值對應(yīng)目標(biāo)狀態(tài)值。這個(gè)函數(shù)應(yīng)具有單極值,且這個(gè)極值對應(yīng)目標(biāo)狀態(tài)值。 圖圖2-3 2-3 爬山法的三種可能狀態(tài)爬山法的三種可能狀態(tài) 測試函數(shù)例:以測試函數(shù)例:以8 8數(shù)碼為例,統(tǒng)計(jì)數(shù)碼為例,統(tǒng)計(jì)“不在位不在位”將牌個(gè)數(shù)將牌個(gè)數(shù)(逐一比(逐一比較當(dāng)前狀態(tài)與目標(biāo)狀態(tài)對應(yīng)位置較當(dāng)前狀態(tài)與目標(biāo)狀態(tài)對應(yīng)位置, ,有差異的將牌總個(gè)數(shù)),并取有差異的將牌總個(gè)數(shù)),并取其負(fù)值作為狀態(tài)描述的函數(shù)其負(fù)值作為狀態(tài)描述的函數(shù). . - W(n) - W(n)(n n為測試狀態(tài))為測試狀態(tài)) 基于該定義,下圖所示狀態(tài)的函數(shù)值為基于該定義,下圖所示狀態(tài)的函數(shù)值為-4-4。顯然,目標(biāo)狀態(tài)的。顯然

27、,目標(biāo)狀態(tài)的函數(shù)值為函數(shù)值為0 0。2 8 31 6 47 51 2 3457 6 81 2 38 47 6 52 8 31 6 47 51W=-42 8 31 47 6 52W=-3上上2 31 8 47 6 53W=-3上上 2 31 8 47 6 54W=-2左左1 2 3 8 47 6 55W=-1下下1 2 38 47 6 56W=0右右2 8 3 1 47 6 53W=-3左左 8 3 2 1 47 6 54W=-3上上8 3 2 1 47 6 55W=-3右右8 1 3 2 47 6 56W=-3下下8 1 3 2 47 6 57W=-3左左 1 3 8 2 47 6 58W=-

28、2上上1 3 8 2 47 6 59W=-1右右1 2 38 47 6 510W=0下下圖圖2-4 2-4 八數(shù)碼問題各狀態(tài)的爬山函數(shù)值八數(shù)碼問題各狀態(tài)的爬山函數(shù)值 爬山法的策略爬山法的策略 執(zhí)行使新狀態(tài)的測試函數(shù)值有最大增長的規(guī)則;執(zhí)行使新狀態(tài)的測試函數(shù)值有最大增長的規(guī)則; 所有規(guī)則都不能使新狀態(tài)的測試函數(shù)值增長時(shí),所有規(guī)則都不能使新狀態(tài)的測試函數(shù)值增長時(shí),執(zhí)行使測試函數(shù)值不減少的規(guī)則;執(zhí)行使測試函數(shù)值不減少的規(guī)則; 如果以上兩種規(guī)則都不存在,則過程停止。如果以上兩種規(guī)則都不存在,則過程停止。2 2)試探方式)試探方式 試探方式分為兩種:試探方式分為兩種:回溯方式和圖搜索方式回溯方式和圖搜索

29、方式。 回溯方式:應(yīng)用規(guī)則后遇到規(guī)定的情況時(shí),返回到最回溯方式:應(yīng)用規(guī)則后遇到規(guī)定的情況時(shí),返回到最近的近的回溯點(diǎn)回溯點(diǎn)(無特殊規(guī)定時(shí),最近的上一狀態(tài)即是回(無特殊規(guī)定時(shí),最近的上一狀態(tài)即是回溯點(diǎn)),從那里改選另外一條可應(yīng)用規(guī)則。溯點(diǎn)),從那里改選另外一條可應(yīng)用規(guī)則。2 2)試探方式)試探方式 對八數(shù)碼問題而言,在對八數(shù)碼問題而言,在3 3種情況下應(yīng)考慮回溯:種情況下應(yīng)考慮回溯: 新生成的狀態(tài)在通向目標(biāo)的路徑上已經(jīng)出現(xiàn)過;新生成的狀態(tài)在通向目標(biāo)的路徑上已經(jīng)出現(xiàn)過; 從初始狀態(tài)開始,在應(yīng)用了指定數(shù)目的規(guī)則后,仍沒有找到從初始狀態(tài)開始,在應(yīng)用了指定數(shù)目的規(guī)則后,仍沒有找到目標(biāo)狀態(tài);目標(biāo)狀態(tài); 對當(dāng)

30、前狀態(tài),再沒有可應(yīng)用規(guī)則。對當(dāng)前狀態(tài),再沒有可應(yīng)用規(guī)則。 假如規(guī)定的搜索深度為假如規(guī)定的搜索深度為6 6層(表現(xiàn)為:應(yīng)用了第層(表現(xiàn)為:應(yīng)用了第6 6條規(guī)則之后得到條規(guī)則之后得到的狀態(tài)仍然不是目標(biāo)狀態(tài)),回溯策略應(yīng)用于八數(shù)碼游戲時(shí)的一的狀態(tài)仍然不是目標(biāo)狀態(tài)),回溯策略應(yīng)用于八數(shù)碼游戲時(shí)的一部分搜索圖如圖部分搜索圖如圖2-52-5所示所示2 8 31 6 47 51 1左、上、右左、上、右同狀態(tài)同狀態(tài)4 4,回溯到上,回溯到上一步,到狀態(tài)一步,到狀態(tài)5 52 22 8 31 6 4 7 5上、右上、右左左2 8 3 6 41 7 53 3上、右、下上、右、下上上 8 32 6 41 7 54 4

31、右、下右、下上上8 32 6 41 7 55 5左、右、下左、右、下右右 8 32 6 41 7 56 6左左同狀態(tài)同狀態(tài)5 5,回溯到,回溯到上一步,到狀態(tài)上一步,到狀態(tài)6 68 32 6 41 7 57 7左左8 3 42 6 1 7 57 7下用了用了6 6條規(guī)則,未找條規(guī)則,未找到解,回溯到上一到解,回溯到上一步,到狀態(tài)步,到狀態(tài) 6 6狀態(tài)狀態(tài)6 6的所有規(guī)則的所有規(guī)則用完,回溯到上一用完,回溯到上一步,到狀態(tài)步,到狀態(tài) 5 58 3 2 6 41 7 56 6左、下左、下右右8 6 3 2 41 7 57 7左左(1 1)(1 1)(2 2)(3 3)8 6 32 41 7 56

32、6左、上、右、下左、上、右、下下下(2 2)圖圖2-5 2-5 利用回溯策略的部分搜索圖利用回溯策略的部分搜索圖 圖搜索方式圖搜索方式: : 對任一狀態(tài),應(yīng)用其所有可應(yīng)用規(guī)則,并把狀態(tài)變對任一狀態(tài),應(yīng)用其所有可應(yīng)用規(guī)則,并把狀態(tài)變化過程用圖結(jié)構(gòu)記錄下來,一直到得到解為止。圖搜索策略求解化過程用圖結(jié)構(gòu)記錄下來,一直到得到解為止。圖搜索策略求解問題是一種窮舉方式。問題是一種窮舉方式。 圖搜索方式下,求得一條解路徑需要搜索問題的整個(gè)求解空間。圖搜索方式下,求得一條解路徑需要搜索問題的整個(gè)求解空間。 對于狀態(tài)空間較大的問題,需要對于狀態(tài)空間較大的問題,需要利用與問題有關(guān)的知識引導(dǎo)規(guī)則的選擇利用與問題有

33、關(guān)的知識引導(dǎo)規(guī)則的選擇,以便在較窄的空間內(nèi)找到問題的解。搜索過程中利用應(yīng)用問題相關(guān)知識對以便在較窄的空間內(nèi)找到問題的解。搜索過程中利用應(yīng)用問題相關(guān)知識對規(guī)則進(jìn)行選擇的搜索,稱為啟發(fā)式圖搜索。規(guī)則進(jìn)行選擇的搜索,稱為啟發(fā)式圖搜索。圖圖2-6 2-6 八數(shù)碼游戲的部分搜索樹八數(shù)碼游戲的部分搜索樹 圖圖2-72-7是是5 5個(gè)城市旅行商問題的地圖,個(gè)城市旅行商問題的地圖, 求從求從A A出發(fā)經(jīng)出發(fā)經(jīng)B B、C C、D D、E E再回到再回到A A的最短的最短路徑。路徑。問題的表示:若每個(gè)城市用一個(gè)字母表問題的表示:若每個(gè)城市用一個(gè)字母表示,則綜合數(shù)據(jù)庫可用字母組成的表或示,則綜合數(shù)據(jù)庫可用字母組成的

34、表或字符串來表示,如(字符串來表示,如(A A)表示初始狀態(tài),)表示初始狀態(tài),(A A* * * * *A A)表示目標(biāo)狀態(tài),()表示目標(biāo)狀態(tài),(A A* * *)表)表示訪問兩個(gè)城市后的當(dāng)前狀態(tài)。示訪問兩個(gè)城市后的當(dāng)前狀態(tài)。啟發(fā)式圖搜索例:啟發(fā)式圖搜索例:問題:旅行商問題。一個(gè)推銷員要到幾個(gè)城市辦理業(yè)務(wù),城市間里程數(shù)已知。問題:旅行商問題。一個(gè)推銷員要到幾個(gè)城市辦理業(yè)務(wù),城市間里程數(shù)已知。求:從某個(gè)城市出發(fā),每個(gè)城市只允許訪問一次,最后回到出發(fā)城市的最短求:從某個(gè)城市出發(fā),每個(gè)城市只允許訪問一次,最后回到出發(fā)城市的最短距離環(huán)路。距離環(huán)路。圖圖2-7 2-7 旅行商問題的地圖旅行商問題的地圖

35、規(guī)則集:規(guī)則集:1 1)下一步走向城市)下一步走向城市A A;2 2)下)下一步走向城市一步走向城市B B;, 5 5)下一步走)下一步走向城市向城市E E;問題的約束:問題的約束: 不可以重復(fù)經(jīng)過同一城市;不可以重復(fù)經(jīng)過同一城市; 在沒有轉(zhuǎn)完所有城市時(shí),不能走向起在沒有轉(zhuǎn)完所有城市時(shí),不能走向起點(diǎn)城市點(diǎn)城市A A。引導(dǎo)策略:每次走向離得最近的城市引導(dǎo)策略:每次走向離得最近的城市。圖圖2-82-8表示求解該問題時(shí),用啟發(fā)式圖表示求解該問題時(shí),用啟發(fā)式圖搜索控制方式生成的搜索樹。搜索控制方式生成的搜索樹。初態(tài)初態(tài)(A)B、C、D、E710613(AB)(AC) B、D、E(AD)(AE)10(A

36、CDEB) A7(ACDEBA) 目標(biāo)目標(biāo)圖圖2-8 2-8 用啟發(fā)式圖搜索生成的搜索樹用啟發(fā)式圖搜索生成的搜索樹5(ACD) B、E(ACB) (ACE) 796(ACDE) BACDB10三種控制方式有不同的特點(diǎn):三種控制方式有不同的特點(diǎn): 不可撤回方式沿著單獨(dú)的一條路徑延伸搜索;不可撤回方式沿著單獨(dú)的一條路徑延伸搜索; 回溯方式保留部分搜索樹結(jié)構(gòu),只記錄當(dāng)前工作的一條回溯方式保留部分搜索樹結(jié)構(gòu),只記錄當(dāng)前工作的一條路徑,回溯操作對當(dāng)前工作路徑進(jìn)行修正;路徑,回溯操作對當(dāng)前工作路徑進(jìn)行修正; 圖搜索方式記錄完整的搜索樹。圖搜索方式記錄完整的搜索樹。2.42.4 正向、逆向、雙向產(chǎn)生式系統(tǒng)正向、逆向、雙向產(chǎn)生式系統(tǒng) 正向產(chǎn)生式

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論