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