單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,人工智能,劉海波,Harbin Engineering University,,Review,An agentisanythingthat can beviewedas perceiving its environment through sensors and actingupon that environment through effectors.,Theproperties of anagent:,Autonomy,Reactivity,Social ability,Pro-activeness,Review,Missionary CannibalProblem,Lecture3:KnowledgeRepresentation&StateSpace,學習要求,了解知識,與,與知識表,示,示的概念,理解狀態(tài),與,與狀態(tài)空,間,間的概念,掌握狀態(tài),空,空間的圖,描,描述方法,掌握用狀,態(tài),態(tài)空間法,表,表示與求,解,解問題,Knowledge,Bacon,Knowledge is power,Feigenbaum,In the knowledge lies the power,如何讓知,識,識爆發(fā)出,力,力量呢？,Knowledge Enginnering,Knowledge Engineering(definedin1983byEdward Feigenbaum)is an engineering disciplinethat involves integrating knowledgeinto computer systems in orderto solvecomplexproblems normally requiringa highlevel ofhuman expertise,。,知識工程,的,的研究課,題,題,知識表示,問,問題,知識獲取,問,問題,知識利用,問,問題,Knowledge,1997,年版,Webster,詞典對知,識,識的定義,：,：,知識是通,過,過實踐、,研,研究、聯(lián),系,系或調(diào)查,獲,獲得的關,于,于事物的,事,事實和狀,態(tài),態(tài)的認識,，,，是對科,學,學、藝術,或,或技術的,理,理解，是,人,人類獲得,的,的關于真,理,理和原理,的,的認識的,總,總和。總,之,之，知識,是,是人類積,累,累的關于,自,自然和社,會,會的認識,和,和經(jīng)驗的,總,總和。,知識反映,了,了客觀世,界,界中事物,之,之間的關系，不同事,物,物或者相,同,同事物間,的,的不同關,系,系形成了,不,不同的知,識,識。,Relations,Knowledge,知識的特,性,性：,相對正確,性,性,不確定性,隨機性,模糊性,經(jīng)驗性,不完全性,可表示性,與,與可利用,性,性,協(xié)議性,Knowledge,知識的分,類,類,按知識的,作,作用范圍,劃,劃分為常識性知,識,識和領域性知,識,識,按知識的,作,作用及表,示,示劃分為事實性知,識,識、過程性知,識,識和控制性知,識,識,Knowledge,知識的分,類,類,例：從哈,爾,爾濱到北,京,京是乘飛,機,機還是坐,火,火車的問,題,題,事實性知,識,識：哈爾,濱,濱、北京,、,、飛機、,火,火車、時,間,間、費用,過程性知,識,識：乘飛,機,機、坐火,車,車,控制性知,識,識：乘飛,機,機較快、,較,較貴。坐,火,火車較慢,、,、較便宜,。,。,Knowledge,知識的分,類,類,按知識的,確,確定性劃,分,分為確定性知,識,識和不確定性,知,知識,按知識的,結,結構及表,現(xiàn),現(xiàn)形式劃,分,分為邏輯性知,識,識和形象性知,識,識,Knowledge,知識的分,類,類,Knowledge Representation,表示是現(xiàn)實事,物,物的一種,替,替代物，,如,如地圖。,Knowledge Representation,知識表示就是將人,類,類知識形,式,式化或者,模,模型化。,實,實際上就,是,是一種計,算,算機可以,接,接受的用,于,于描述知,識,識的數(shù)據(jù),結,結構及其,處,處理機制,。,。,知識表示,=,數(shù)據(jù)結構,+,處理機制,Knowledge Representation,知識表示,的,的要求,正確有效,便于知識,的,的獲取、,組,組織與維,護,護管理,便于知識,的,的利用（,如,如搜索、,推,推理、計,算,算）,便于知識,的,的理解與,機,機器實現(xiàn),Knowledge Representation,State SpaceRepresentation,（狀態(tài)空,間,間法）,ProblemReduction Representation,（問題歸,約,約法）,Predicate LogicRepresentation,（謂詞邏,輯,輯法）,SemanticNetworkRepresentations,（語義網(wǎng),絡,絡法）,Frame Representations,（框架法,）,）,Script Representations,（腳本法,）,）,Procedure Representations,（過程法,）,）,Petri Net Representations,（,Petri,網(wǎng)法）,Object-OrientedRepresentations,（面向?qū)?象,象法）,State SpaceRepresentation,狀態(tài)是用來表,示,示描述系,統(tǒng),統(tǒng)狀態(tài)的,事,事實性知,識,識的一組,有,有序變量,集,集合：,Q,=,q,0,q,1,q,n,T,式中每個,元,元素,q,i,(,i,=0,1,，,n,),稱為狀態(tài),變,變量，給,定,定每個狀,態(tài),態(tài)變量的,一,一組值就,得,得到一個,具,具體的狀,態(tài),態(tài)。,State SpaceRepresentation,操作是用來表,示,示引起狀,態(tài),態(tài)變化的,過,過程性知,識,識的一組,關,關系或函,數(shù),數(shù)：,O,=,o,1,o,2,o,m,式中每個,元,元素,o,j,(,j,=0,1,，,m,),稱為操作,算,算子。,State SpaceRepresentation,狀態(tài)空間是利用狀,態(tài),態(tài)變量和,操,操作算子,表,表示系統(tǒng),或,或問題的,有,有關知識,的,的符號體,系,系，狀態(tài),空,空間是一,個,個四元組,：,：,(,S,O,S,0,G,),其中：,S,：狀態(tài)集,合,合；,O,：操作算,子,子的集合,；,；,S,0,：包含問,題,題的初始,狀,狀態(tài),G,：包含問,題,題的目標,狀,狀態(tài),State SpaceRepresentation,解是使初始,狀,狀態(tài)轉(zhuǎn)換,為,為目標狀,態(tài),態(tài)的有限,操,操作算子,序,序列。,解往往不,惟,惟一！,State SpaceRepresentation,任何類型,的,的數(shù)據(jù)結,構,構都可以,用,用來描述,狀,狀態(tài)，如,符,符號、字,符,符串、向,量,量、多維,數(shù),數(shù)組、樹,和,和表格等,。,。,所選用的數(shù)據(jù),結,結構形式要與,狀,狀態(tài)所蘊含的,某,某些特性具有,相,相似性。,StateSpaceRepresentation,例題：八數(shù)碼,問,問題（重排九,宮,宮問題）,任何一種擺法,就,就是一個狀態(tài),，,，所有擺法即,為,為狀態(tài)集,S,，其大小為,9!,，,S,0,和,G,分別為上面左,右,右兩圖所示狀,態(tài),態(tài)。操作,O,如何表示？,StateSpaceRepresentation,例題：八數(shù)碼,問,問題（重排九,宮,宮問題）,O=,數(shù)碼移動操作,O=,，箭頭表示移,動,動空格,如何求解？,StateSpaceGraph,狀態(tài)空間可用,有,有向圖來描述,圖的節(jié)點表示,問,問題的狀態(tài),圖的弧表示狀,態(tài),態(tài)之間的關系,弧可用一個數(shù),字,字表示對應操,作,作算子的代價,問題求解等價,于,于在圖中尋找,從,從起點到目標,點,點的路徑,StateSpaceGraph,八數(shù)碼問題狀,態(tài),態(tài)空間的圖描,述,述,Examples,TSP,問題（,Traveling SalemanProblem,）,有一個推銷員,，,，要到,n,個城市推銷商,品,品，他要找出,一,一個包含所有,n,個城市（每個,城,城市只能經(jīng)過,一,一次）的具有,最,最短路程的環(huán),路,路。,Examples,TSP,問題（,Traveling SalemanProblem,）,Examples,CPP,問題（,Chinese Postman Problem,）,一個郵遞員從,郵,郵局出發(fā)，到,所,所轄街道投遞,郵,郵件，最后返,回,回郵局，如果,他,他必須走遍所,轄,轄的每條街道,至,至少一次，那,么,么他應如何選,擇,擇投遞路線，,使,使所走的路程,最,最短？,Extensions,哥尼斯堡七橋,問,問題,Pregel,Knigsberg,Pregel,Extensions,哥尼斯堡七橋,問,問題,Extensions,Euler,回路,給定無孤立結,點,點圖,G,，若存在一條,回,回路，經(jīng)過圖,中,中每邊一次且,僅,僅一次，該回,路,路稱為,Euler,回路。,Extensions,Hamilton,回路,給定圖,G,，若存在一條,回,回路，經(jīng)過圖,中,中每個結點恰,好,好一次，這條,回,回路稱作,Hamilton,回路。,Questions,TSP,、,CPP,、,Hamilton,和,Euler,回路之間是什,么,么關系？,Hamilton,和,Euler,回路在什么情,況,況下存在？又,如,如何找到？,我們?nèi)绾斡萌?工,工智能方法對,此,此類問題求解,？,？,