人工智能第2章知识表示.

第2章知识表示敖志刚编制第2章知识表示第2章知识表示第2章知识表示•2．1知识与知识表示的概念•2．1．1知识•2．1．2知识表示•2．2状态空间表示法•2．2．1状态空间表示法的基本概念和策略•2．2．2状态空间表示法示例•2．3与/或图知识表示•2．3．1与/或图知识表示的概念•2．3．2与/或图表示示例第2章知识表示第2章知识表示•2．4产生式知识表示•2．4．1产生式的结构和组成•2．4．2产生式系统的分类•2．4．3产生式系统的性能及其应用•2．5语义网络•2．5．1语义网络的概念•2．5．2语义网络的推理•2．5．3语义网络表示法的特征•2．6框架表示法•2．6．1框架表示法的概念与设计•2．6．2框架的基本结构和描述•2．6．3框架系统•2．6．4框架系统的推理和求解过程•2．6．4五种知识表示方法的比较第2章知识表示2．1知识与知识表示的概念2.1.1知识1.知识的概念•知识是人们对客观事物及其规律的认识，包括对事物的现象、本质、属性、状态、关系、联系和运动等的认识；是解决问题的步骤、操作、规则、过程、技术、技巧、战术、战略、计谋、策略。知识是经过消减、加工、整理、解释、挑选、改造、选择和转换的信息和数据，是由特定领域的事实、信念、描述、关系、启发式和过程组合起来的。第2章知识表示2.知识的分类①按知识的作用：叙述型知识、过程型知识、控制型知识；②按知识的的性质：对象性知识、事件性知识、性能性知识、元知识；③按知识的作用范围：常识性知识、领域性知识；④按知识的层次：表层知识、深层知识；⑤按知识的确定性：确定性知识、不确定性知识第2章知识表示3.知识的属性•可表示性、可利用性、不确定性、矛盾性、相容性、真假性、相对性。第2章知识表示2．1．2知识表示面向人的知识表示的概念•面向人的知识表示可以用是语言、文字、数字、符号、公式、图表、图形、图像等多种形式。这些表示形式是人所能接受、理解和处理的形式。第2章知识表示2.面向计算机的知识表示的概念•就是要用某种约定的(外部)形式结构来描述知识，通常用知识的规则符号、形式语言和网络图等使知识形式化或模型化，而且这种形式结构还要能够转换为机器的内部形式，在计算机中用合适的形式对问题求解过程中所需要的各种知识进行组织、存储、检索、使用、增删、修改、推理和判断；使得计算机能方便地存储、处理和利用。第2章知识表示3.设计知识表示的基本原则•可实现性、可理解性、表示能力、可维护性、可利用性、自然性、可组织性第2章知识表示4.知识表示方法的分类•状态空间表示法•基于图的表示法与/或图表示法•语义网络表示法•谓词逻辑表示法•产生式表示法•特性表示法•框架表示法•知识表示功能表示法•脚本表示法•过程表示法•多层次信息结构表示法•概念图解表示法•神经网络表示法•意识胞表示法•不精确表示法第2章知识表示状态图YXWZSUVTACDEB节点A是B的前驱弧弧的标记弧T从A指向BB是A的后继第2章知识表示与或图示例•与节点或节点dxxxx1122dxxx12dxxx12dxx11dxxxxxx111212dxx)1(xdxdxxx21第2章知识表示有关图书馆的一个语义网络图书馆建筑物张三阅览室读者理工大学单位大礼堂校园钟山学会讲英语公园开放阅览风景美丽海福巷OwnerAfterCanNear-toSimilar-toCanA-Member-ofIs-aFetchLocated-underLocated-insideA-Kind-ofIs-aA-part-ofHaveCanLocated-at语义网络示例•第2章知识表示动物识别系统的产生式推理网络R1R2R3R4R5R6R7R8R9R10是食肉类黄褐色有黑条纹有暗斑点是有蹄类长脖子长腿吃肉∧∧∧∧∧∧有犬齿有爪眼前视是哺乳类有蹄子反刍食物∧产奶有毛虎豹斑马长颈鹿产生式推理网络示例•第2章知识表示2．2状态空间表示法2.2.1状态空间表示法的基本概念•状态：各种相关对象的可能的排列、情况、形势和现状。•表示形式：通常用一组指标、变量或数组来表示。•三个共有特征：就是状态、规则和目标。•问题的三种状态：开始状态、中间状态和目标状态。第2章知识表示知识表示一般步骤:•1．定义一状态空间；•2．确定开始状态；•3．确定目标状态；•4．规定一组规则；•5．将非形式的问题描述转换成形式描述；画出描述问题的状态图；•6．分析问题；•7．选择最佳技术去求解待解问题。第2章知识表示2.2.2状态空间表示法示例•例2-1水壶问题•有两个水壶，一个盛满为4公斤水，另一个盛满为3公斤水，水壶上没有任何度量标记。怎样在能装4公斤的水壶里恰好只装2公斤水。第2章知识表示定义操作符1．(X，Y│X＜4)→(4，Y)把4公斤的水壶装满。•2．(X，Y│Y＜3)→(X，3)把3公斤的水壶装满。•3．(X，Y│X＞O)→(X－D，Y)从4公斤的水壶倒出一些水。•4．(X，Y│Y＞O)→(X，Y－D)从3公斤的水壶倒出一些水。•5．(X，Y│X＞O)→(O，Y)把4公斤水壶中的水全部倒掉。•6．(X，Y│Y＞O)→(X，O)把3公斤水壶中的水全部倒掉。•7．(X，Y│X+Y≥4∧Y＞O)把3公斤水壶中的水往4公斤水壶•→(4，Y一(4一X))里倒，直到4公斤水壶满。•8．(X，Y│X+Y≥3∧X＞O)把4公斤水壶中的水往3公斤水壶•→(X一(3一Y)，3)里倒，直到3公斤水壶满。•9．(X，Y│X+Y≤3∧X＞O)→(O，X+Y)把4公斤水壶中水全部倒入3公斤水壶。•10．(X，Y│X+Y≤4∧Y＞O)→(X+Y，O)把3公斤水壶中水全部倒入4公斤水壶。第2章知识表示例2-2修道士和野人问题•在河的左岸有3个修道士，3个野人和1条船，修道士们想用这条船将所有的人都运过河去，但是受到以下条件的限制：•①修道士和野人都会划船，但船一次只能装运两个人；•②修道士的人数必须大于野人数；•③野人不知道是个骗局。•试问修道士如何用这条船将这些人全部都渡到河的对岸？第2章知识表示表2-2修道士和野人问题全部状态的合法性•XYZ合法性XYZ合法性XYZ合法性XYZ合法性•331合法321合法311合法301不可能•231不合法221合法211不合法201不合法•131不合法121不合法111合法101不合法•031合法021合法011合法001不可能•330不可能320合法310合法300合法•230不合法220合法210不合法200不合法•130不合法120不合法110合法100不合法•030不可能020合法010合法000合法第2章知识表示定义规则•①将一个修道士从左岸运到右岸；•②将一个野人从左岸运到右岸；•③将一个修道士和一个野人从左岸运到右岸；•④将二个修道士从左岸运到右岸；•⑤将二个野人从左岸运到右岸；•⑥将一个修道士从右岸运到左岸；•⑦将一个野人从右岸运到左岸；•⑧将一个修道士和一个野人从右岸运到左岸；•⑨将二个修道士从右岸运到左岸；•⑩将二个野人从右岸运到左岸；第2章知识表示•YXWZSUVTACDEB节点A是B的前驱弧弧的标记弧T从A指向BB是A的后继状态图的概念第2章知识表示•331310320220321300311110111011021000010031020221修道士和野人问题的状态图第2章知识表示计算机的表达方法•按BASIC语言的写法，就是用赋值语句：•10LETX=X—2•20LETZ=0•30LETX=X+1•40LETY=Y+1•50LETZ=1第2章知识表示•例2-3梵塔问题：传说印度的主神梵天做了一个梵塔，它是在一块黄铜板上插3根宝面针，其中一根针上从上到下按从小到大的顺序串上了64个金片。梵天要求僧侣们轮流把金片在三根针之间移来移去，规定每次只能移动1片，且不许大片压到小片上。并说如果这64片金片全部移至另一根针上时，世界就会在一声霹雳之中毁灭。•641231231236464第2章知识表示梵塔问题的状态图•113132221213332321两片金片的状态图（111）（311）(211）（321）（231）（221）（331）（121）（131）（223）（332）（123）（323)（232）（132）（133）（313）（212）（122）（333）（222）（233）(213）（113）（112）（312）（322）三片金片梵塔问题的状态图第2章知识表示二金片问题的一种最佳求解过程123AB123AB23AB目标状态12S'2S'1S'3123AB123AB123ABS2目标状态S1S3M(A13)M(B12)M(A32)13ABS0初始状态M(A12)M(B13)M(A23)二金片问题的状态空间图第2章知识表示三金片问题的一种最佳求解过程•123123123123123123123123XYZXYZ第2章知识表示2．3与/或图知识表示•如果一个问题p可以分解为一组子问题P1、P2、P3，…，Pn，并且只有当所有子问题Pi(i=1，2，3，…，n)都有解时原问题P才有解，任何一个子问题Pi(i=1，2，3，…，n)无解都会导致原问题P无解，则分解所得到的子问题的“与”与原问题P等价。P与P1、P2、P3，…，Pn之间的关系就可以用一棵“与树”来表示。第2章知识表示与或图示例PP1P2P3P11P12P13P14P15P16P17P18图2-9与/或图P1P2P3…PnP图2-7与树P1P2P3…PnP图2-8或树第2章知识表示可解节点•在与/或图中，满足以下三个条件之一的节点为可解节点:•任何终止节点都是可解节点。•对“或”节点，当其子节点中至少有一个为可解节点时，则该“或”节点就是可解节点。•对“与”节点，只有当其子节点全部为可解节点时，该“与”节点才是可解节点。第2章知识表示不可解节点•可用类似的方法定义不可解节点:•不为终止节点的端节点是不可解节点。•对“或”节点，若其全部子节点都为不可解节点，则该“或”节点是不可解节点。•对“与”节点，只要其子节点中有一个为不可解节点，则该“与”节点是不可解节点。第2章知识表示与或图表示举例•例2-4试证明两四边形全等问题T，如图2-9所示，要求用与/或图表示。•证明现假设：•T1：证明△ABD≌△AˊBˊDˊ；•T2：证明△BCD≌△BˊCˊDˊ。•T1又可以等价于三个子问题E1、E2、E3的与，其中•E1：AB=AˊBˊ；E2：AD=AˊDˊ；E3：BD=BˊDˊ。•T2也可以等价三个子问题E3、E4、E5的与，其中•E3：BD=BˊDˊ；E4：BC=BˊCˊ；E5：CD=CˊDˊ。第2章知识表示两全等四边形•图2-10两四边形全等问题d2ˊαˊβ1ˊd1ˊcˊβ2ˊAˊBˊCˊDˊcd2αβ1d1β2ABCD第2章知识表示与/或图表示•图2-11证明四边形全等问题的与/或图T14T11T13T12TT1T2E1E2E3T121T122T123T131T132T141T133T142T143T1211T1212T1213第2章知识表示示例•例试求积分••有两种方法解此积分•1．因为，所以上述积分变为•2．上述积分可按下式变换•••上述两种方法可用下列与/或图如图2-11来描述22)1(12xxxdxxdxdxxxF)1()(dxxdxxxdxxxdxxxxxxdxxxxxF1112111121112)(222dxxxxxF112)(2第2章知识表示与或图表示•图2-11微积分问题的与/或图与节点或节点dxxxx1122dxxx12dxxx12dxx11dxxxxxx111212dxx)1(xdxdxxx21第2章知识表示示例•例2-5分火柴游戏，设堆有7根火柴，由Max（我方）和Min方（对手）两人轮流来分它们，要求每次都要把某堆火柴分成不相等的两部分，最后不能分下去的人为负，对方为胜。如果