《人工智能知识表示-状态空间35》由会员分享，可在线阅读，更多相关《人工智能知识表示-状态空间35（35页珍藏版）》请在装配图网上搜索。
1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能,刘海波,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,学习要求,了解知识,与,与知识表,示,示的概念,理解状态,与,与状态空,间,间的概念,掌握状态,空,空间的图,描,描述方法,掌握用状,态,态空间法,表,表示与求,解,解问题,Knowledge,Bacon,Knowledge is power,Feigenbaum,In the knowledge lies the power,如何让知,识,识爆发出,力,力量呢？,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,。,知识工程,的,的研究课,题,题,知识表示,问,问题,知识获取,问,问题,知识利用,问,问题,Knowledge,1997,年版,Webster,词典对知,识,识的定义,：,：,知识是通,过,
4、过实践、,研,研究、联,系,系或调查,获,获得的关,于,于事物的,事,事实和状,态,态的认识,，,，是对科,学,学、艺术,或,或技术的,理,理解，是,人,人类获得,的,的关于真,理,理和原理,的,的认识的,总,总和。总,之,之，知识,是,是人类积,累,累的关于,自,自然和社,会,会的认识,和,和经验的,总,总和。,知识反映,了,了客观世,界,界中事物,之,之间的关系，不同事,物,物或者相,同,同事物间,的,的不同关,系,系形成了,不,不同的知,识,识。,Relations,Knowledge,知识的特,性,性：,相对正确,性,性,不确定性,随机性,模糊性,经验性,不完全性,可表示性,与,与可利
5、用,性,性,协议性,Knowledge,知识的分,类,类,按知识的,作,作用范围,划,划分为常识性知,识,识和领域性知,识,识,按知识的,作,作用及表,示,示划分为事实性知,识,识、过程性知,识,识和控制性知,识,识,Knowledge,知识的分,类,类,例：从哈,尔,尔滨到北,京,京是乘飞,机,机还是坐,火,火车的问,题,题,事实性知,识,识：哈尔,滨,滨、北京,、,、飞机、,火,火车、时,间,间、费用,过程性知,识,识：乘飞,机,机、坐火,车,车,控制性知,识,识：乘飞,机,机较快、,较,较贵。坐,火,火车较慢,、,、较便宜,。,。,Knowledge,知识的分,类,类,按知识的,确,确定
6、性划,分,分为确定性知,识,识和不确定性,知,知识,按知识的,结,结构及表,现,现形式划,分,分为逻辑性知,识,识和形象性知,识,识,Knowledge,知识的分,类,类,Knowledge Representation,表示是现实事,物,物的一种,替,替代物，,如,如地图。,Knowledge Representation,知识表示就是将人,类,类知识形,式,式化或者,模,模型化。,实,实际上就,是,是一种计,算,算机可以,接,接受的用,于,于描述知,识,识的数据,结,结构及其,处,处理机制,。,。,知识表示,=,数据结构,+,处理机制,Knowledge Representation,知识
7、表示,的,的要求,正确有效,便于知识,的,的获取、,组,组织与维,护,护管理,便于知识,的,的利用（,如,如搜索、,推,推理、计,算,算）,便于知识,的,的理解与,机,机器实现,Knowledge Representation,State SpaceRepresentation,（状态空,间,间法）,ProblemReduction Representation,（问题归,约,约法）,Predicate LogicRepresentation,（谓词逻,辑,辑法）,SemanticNetworkRepresentations,（语义网,络,络法）,Frame Representations,（
8、框架法,）,）,Script Representations,（脚本法,）,）,Procedure Representations,（过程法,）,）,Petri Net Representations,（,Petri,网法）,Object-OrientedRepresentations,（面向对,象,象法）,State SpaceRepresentation,状态是用来表,示,示描述系,统,统状态的,事,事实性知,识,识的一组,有,有序变量,集,集合：,Q,=,q,0,q,1,q,n,T,式中每个,元,元素,q,i,(,i,=0,1,，,n,),称为状态,变,变量，给,定,定每个状,态,态变量
9、的,一,一组值就,得,得到一个,具,具体的状,态,态。,State SpaceRepresentation,操作是用来表,示,示引起状,态,态变化的,过,过程性知,识,识的一组,关,关系或函,数,数：,O,=,o,1,o,2,o,m,式中每个,元,元素,o,j,(,j,=0,1,，,m,),称为操作,算,算子。,State SpaceRepresentation,状态空间是利用状,态,态变量和,操,操作算子,表,表示系统,或,或问题的,有,有关知识,的,的符号体,系,系，状态,空,空间是一,个,个四元组,：,：,(,S,O,S,0,G,),其中：,S,：状态集,合,合；,O,：操作算,子,子的
10、集合,；,；,S,0,：包含问,题,题的初始,状,状态,G,：包含问,题,题的目标,状,状态,State SpaceRepresentation,解是使初始,状,状态转换,为,为目标状,态,态的有限,操,操作算子,序,序列。,解往往不,惟,惟一！,State SpaceRepresentation,任何类型,的,的数据结,构,构都可以,用,用来描述,状,状态，如,符,符号、字,符,符串、向,量,量、多维,数,数组、树,和,和表格等,。,。,所选用的数据,结,结构形式要与,状,状态所蕴含的,某,某些特性具有,相,相似性。,StateSpaceRepresentation,例题：八数码,问,问题（
11、重排九,宫,宫问题）,任何一种摆法,就,就是一个状态,，,，所有摆法即,为,为状态集,S,，其大小为,9!,，,S,0,和,G,分别为上面左,右,右两图所示状,态,态。操作,O,如何表示？,StateSpaceRepresentation,例题：八数码,问,问题（重排九,宫,宫问题）,O=,数码移动操作,O=,，箭头表示移,动,动空格,如何求解？,StateSpaceGraph,状态空间可用,有,有向图来描述,图的节点表示,问,问题的状态,图的弧表示状,态,态之间的关系,弧可用一个数,字,字表示对应操,作,作算子的代价,问题求解等价,于,于在图中寻找,从,从起点到目标,点,点的路径,State
12、SpaceGraph,八数码问题状,态,态空间的图描,述,述,Examples,TSP,问题（,Traveling SalemanProblem,）,有一个推销员,，,，要到,n,个城市推销商,品,品，他要找出,一,一个包含所有,n,个城市（每个,城,城市只能经过,一,一次）的具有,最,最短路程的环,路,路。,Examples,TSP,问题（,Traveling SalemanProblem,）,Examples,CPP,问题（,Chinese Postman Problem,）,一个邮递员从,邮,邮局出发，到,所,所辖街道投递,邮,邮件，最后返,回,回邮局，如果,他,他必须走遍所,辖,辖的每
13、条街道,至,至少一次，那,么,么他应如何选,择,择投递路线，,使,使所走的路程,最,最短？,Extensions,哥尼斯堡七桥,问,问题,Pregel,Knigsberg,Pregel,Extensions,哥尼斯堡七桥,问,问题,Extensions,Euler,回路,给定无孤立结,点,点图,G,，若存在一条,回,回路，经过图,中,中每边一次且,仅,仅一次，该回,路,路称为,Euler,回路。,Extensions,Hamilton,回路,给定图,G,，若存在一条,回,回路，经过图,中,中每个结点恰,好,好一次，这条,回,回路称作,Hamilton,回路。,Questions,TSP,、,CPP,、,Hamilton,和,Euler,回路之间是什,么,么关系？,Hamilton,和,Euler,回路在什么情,况,况下存在？又,如,如何找到？,我们如何用人,工,工智能方法对,此,此类问题求解,？,？,
人工智能知识表示-状态空间35
