人工智能 知識(shí)表示-狀態(tài)空間.ppt

1、人工智能,劉海波,Harbin Engineering University,Review,An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through effectors. The properties of an agent: Autonomy Reactivity Social ability Pro-activeness,Review,Missionary Cannibal Problem,Lec

2、ture 3:Knowledge Representation & State Space,學(xué)習(xí)要求,了解知識(shí)與知識(shí)表示的概念 理解狀態(tài)與狀態(tài)空間的概念 掌握狀態(tài)空間的圖描述方法 掌握用狀態(tài)空間法表示與求解問(wèn)題,Knowledge,如何讓知識(shí)爆發(fā)出力量呢？,Knowledge Enginnering,Knowledge Engineering (defined in 1983 by Edward Feigenbaum) is an engineering discipline that involves integrating knowledge into computer systems i

3、n order to solve complex problems normally requiring a high level of human expertise。 知識(shí)工程的研究課題 知識(shí)表示問(wèn)題 知識(shí)獲取問(wèn)題 知識(shí)利用問(wèn)題,Knowledge,1997年版Webster詞典對(duì)知識(shí)的定義： 知識(shí)是通過(guò)實(shí)踐、研究、聯(lián)系或調(diào)查獲得的關(guān)于事物的事實(shí)和狀態(tài)的認(rèn)識(shí)，是對(duì)科學(xué)、藝術(shù)或技術(shù)的理解，是人類獲得的關(guān)于真理和原理的認(rèn)識(shí)的總和?？傊?，知識(shí)是人類積累的關(guān)于自然和社會(huì)的認(rèn)識(shí)和經(jīng)驗(yàn)的總和。 知識(shí)反映了客觀世界中事物之間的關(guān)系，不同事物或者相同事物間的不同關(guān)系形成了不同的知識(shí)。,Relations,

4、Knowledge,知識(shí)的特性： 相對(duì)正確性 不確定性 隨機(jī)性 模糊性 經(jīng)驗(yàn)性 不完全性 可表示性與可利用性 協(xié)議性,Knowledge,知識(shí)的分類 按知識(shí)的作用范圍劃分為常識(shí)性知識(shí)和領(lǐng)域性知識(shí) 按知識(shí)的作用及表示劃分為事實(shí)性知識(shí)、過(guò)程性知識(shí)和控制性知識(shí),Knowledge,知識(shí)的分類 例：從哈爾濱到北京是乘飛機(jī)還是坐火車的問(wèn)題 事實(shí)性知識(shí)：哈爾濱、北京、飛機(jī)、火車、時(shí)間、費(fèi)用 過(guò)程性知識(shí)：乘飛機(jī)、坐火車 控制性知識(shí)：乘飛機(jī)較快、較貴。坐火車較慢、較便宜。,Knowledge,知識(shí)的分類 按知識(shí)的確定性劃分為確定性知識(shí)和不確定性知識(shí) 按知識(shí)的結(jié)構(gòu)及表現(xiàn)形式劃分為邏輯性知識(shí)和形象性知識(shí),Know

5、ledge,知識(shí)的分類,Knowledge Representation,表示是現(xiàn)實(shí)事物的一種替代物，如地圖。,Knowledge Representation,知識(shí)表示就是將人類知識(shí)形式化或者模型化。實(shí)際上就是一種計(jì)算機(jī)可以接受的用于描述知識(shí)的數(shù)據(jù)結(jié)構(gòu)及其處理機(jī)制。 知識(shí)表示=數(shù)據(jù)結(jié)構(gòu)+處理機(jī)制,Knowledge Representation,知識(shí)表示的要求 正確有效 便于知識(shí)的獲取、組織與維護(hù)管理 便于知識(shí)的利用（如搜索、推理、計(jì)算） 便于知識(shí)的理解與機(jī)器實(shí)現(xiàn),Knowledge Representation,State Space Representation（狀態(tài)空間法） Probl

6、em Reduction Representation（問(wèn)題歸約法） Predicate Logic Representation（謂詞邏輯法） Semantic Network Representations（語(yǔ)義網(wǎng)絡(luò)法） Frame Representations（框架法） Script Representations（腳本法） Procedure Representations（過(guò)程法） Petri Net Representations（Petri網(wǎng)法） Object-Oriented Representations（面向?qū)ο蠓ǎ?State Space Representation,

7、狀態(tài)是用來(lái)表示描述系統(tǒng)狀態(tài)的事實(shí)性知識(shí)的一組有序變量集合： Q= q0, q1, , qnT式中每個(gè)元素qi (i=0,1，, n)稱為狀態(tài)變量，給定每個(gè)狀態(tài)變量的一組值就得到一個(gè)具體的狀態(tài)。,State Space Representation,操作是用來(lái)表示引起狀態(tài)變化的過(guò)程性知識(shí)的一組關(guān)系或函數(shù)： O = o1, o2, , om 式中每個(gè)元素oj (j=0,1，, m)稱為操作算子。,State Space Representation,狀態(tài)空間是利用狀態(tài)變量和操作算子表示系統(tǒng)或問(wèn)題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空間是一個(gè)四元組： (S, O, S0, G) 其中：S：狀態(tài)集合；O：操作算

8、子的集合；S0：包含問(wèn)題的初始狀態(tài)G：包含問(wèn)題的目標(biāo)狀態(tài),State Space Representation,解是使初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)的有限操作算子序列。 解往往不惟一！,State Space Representation,任何類型的數(shù)據(jù)結(jié)構(gòu)都可以用來(lái)描述狀態(tài)，如符號(hào)、字符串、向量、多維數(shù)組、樹(shù)和表格等。 所選用的數(shù)據(jù)結(jié)構(gòu)形式要與狀態(tài)所蘊(yùn)含的某些特性具有相似性。,State Space Representation,例題：八數(shù)碼問(wèn)題（重排九宮問(wèn)題） 任何一種擺法就是一個(gè)狀態(tài)，所有擺法即為狀態(tài)集S，其大小為9!，S0和G分別為上面左右兩圖所示狀態(tài)。操作O如何表示？,State Space

9、 Representation,例題：八數(shù)碼問(wèn)題（重排九宮問(wèn)題）,O = 數(shù)碼移動(dòng)操作 O = , , , ，箭頭表示移動(dòng)空格,如何求解？,State Space Graph,狀態(tài)空間可用有向圖來(lái)描述 圖的節(jié)點(diǎn)表示問(wèn)題的狀態(tài) 圖的弧表示狀態(tài)之間的關(guān)系 弧可用一個(gè)數(shù)字表示對(duì)應(yīng)操作算子的代價(jià) 問(wèn)題求解等價(jià)于在圖中尋找從起點(diǎn)到目標(biāo)點(diǎn)的路徑,State Space Graph,八數(shù)碼問(wèn)題狀態(tài)空間的圖描述,Examples,TSP問(wèn)題（Traveling Saleman Problem） 有一個(gè)推銷員，要到n個(gè)城市推銷商品，他要找出一個(gè)包含所有n個(gè)城市（每個(gè)城市只能經(jīng)過(guò)一次）的具有最短路程的環(huán)路。,Examples,TSP問(wèn)題（Traveling Saleman Problem）,Examples,CPP問(wèn)題（Chinese Postman Problem） 一個(gè)郵遞員從郵局出發(fā)，到所轄街道投遞郵件，最后返回郵局，如果他必須走遍所轄的每條街道至少一次，那么他應(yīng)如何選擇投遞路線，使所走的路程最短？,Extensions,哥尼斯堡七橋問(wèn)題,Pregel,Knigsberg,Pregel,Extensions,哥尼斯堡七橋問(wèn)題,Extensions,Euler回路 給定無(wú)孤立結(jié)點(diǎn)圖G，若存在一條回路，經(jīng)過(guò)圖中每邊一次且僅一次，該回路稱為Euler回路。,Exten