【文章內(nèi)容簡(jiǎn)介】 有生命 吃飼料 能吃食物 有繁殖能力 能運(yùn)動(dòng) 個(gè)頭大 吃肉 個(gè)頭小 跑得慢 不咬人 供觀賞 框架表示 ? 1974年，由 Minsky在“ A framework for representing knowledge”中提出。 ?框架是一種描述所論對(duì)象屬性的數(shù)據(jù)結(jié)構(gòu)。所論對(duì)象可以是一個(gè)事物、一個(gè)事件或者一個(gè)概念。一個(gè)框架由若干個(gè)“槽”組成，每個(gè)“槽”又可劃分為若干個(gè)“側(cè)面”。一個(gè)槽用于描述所論及對(duì)象的某一方面的屬性，一個(gè)側(cè)面用于描述相應(yīng)屬性的一個(gè)方面。槽和側(cè)面所具有的屬性值分別稱為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可以是程序、條件、默認(rèn)值或是一個(gè)子框架。 框架表示 ?用框架表示法表示知識(shí)的步驟如下： （ 1）分析待表達(dá)知識(shí)中的對(duì)象及其屬性，對(duì)框架中的槽進(jìn)行合理設(shè)置。 （ 2）對(duì)各對(duì)象間的各種聯(lián)系進(jìn)行考察。使用一些常用的名稱或根據(jù)具體需要定義一些表達(dá)聯(lián)系的槽名，來(lái)描述上、下層框架間的聯(lián)系。 （ 3）對(duì)各層對(duì)象的“槽”及“側(cè)面”進(jìn)行合理的組織安排，避免信息描述的重復(fù)。 例：用框架表示下述報(bào)道的地震事件 【 虛擬新華社 3月 15日電 】 昨日 ， 在 云南玉溪地區(qū)發(fā)生 地震 ， 造成 財(cái)產(chǎn)損失約 10萬(wàn)元 ， 統(tǒng)計(jì)部門(mén) 如果需要詳細(xì)的損失數(shù)字 ， 可 電詢 62332931。 另?yè)?jù)專家認(rèn)為震級(jí) 不會(huì)超過(guò) 4級(jí) ， 并認(rèn)為地 處無(wú)人區(qū) ， 不會(huì)造成人員傷亡 。 提示：分析概括用下劃線標(biāo)出的要點(diǎn)，經(jīng)過(guò)概念化形成槽（ slot）、側(cè)面（ facet）值。特別要注意，“ 值 ” （ value）、 “ 默認(rèn)值 ” （ default）、 “ 如果需要值 ” （ ifneeded）、 “ 如果附加值 ” （ ifadded）的區(qū)別與應(yīng)用，建議采用格式如下，不用的側(cè)面值可刪。 Frame 地震 Slot1： Value： Default： Ifneeded： Ifadded： Slot2： Value： Default： Ifneeded： Ifadded： Slot3： Value： Default： Ifneeded： Ifadded： 解： 第一步：確定框架的名字和框架的槽 。 本報(bào)道中 ， 涉及地震的發(fā)生時(shí)間 、 地點(diǎn) 、財(cái)產(chǎn)損失 、 傷亡人數(shù) 、 震級(jí)大小等屬性 ， 所以 ， 可將時(shí)間 、 地點(diǎn) 、 震級(jí) 、 傷亡人數(shù) 、 財(cái)產(chǎn)損失等作為槽名 。 第二步：分析本報(bào)道中各對(duì)象間的關(guān)系 。 由于報(bào)道中只涉及地震一件事 ， 所以該步可省略 。 框架名：＜地震 1＞ 時(shí)間：3月 14日 地點(diǎn)：云南玉溪地區(qū) 震級(jí)： 專家經(jīng)驗(yàn)值： ≤4級(jí) 準(zhǔn)確值：NIL 傷亡人數(shù)： 專家經(jīng)驗(yàn)值： 0 財(cái)產(chǎn)損失： 大約損失： 10萬(wàn)元 ifneeded ：ASK （ 電詢62332931） 第 3章 搜索推理技術(shù) 重點(diǎn)掌握一般圖搜索策略和消解原理，掌握各種搜索方法和產(chǎn)生式系統(tǒng)原理，了解規(guī)則演繹系統(tǒng)的基本原理，對(duì)系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等高級(jí)推理技術(shù)作一般性了解。 第 3章 搜索推理技術(shù) 從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。而實(shí)現(xiàn)求解的過(guò)程，采用的基本方法包括搜索和推理。 第 3章 搜索推理技術(shù) ?和搜索相對(duì)應(yīng)的知識(shí)表示法一般有兩種： ?狀態(tài)空間法 ：（ S， F， G） ?與或圖表示法：基于一種分解與變換的思想，利用樹(shù)狀結(jié)構(gòu)對(duì)復(fù)雜問(wèn)題進(jìn)行表示，使復(fù)雜問(wèn)題簡(jiǎn)單化。 第 3章 搜索推理技術(shù) ?圖搜索策略是一種在圖中尋找路徑的方法。 ?搜索種類(lèi)： ?盲目搜索：只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索。 ?啟發(fā)式搜索：根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些信息來(lái)不斷改變和調(diào)整搜索的方向。 圖搜索過(guò)程框圖 開(kāi)始 把 S放入 OPEN表 OPEN為空表？ 把第一個(gè)節(jié)點(diǎn) (n)從 OPEN 移至 CLOSED表 n為目標(biāo)節(jié)點(diǎn)？ 把 n的后繼節(jié)點(diǎn)放入 OPEN表的 末端，提供返回節(jié)點(diǎn) n的指針 修改指針?lè)较? 重排 OPEN表 失敗 成功 是 是 否 否 盲目搜索 ? 盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。寬度優(yōu)先搜索和深度優(yōu)先搜索，屬于盲目搜索方法。 寬度優(yōu)先搜索 ?搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，如左圖所示。 從圖可見(jiàn)，這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 s L O M F P Q N F F F ?例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缬覉D所示的目標(biāo)棋局問(wèn)題： 啟發(fā)式搜索 ? 盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。 ? 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法 ,其主要的差別是 OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問(wèn)題。人們就試圖找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大為提高。 ? 啟發(fā)信息：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問(wèn)題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。 ? 把利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。 啟發(fā)式搜索 ?啟發(fā)式搜索策略 啟發(fā)信息用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免象在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。 這種搜索總是選擇 “ 最有希望 ” 的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。這種搜索叫做有序搜索 (ordered search)。 有序搜索 ?有序搜索又稱為最好優(yōu)先搜索，它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。 估價(jià)函數(shù) f的確定：一個(gè)節(jié)點(diǎn)的希望程度越大，則其 f值越小。為此，被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。 f是從起始節(jié)點(diǎn)約束地通過(guò)節(jié)點(diǎn) n而到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑上的一個(gè)估算代價(jià) 。 有序搜索 ?寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。 ?對(duì)于寬度優(yōu)先搜索，我們選擇 f(i)作為節(jié)點(diǎn) i的深度。對(duì)于等代價(jià)搜索， f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn) i這段路徑的代價(jià)。 A*算法 ?A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 ?估價(jià)函數(shù) f： f(n)=g(n)+h(n) g(n)：就是到目前為止用搜索算法找到的從 S到 n的最小路徑代價(jià)。 h(n)： 依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。 從節(jié)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià) 的估計(jì)。 例：八數(shù)碼難題 解： 采用估價(jià)函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹(shù)中節(jié)點(diǎn) n的深度； W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。 因此，起始節(jié)點(diǎn)棋局的 f值等于 0+3=3。 2 8 31 47 6 51 2 38 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 58 32 1 47 6 52 8 37 1 46 52 31 8 47 6 528 47 6 51 2 38 47 6 52 38 46 5