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

人工智能劉海波HarbinEngineeringUniversityReviewAnagentisanythingthatcanbeviewedasperceivingitsenvironmentthroughsensorsandactinguponthatenvironmentthrougheffectors.Thepropertiesofanagent:AutonomyReactivitySocialabilityPro-activenessReviewMissionaryCannibalProblemLecture3:

KnowledgeRepresentation&StateSpace學(xué)習(xí)要求了解知識(shí)與知識(shí)表示的概念了解形狀與形狀空間的概念掌握形狀空間的圖描畫方法掌握用形狀空間法表示與求解問(wèn)題KnowledgeBaconKnowledgeispowerFeigenbaumIntheknowledgeliesthepower如何讓知識(shí)迸發(fā)出力量呢？KnowledgeEnginneringKnowledgeEngineering(definedin1983byEdwardFeigenbaum)isanengineeringdisciplinethatinvolvesintegratingknowledgeintocomputersystemsinordertosolvecomplexproblemsnormallyrequiringahighlevelofhumanexpertise。知識(shí)工程的研討課題知識(shí)表示問(wèn)題知識(shí)獲取問(wèn)題知識(shí)利用問(wèn)題Knowledge1997年版Webster詞典對(duì)知識(shí)的定義：知識(shí)是經(jīng)過(guò)實(shí)際、研討、聯(lián)絡(luò)或調(diào)查獲得的關(guān)于事物的現(xiàn)實(shí)和形狀的認(rèn)識(shí)，是對(duì)科學(xué)、藝術(shù)或技術(shù)的了解，是人類獲得的關(guān)于真理和原理的認(rèn)識(shí)的總和?？傊R(shí)是人類積累的關(guān)于自然和社會(huì)的認(rèn)識(shí)和閱歷的總和。知識(shí)反映了客觀世界中事物之間的關(guān)系，不同事物或者一樣事物間的不同關(guān)系構(gòu)成了不同的知識(shí)。RelationsKnowledge知識(shí)的特性：相對(duì)正確性不確定性隨機(jī)性模糊性閱歷性不完全性可表示性與可利用性協(xié)議性Knowledge知識(shí)的分類按知識(shí)的作用范圍劃分為常識(shí)性知識(shí)和領(lǐng)域性知識(shí)按知識(shí)的作用及表示劃分為現(xiàn)實(shí)性知識(shí)、過(guò)程性知識(shí)和控制性知識(shí)Knowledge知識(shí)的分類例：從哈爾濱到北京是乘飛機(jī)還是坐火車的問(wèn)題現(xiàn)實(shí)性知識(shí)：哈爾濱、北京、飛機(jī)、火車、時(shí)間、費(fèi)用過(guò)程性知識(shí)：乘飛機(jī)、坐火車控制性知識(shí)：乘飛機(jī)較快、較貴。坐火車較慢、較廉價(jià)。Knowledge知識(shí)的分類按知識(shí)確實(shí)定性劃分為確定性知識(shí)和不確定性知識(shí)按知識(shí)的構(gòu)造及表現(xiàn)方式劃分為邏輯性知識(shí)和籠統(tǒng)性知識(shí)Knowledge知識(shí)的分類KnowledgeRepresentation表示是現(xiàn)實(shí)事物的一種替代物，如地圖。KnowledgeRepresentation知識(shí)表示就是將人類知識(shí)方式化或者模型化。實(shí)踐上就是一種計(jì)算機(jī)可以接受的用于描畫知識(shí)的數(shù)據(jù)構(gòu)造及其處置機(jī)制。知識(shí)表示=數(shù)據(jù)構(gòu)造+處置機(jī)制KnowledgeRepresentation知識(shí)表示的要求正確有效便于知識(shí)的獲取、組織與維護(hù)管理便于知識(shí)的利用〔如搜索、推理、計(jì)算〕便于知識(shí)的了解與機(jī)器實(shí)現(xiàn)KnowledgeRepresentationStateSpaceRepresentation〔形狀空間法〕ProblemReductionRepresentation〔問(wèn)題歸約法〕PredicateLogicRepresentation〔謂詞邏輯法〕SemanticNetworkRepresentations〔語(yǔ)義網(wǎng)絡(luò)法〕FrameRepresentations〔框架法〕ScriptRepresentations〔腳本法〕ProcedureRepresentations〔過(guò)程法〕PetriNetRepresentations〔Petri網(wǎng)法〕Object-OrientedRepresentations〔面向?qū)ο蠓ā砈tateSpaceRepresentation形狀是用來(lái)表示描畫系統(tǒng)形狀的現(xiàn)實(shí)性知識(shí)的一組有序變量集合：

Q=[q0,q1,…,qn]T

式中每個(gè)元素qi(i=0,1，…,n)稱為形狀變量，給定每個(gè)形狀變量的一組值就得到一個(gè)詳細(xì)的形狀。StateSpaceRepresentation操作是用來(lái)表示引起形狀變化的過(guò)程性知識(shí)的一組關(guān)系或函數(shù)：

O={o1,o2,…,om}

式中每個(gè)元素oj(j=0,1，…,m)稱為操作算子。StateSpaceRepresentation形狀空間是利用形狀變量和操作算子表示系統(tǒng)或問(wèn)題的有關(guān)知識(shí)的符號(hào)體系，形狀空間是一個(gè)四元組：

(S,O,S0,G)

其中：

S：形狀集合；

O：操作算子的集合；

S0：包含問(wèn)題的初始形狀

G：包含問(wèn)題的目的形狀StateSpaceRepresentation解是使初始形狀轉(zhuǎn)換為目的形狀的有限操作算子序列。解往往不獨(dú)一！StateSpaceRepresentation任何類型的數(shù)據(jù)構(gòu)造都可以用來(lái)描畫形狀，如符號(hào)、字符串、向量、多維數(shù)組、樹和表格等。所選用的數(shù)據(jù)構(gòu)造方式要與形狀所蘊(yùn)含的某些特性具有類似性。StateSpaceRepresentation例題：八數(shù)碼問(wèn)題〔重排九宮問(wèn)題〕任何一種擺法就是一個(gè)形狀，一切擺法即為形狀集S，其大小為9!，S0和G分別為上面左右兩圖所示形狀。操作O如何表示？StateSpaceRepresentation例題：八數(shù)碼問(wèn)題〔重排九宮問(wèn)題〕O={數(shù)碼挪動(dòng)操作}O={,,,}，箭頭表示挪動(dòng)空格如何求解？StateSpaceGraph形狀空間可用有向圖來(lái)描畫圖的節(jié)點(diǎn)表示問(wèn)題的形狀圖的弧表示形狀之間的關(guān)系弧可用一個(gè)數(shù)字表示對(duì)應(yīng)操作算子的代價(jià)問(wèn)題求解等價(jià)于在圖中尋覓從起點(diǎn)到目的點(diǎn)的途徑StateSpaceGraph八數(shù)碼問(wèn)題形狀空間的圖描畫ExamplesTSP問(wèn)題〔TravelingSalemanProblem〕有一個(gè)推銷員，要到n個(gè)城市推銷商品，他要找出一個(gè)包含一切n個(gè)城市〔每個(gè)城市只能經(jīng)過(guò)一次〕的具有最短路程的環(huán)路。ExamplesTSP問(wèn)題〔TravelingSalemanProblem〕ExamplesCPP問(wèn)題〔ChinesePostmanProblem〕一個(gè)郵遞員從郵局出發(fā)，到所轄街道投遞郵件，最后前往郵局，假設(shè)他必需走遍所轄的每條街道至少一次，那么他應(yīng)如何選擇投遞道路，使所走的路程最短？Extensions哥尼斯堡七橋問(wèn)題PregelK?nigsbergPregelExtensions哥尼斯堡七橋問(wèn)題ExtensionsEuler回路給定無(wú)孤立結(jié)點(diǎn)圖G，假設(shè)存在一條回路，經(jīng)過(guò)圖中每邊一次且僅一次，該回路稱為Euler回路。