《知识表示与推理课件.ppt》由会员分享，可在线阅读，更多相关《知识表示与推理课件.ppt（75页珍藏版）》请在三一办公上搜索。
1、知识表示与推理,主要内容,知识表示及其概念知识表示状态图（或图）的搜索及问题求解与或图的搜索及问题求解博弈树的搜索及问题求解,知识点,2.1 知识的概念,费根鲍姆Feigenbaum：知识是经过消减、塑造、解释和转换的信息。Bernstein：知识是由特定领域的描述、关系和过程组成的。Hayes-roth：知识是事实、信念和启发式规则。从知识库的观点看，知识是某领域中所涉及的各有关方面的一种符号表示。,知识的分类,从不同的角度、不同的侧面对知识有着不同的分类方法。从内容上分：原理（客观）性知识和方法（主观）性知识。原理（客观）性知识具有抽象概括性方法（主观）性知识具有通用性。从形式上分：显示和
2、隐式。从逻辑思维角度分：逻辑型和直觉型知识。从可靠性上分：理论知识和经验知识。,知识的要素,事实：事物的分类、属性、事物间关系、科学事实、客观事实等。规则：事物的行动、动作和联系的因果关系知识。控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。,知识表示定义,知识表示方法是面向计算机的知识描述或表达形式和方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组事物的约定，以把人类知识表示成机器能处理的数据结构。,2.2状态空间及状态图搜索,状态空间及其搜索的表示一般图搜索策略启发式搜索
3、算法,状态空间图,状态空间图：描述问题的有向图，简称为状态图。状态空间：一个问题的全体状态及其关系所构成的空间。一般都表示为或图。节点：表示状态。节点间的有向弧：表示状态变迁。弧上的标签：表示导致状态转换的规则，称为状态转换规则，也称操作。,状态空间图,状态状态一般用一组数据表示。可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。状态转换规则可以是某种操作、规则、行为、变换、关系、函数、算子和过程等。,状态空间图,状态图也可以用一个三元组表示：（S，F，G）S：问题的初始状态集合。F：问题的状态转换规则集合。G：问题的目标状态集合。,状态空间图,例1 迷宫问
4、题显式状态图：写出全部节点和边的状态图。例2 八数码难题 隐式状态图：仅写出初始节点和目标节点，其余节点需要用状态转换规则产生的状态图。,状态图搜索,搜索从初始节点出发，沿着与之相连的边寻找目标节点的过程。解答路径初-目变迁过程中的状态序列或相应的操作算子调用序列。搜索树（图）在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。,搜索空间示意图,状态图搜索,（1）求任一解路的搜索策略回溯法（Backtracking）宽(广)度优先法（Breadth-first）深度优先法（Depth-first）限定范围搜索法（Beam Search）局部择优（爬山法Hill Clim
5、bing）全局择优搜索（最好的优先法Best-first）,状态图搜索,（2）求最佳解路的搜索策略大英博物馆法（British Museum）分枝界限法（最小代价优先法Branch and Bound）动态规划法（Dynamic Programming）最佳图搜索法（A）,状态图搜索搜索术语,节点深度搜索图是一种有根图，根节点指示初始状态，令其节点深度为0，则搜索图中的其它节点的深度d n就可递归地定义为其父节点深度d n-1加1：dn=d n-1+1.路径从节点ni到nk的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。节点扩展应用转换规则将上一状态（
6、节点ni）变迁到下一状态（节点nj），ni指示被扩展节点，nj 即是由ni 扩展出的子节点。,状态图搜索搜索术语,路径代价相邻节点ni和nj间路径的代价记为C(ni,nj),由两部分组成：路径本身代价转换规则的执行代价。路径搜索代价又分为二部分：路径建立代价从节点ni 扩展出节点nj 所付出的代价；路径选择代价选择这条路径作为搜索方向（即选择nj作为下一步搜索起点）所付出的代价。,状态图搜索搜索方式,树式搜索：在搜索过程中，记录所经过的所有节点和边。线式搜索：在搜索过程中，只记录当前所找路径上的节点和边。,状态图搜索搜索策略,盲目搜索：就是未利用问题的知识，采用固定的方式生成状态的方法。特点：
7、搜索效率是低下的，但方法具有通用性。,状态图搜索搜索策略,启发式搜索：利用问题的知识，缩小问题的搜索范围，选择那些最有可能在（最优）解路径上的状态优先搜索，以尽快地找到问题的（最优）解。特点：搜索效率提高。问题：寻找对求解问题有帮助的知识，以及如何利用这些知识。,状态图搜索搜索算法,OPEN表和CLOSED表。其中OPEN表记录的是已经被生成出来，但还没有被扩展的节点；CLOSED表记录的是已经被扩展过的节点。,状态图搜索搜索算法,G：（s），OPEN：（s）；G表示图，s为初始节点，设置OPEN表，最初只含初始节点。CLOSED：（）；设置CLOSED表，起始设置为空表。LOOP：IF OP
8、EN（），THEN EXIT（FAIL）；n：FIRST（OPEN），REMOVE（n，OPEN），ADD（n，CLOSED）；称n为当前节点。IF GOAL（n），THEN EXIT（SUCCESS）；由n返回到s路径上的指针，可给出解路径。EXPAND（n）mi，G：ADD（mi，G）；子节点集mi中不包含n的父辈节点。,状态图搜索搜索算法,标记和修改指针ADD（mj，OPEN），并标记mj连接到n的指针；mj为OPEN和CLOSED中未出现过的子节点，mimjmkml。计算是否要修改mk，ml到n的指针；mk为已出现在OPEN中的子节点，ml为已出现在CLOSED中的子节点。计算是否要修
9、改到其后继节点的指针；对OPEN中的节点按某种原则重新排序；GO LOOP；,状态图搜索搜索算法,mk没被扩展,在OPEN表中.ml已被扩展,在CLOSED表中.当n被扩展时，它生成了节点mi.mj是新出现的节点.,mj,状态图搜索宽度优先,步1、把初始节点S0放入OPEN表中；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，将其所有子节点配上指向N的指针，依次放入OPEN表尾部，转步2。OPEN表是一个队列。,状态图搜索宽度优先,宽度优先特点
10、当问题有解时，宽度优先算法不但能一定找到解，能找到最优解，盲目性大，可能产生许多无用的中间顶点，效率低。,状态图搜索深度优先,步1、把初始节点S0放入OPEN表中；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，将其所有子节点配上指向N的指针，依次放入OPEN表首部，转步2。OPEN表是一个栈。,状态图搜索深度优先,深度优先特点效率较高。一般情况下，当问题有解时，不一定能找到解，且解一般不是最优解。如果问题的状态空间是有限的，则可以保证找到解，
11、当问题的状态空间是无限的时，则可能陷入“深渊”，而找不到解。,状态图搜索有界深度优先,步1、把初始节点S0放入OPEN表中；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N的深度d(N)=dm(深度限制值)，或者N不可扩展，则转步2；步6、扩展N，将其所有子节点配上指向N的指针，依次放入OPEN表首部，置d(Ni)=d(N)+1,转步2。,状态图搜索有界深度优先,算法：对于深度优先算法中需放入OPEN中的顶点若其深度不超过规定的上界d，则放入OPEN的头部，并为每一个顶点配置指
12、向父顶点的指针。特点：不一定能找到解，且解一般不是最优解。效率较高。关键：d的选择,状态图搜索启发式搜索,启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。目的：引入与应用领域相关的启发式知识来指导OPEN表中节点的排序，使最有希望出现在较短解答路径上的节点优先考察，就能显著提高搜索的有效性。,状态图搜索启发式搜索,启发性信息用途：(1)决定扩展节点的先后顺序；(2)决定生成后续节点的多少；(3)决定删除哪些无用的节点。,状态图搜索启发式搜索,启发函数（Heuristic function）启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数，通常记为h(x
13、)。如何定义一个启发函数一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算启发函数的方法。,状态图搜索全局择优搜索,对OPEN表中的所有节点排序，使最有希望的节点排在表首。步1、把初始节点S0放入OPEN表中，计算h(S0)；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，计算每个子节点的函数值h(x)，将所有子节
14、点配上指向N的指针，依次放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小升序排列，转步2。,状态图搜索局部择优,这是对于上述深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展。步1、把初始节点S0放入OPEN表中，计算h(S0)；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，计算每个子节点的函数值h(x)，将子节点配上指向N的指针，按其函数值大小升序排列依次放入OPEN表首部，转步2。,加权状
15、态图,加权状态图：具有权值的状态图。代价树：属性的加权状态图。代价：表示两点之间的距离、交通费用或所需的时间。通常用g(x)表示从初始节点S0到节点x的代价，用c(xi,xj)表示父节点xi到子节点xj的代价，即边(xi,xj)的代价。g(xj)=g(xi)+c(xi,xj)g(S0)=0,加权状态图搜索分支界限法,分支界限法是优先扩展当前具有最小代价分支路径的端节点n，其启发函数为f(n)=g(n)。算法的基本思想建立一个局部路径（或分支）的队列表，每次都选代价最小的那个分支上的端节点来扩展，直到生成出含有目标节点的路径为止。,加权状态图搜索最近择优法,最近择优法（瞎子爬山法）：类似于局部择
16、优法h(n)。特点：只能向上，不准后退，从而简化了搜索算法；爬山法对于单一极值问题（登单一山峰）十分有效而又简便。对于具有多极值的问题无能为力会错登上次高峰而失败：不能到达最高峰。,启发式图搜索 估价函数,估价函数（Evaluation function）估价函数f设计为：f(n)=g(n)+h(n)n 搜索图中的某个当前被扩展的节点；f(n)从初始状态节点s,经由节点n到达目标节点ng，估计的最小路径代价；g(n)从s到n,估计的最小路径代价；h(n)从n到ng,估计的最小路径代价。,启发式图搜索 A算法,利用估价函数f（n）g（n）h（n）来排列OPEN表节点顺序的图搜索算法称为算法A。g
17、(n)值取至今已发现的自s到n的最短路径.h(n)值依赖于启发式知识来加以估算.每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。,最佳图搜索算法A*算法,当在算法A的估价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)h*(n)时，则我们把这个算法称为算法A*。h*(n)：表示从节点n到目标节点g的最小代价。,2.3问题归约法,问题归约描述先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解
18、答。问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,与或图表示,用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。,与或图搜索,与或图基本概念与或图搜索启发式与或树搜索解树代价计算方法最大代价法和代价法与或树的有序搜索,与或图基本概念,与或图：图中既有与关系又有或关系，与关系的边之间用弧线表示，或关系不用弧线表示。与或图与状态图的关系：与或图是状态图的推广，状态图是与或图的特例
19、。解图（解树）：与或图的解是一个图或路径，因此称为解图或解树。即由可解节点形成的一个子图（树）。,与或图基本概念,本原问题：直接可解的简单问题。终止节点：本原问题对应的节点称为终止节点。可解的端节点。端节点：无子节点的节点。与节点：一个节点的子节点如果是“与”关系，该节点称为与节点。或节点：一个节点的子节点如果是“或”关系，该节点称为或节点。终止节点和端节点的关系：终止节点一定是端节点，端节点不一定是终止节点。,与或图搜索可解性判别,节点可解的判断，满足下列条件之一：终止节点是可解的。一个与节点是可解的，当且仅当其子节点全部都可解。一个或节点是可解的，只要其子节点至少有一个可解。,与或图搜索不
20、可解性判别,节点不可解的判断，满足下列条件之一：非终止节点是不可解的。一个与节点是不可解的，只要其子节点至少有一个不可解。一个或节点是可解的，当且仅当其子节点全部都不可解。,与或图搜索,搜索方式同状态图一样。树式搜索线式搜索,与或图搜索搜索策略,盲目搜索穷举搜索深度优先和广度优先盲目碰撞搜索启发式搜索,与或图搜索算法,注意：考察节点的可解性。CLOSED表中放的是可解节点。,启发式与或树搜索,有序搜索根据代价决定搜索路线的方法称为与或树的有序搜索。解树的代价（树根的代价）：从树叶开始自下而上逐层计算。与状态图刚好相反。,解树代价计算方法,终止节点的代价为0；或节点的代价为各子节点到该节点的最小
21、代价。与节点的代价有两种计算方法：和代价法：各子节点到该节点的代价之和；最大代价法：各子节点到该节点的最大代价。,启发式与或树搜索希望树,最有希望成为最优解树一部分的节点及其先辈节点所构成的与或树称为希望树。,与或树的有序搜索过程,类似于加权状态图中的全局择优搜索法，有两点区别：考察节点的可解性；重新计算代价。,博弈,博弈的概念极小极大分析法（Minimax）剪枝法（Alpha-beta Pruning）,博弈的概念,双人对弈，对垒的双方轮流走步。全信息，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均
22、无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。,博弈树的概念,描述博弈过程的与或树称为博弈树。特点：博弈的初始格局是初始节点。在博弈中，“或”节点和“与”节点逐层交替出现。自己一方扩展的节点是“或”关系，对方扩展的节点是“与”关系。双方轮流地扩展节点。所有自己一方获胜的终局都是本原问题，相应的节点是可解节点，所有使对方获胜的终局都是不可解节点。,博弈树的搜索极小极大分析法（Minimax）,极小极大搜索方法是博弈树搜索的基本方法。按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。,博弈树的搜索极小极大分析法（Minimax）,从d-1层节点开始逆向计算：对
23、于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。,博弈树的搜索极小极大分析法静态估计函数f,功能：对棋局的势态（节点）作出优劣估值。定义方法：根据势态优劣特征来定义（主要用于对端节点的“价值”进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值；势均力敌的势态，f（p）取0值；若f（p），则表示MAX赢；若
24、f（p），则表示MIN赢。,博弈树的搜索倒推值计算方法,由静态估计函数求得父节点的倒推值方法是：从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。,极小极大分析法例子33棋盘的一字棋,设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。静态估计函数f(p)规定如下：若p对任何一方来说都不是获胜的格局，则f(p)(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角）的总数(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)若p是MAX获胜的格局，则f(p)；若p是MIN获胜的格局，则f(p)。例如，当p的格局如上时，则可得f(p)6
25、42,极小极大分析法例子33棋盘的一字棋,第一阶段搜索树,第二阶段搜索树,第三阶段搜索树,博弈树的搜索剪枝法（Alpha-beta Pruning）,极小极大搜索方法存在的问题：把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加呈现指数增长的趋势。这极大地限制了极小极大搜索方法的使用。剪枝法（Alpha-beta Pruning）在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数。,博弈树的搜索剪枝法（Alpha-beta Pruning）,剪枝(与节点
26、)：若任一极小值层节点的值小于或等于它任一先辈极大值居节点的值，即（先辈层）（后继层），则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个值。剪枝（或节点）：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）（先辈层），则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个值。,博弈树的搜索剪枝法,一字棋的例子来说明-剪枝方法,博弈树的搜索剪枝法（Alpha-beta Pruning）,应注意以下几个问题：比较都是在极小节点和极大节点间进行的，极大节点和极大节点的比较，或者极小节点和极小节点间的比较
27、是无意义的。在比较时注意是与先辈层节点比较，不只是与父辈节点比较。当然，这里的先辈层节点，指的是那些已经有了值的节点。当只有一个节点的固定以后，其值才能够向其父节点传递。-剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，-剪枝并没有因为提高效率，而降低得到最佳走步的可能性。,博弈树的搜索剪枝法（Alpha-beta Pruning）,实际程序实现方法：首先规定一个搜索深度；然后按照类似于深度优先搜索的方式，生成节点；在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。,博弈树的搜索剪枝法（Alpha-beta Pruning）,博弈树搜索的目标找到当前棋局的一步走法，所以-剪枝搜索的结果是得到了一步最佳走步，而不是象一般的图搜索或者与或图搜索那样，得到的是从初始节点到目标节点（集）的一条路径或者解图。,博弈树的搜索剪枝法,
