人工智能,刘海波,Harbin Engineering University,bb.hrbeu.edu.cn,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,Lecture 3: Knowledge Representation & State Space,学习要求,了解知识与知识表示的概念 理解状态与状态空间的概念 掌握状态空间的图描述方法 掌握用状态空间法表示与求解问题,Knowledge,如何让知识爆发出力量呢？,Knowledge Enginnering,Knowledge Engineering (defined in 1983 by Edward Feigenbaum) is an engineering discipline that involves integrating knowledge into computer systems in order to solve complex problems normally requiring a high level of human expertise。 知识工程的研究课题 知识表示问题 知识获取问题 知识利用问题,Knowledge,1997年版Webster词典对知识的定义： 知识是通过实践、研究、联系或调查获得的关于事物的事实和状态的认识，是对科学、艺术或技术的理解，是人类获得的关于真理和原理的认识的总和。总之，知识是人类积累的关于自然和社会的认识和经验的总和。 知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。,Relations,Knowledge,知识的特性： 相对正确性 不确定性 随机性 模糊性 经验性 不完全性 可表示性与可利用性 协议性,Knowledge,知识的分类按知识的作用范围划分为常识性知识和领域性知识按知识的作用及表示划分为事实性知识、过程性知识和控制性知识,Knowledge,知识的分类 例：从哈尔滨到北京是乘飞机还是坐火车的问题事实性知识：哈尔滨、北京、飞机、火车、时间、费用 过程性知识：乘飞机、坐火车 控制性知识：乘飞机较快、较贵。坐火车较慢、较便宜。,Knowledge,知识的分类按知识的确定性划分为确定性知识和不确定性知识 按知识的结构及表现形式划分为逻辑性知识和形象性知识,Knowledge,知识的分类,Knowledge Representation,表示是现实事物的一种替代物，如地图。,Knowledge Representation,知识表示就是将人类知识形式化或者模型化。实际上就是一种计算机可以接受的用于描述知识的数据结构及其处理机制。知识表示=数据结构+处理机制,Knowledge Representation,知识表示的要求正确有效 便于知识的获取、组织与维护管理 便于知识的利用（如搜索、推理、计算） 便于知识的理解与机器实现,Knowledge Representation,State Space Representation（状态空间法） Problem Reduction Representation（问题归约法） Predicate Logic Representation（谓词逻辑法） Semantic Network Representations（语义网络法） Frame Representations（框架法） Script Representations（脚本法） Procedure Representations（过程法） Petri Net Representations（Petri网法） Object-Oriented Representations（面向对象法）,State Space Representation,状态是用来表示描述系统状态的事实性知识的一组有序变量集合： Q= q0, q1, , qnT 式中每个元素qi (i=0,1，, n)称为状态变量，给定每个状态变量的一组值就得到一个具体的状态。,State Space Representation,操作是用来表示引起状态变化的过程性知识的一组关系或函数： O = o1, o2, , om 式中每个元素oj (j=0,1，, m)称为操作算子。,State Space Representation,状态空间是利用状态变量和操作算子表示系统或问题的有关知识的符号体系，状态空间是一个四元组： (S, O, S0, G) 其中： S：状态集合； O：操作算子的集合； S0：包含问题的初始状态 G：包含问题的目标状态,State Space Representation,解是使初始状态转换为目标状态的有限操作算子序列。解往往不惟一！,State Space Representation,任何类型的数据结构都可以用来描述状态，如符号、字符串、向量、多维数组、树和表格等。所选用的数据结构形式要与状态所蕴含的某些特性具有相似性。,State Space Representation,例题：八数码问题（重排九宫问题）任何一种摆法就是一个状态，所有摆法即为状态集S，其大小为9!，S0和G分别为上面左右两图所示状态。操作O如何表示？,State Space Representation,例题：八数码问题（重排九宫问题）,O = 数码移动操作 O = , , , ，箭头表示移动空格,如何求解？,State Space Graph,状态空间可用有向图来描述 图的节点表示问题的状态 图的弧表示状态之间的关系 弧可用一个数字表示对应操作算子的代价 问题求解等价于在图中寻找从起点到目标点的路径,State Space Graph,八数码问题状态空间的图描述,Examples,TSP问题（Traveling Saleman Problem） 有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市（每个城市只能经过一次）的具有最短路程的环路。,Examples,TSP问题（Traveling Saleman Problem）,Examples,CPP问题（Chinese Postman Problem）一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？,Extensions,哥尼斯堡七桥问题,Pregel,Knigsberg,Pregel,Extensions,哥尼斯堡七桥问题,Extensions,Euler回路给定无孤立结点图G，若存在一条回路，经过图中每边一次且仅一次，该回路称为Euler回路。,Extensions,Hamilton回路,给定图G，若存在一条回路，经过图中每个结点恰好一次，这条回路称作Hamilton回路。,Questions,TSP、CPP、Hamilton和Euler回路之间是什么关系？ Hamilton和Euler回路在什么情况下存在？又如何找到？ 我们如何用人工智能方法对此类问题求解？,