知识表示与推理课件

知识表示与推理知识表示与推理1主要内容知识表示及其概念知识表示——状态图（或图）的搜索及问题求解与或图的搜索及问题求解博弈树的搜索及问题求解主要内容知识表示及其概念2知识点或图与或图博弈树搜索策略问题求解盲目搜索启发式搜索希望树问题求解极大极小法α-β剪枝法图搜索知识点或图与或图博弈树搜索策略问题求解盲目搜索启发式搜索希32.1知识的概念费根鲍姆Feigenbaum：知识是经过消减、塑造、解释和转换的信息。Bernstein：知识是由特定领域的描述、关系和过程组成的。Hayes-roth：知识是事实、信念和启发式规则。从知识库的观点看，知识是某领域中所涉及的各有关方面的一种符号表示。2.1知识的概念费根鲍姆Feigenbaum：知识是经过消4知识的分类从不同的角度、不同的侧面对知识有着不同的分类方法。从内容上分：原理（客观）性知识和方法（主观）性知识。原理（客观）性知识具有抽象概括性方法（主观）性知识具有通用性。从形式上分：显示和隐式。从逻辑思维角度分：逻辑型和直觉型知识。从可靠性上分：理论知识和经验知识。知识的分类从不同的角度、不同的侧面对知识有着不同的分类方法5知识的要素事实：事物的分类、属性、事物间关系、科学事实、客观事实等。规则：事物的行动、动作和联系的因果关系知识。控制：当有多个动作同时被激活时，选择哪一个动作来执行的知识。元知识：怎样使用规则、解释规则、校验规则、解释程序结构等知识。知识的要素事实：事物的分类、属性、事物间关系、科学事实、客6知识表示定义知识表示方法是面向计算机的知识描述或表达形式和方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一组事物的约定，以把人类知识表示成机器能处理的数据结构。知识表示定义知识表示方法是面向计算机的知识描述或表达形式和方7知识表示与推理课件82.2状态空间及状态图搜索状态空间及其搜索的表示一般图搜索策略启发式搜索算法2.2状态空间及状态图搜索状态空间及其搜索的表示9状态空间图状态空间图：描述问题的有向图，简称为状态图。状态空间：一个问题的全体状态及其关系所构成的空间。一般都表示为或图。节点：表示状态。节点间的有向弧：表示状态变迁。弧上的标签：表示导致状态转换的规则，称为状态转换规则，也称操作。状态空间图状态空间图：描述问题的有向图，简称为状态图。10状态空间图状态——状态一般用一组数据表示。可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。状态转换规则——可以是某种操作、规则、行为、变换、关系、函数、算子和过程等。状态空间图状态——状态一般用一组数据表示。可通过定义某种数11状态空间图状态图也可以用一个三元组表示：（S，F，G）S：问题的初始状态集合。F：问题的状态转换规则集合。G：问题的目标状态集合。状态空间图状态图也可以用一个三元组表示：（S，F，G）12状态空间图例1迷宫问题显式状态图：写出全部节点和边的状态图。

例2八数码难题隐式状态图：仅写出初始节点和目标节点，其余节点需要用状态转换规则产生的状态图。状态空间图例1迷宫问题13状态图搜索搜索——从初始节点出发，沿着与之相连的边寻找目标节点的过程。解答路径——初-目变迁过程中的状态序列或相应的操作算子调用序列。搜索树（图）——在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。状态图搜索搜索——从初始节点出发，沿着与之相连的边寻找目标14搜索空间示意图搜索空间示意图15状态图搜索（1）求任一解路的搜索策略回溯法（Backtracking）宽(广)度优先法（Breadth-first）深度优先法（Depth-first）限定范围搜索法（BeamSearch）局部择优（爬山法HillClimbing）全局择优搜索（最好的优先法Best-first）状态图搜索（1）求任一解路的搜索策略16状态图搜索（2）求最佳解路的搜索策略大英博物馆法（BritishMuseum）分枝界限法（最小代价优先法BranchandBound）动态规划法（DynamicProgramming）最佳图搜索法（A﹡）状态图搜索（2）求最佳解路的搜索策略17状态图搜索——搜索术语节点深度——搜索图是一种有根图，根节点指示初始状态，令其节点深度为0，则搜索图中的其它节点的深度dn就可递归地定义为其父节点深度dn-1加1：dn=dn-1+1.路径——从节点ni到nk的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。节点扩展——应用转换规则将上一状态（节点ni）变迁到下一状态（节点nj），ni指示被扩展节点，nj即是由ni扩展出的子节点。状态图搜索——搜索术语节点深度——搜索图是一种有根图，根节点18状态图搜索——搜索术语路径代价——相邻节点ni和nj间路径的代价记为C(ni,nj),由两部分组成：路径本身代价——转换规则的执行代价。路径搜索代价——又分为二部分：路径建立代价——从节点ni扩展出节点nj所付出的代价；路径选择代价——选择这条路径作为搜索方向（即选择nj作为下一步搜索起点）所付出的代价。状态图搜索——搜索术语路径代价——相邻节点ni和nj间路径的19状态图搜索——搜索方式树式搜索：在搜索过程中，记录所经过的所有节点和边。线式搜索：在搜索过程中，只记录当前所找路径上的节点和边。状态图搜索——搜索方式树式搜索：在搜索过程中，记录所经过的所20状态图搜索——搜索策略盲目搜索：就是未利用问题的知识，采用固定的方式生成状态的方法。特点：搜索效率是低下的，但方法具有通用性。状态图搜索——搜索策略盲目搜索：就是未利用问题的知识，采用21状态图搜索——搜索策略启发式搜索：利用问题的知识，缩小问题的搜索范围，选择那些最有可能在（最优）解路径上的状态优先搜索，以尽快地找到问题的（最优）解。特点：搜索效率提高。问题：寻找对求解问题有帮助的知识，以及如何利用这些知识。状态图搜索——搜索策略启发式搜索：利用问题的知识，缩小问题22状态图搜索——搜索算法OPEN表和CLOSED表。其中OPEN表记录的是已经被生成出来，但还没有被扩展的节点；CLOSED表记录的是已经被扩展过的节点。OPEN表节点父节点编号

CLOSED表编号节点父节点编号

状态图搜索——搜索算法OPEN表和CLOSED表。其中OPE23状态图搜索——搜索算法①G：＝（＝s），OPEN：＝（s）；G表示图，s为初始节点，设置OPEN表，最初只含初始节点。②CLOSED：＝（）；设置CLOSED表，起始设置为空表。③LOOP：IFOPEN＝（），THENEXIT（FAIL）；④n：＝FIRST（OPEN），REMOVE（n，OPEN），ADD（n，CLOSED）；称n为当前节点。⑤IFGOAL（n），THENEXIT（SUCCESS）；由n返回到s路径上的指针，可给出解路径。⑥EXPAND（n）→{mi}，G：＝ADD（mi，G）；子节点集{mi}中不包含n的父辈节点。状态图搜索——搜索算法①G：＝（＝s），OPEN：＝（s）；24状态图搜索——搜索算法⑦标记和修改指针ADD（mj，OPEN），并标记mj连接到n的指针；mj为OPEN和CLOSED中未出现过的子节点，{mi}＝{mj}∪{mk}∪{ml}。计算是否要修改mk，ml到n的指针；mk为已出现在OPEN中的子节点，ml为已出现在CLOSED中的子节点。计算是否要修改到其后继节点的指针；⑧对OPEN中的节点按某种原则重新排序；⑨GOLOOP；状态图搜索——搜索算法⑦标记和修改指针25状态图搜索——搜索算法mk没被扩展,在OPEN表中.

ml已被扩展,在CLOSED表中.当n被扩展时，它生成了节点mi.mj是新出现的节点.mj状态图搜索——搜索算法mk没被扩展,在OPEN表中.mj26状态图搜索——宽度优先步1、把初始节点S0放入OPEN表中；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，将其所有子节点配上指向N的指针，依次放入OPEN表尾部，转步2。OPEN表是一个队列。状态图搜索——宽度优先步1、把初始节点S0放入OPEN表中；27状态图搜索——宽度优先宽度优先特点当问题有解时，宽度优先算法不但能一定找到解，能找到最优解，盲目性大，可能产生许多无用的中间顶点，效率低。状态图搜索——宽度优先宽度优先特点28状态图搜索——深度优先步1、把初始节点S0放入OPEN表中；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，将其所有子节点配上指向N的指针，依次放入OPEN表首部，转步2。OPEN表是一个栈。状态图搜索——深度优先步1、把初始节点S0放入OPEN表中；29状态图搜索——深度优先深度优先特点效率较高。一般情况下，当问题有解时，不一定能找到解，且解一般不是最优解。如果问题的状态空间是有限的，则可以保证找到解，当问题的状态空间是无限的时，则可能陷入“深渊”，而找不到解。状态图搜索——深度优先深度优先特点30状态图搜索——有界深度优先步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。状态图搜索——有界深度优先步1、把初始节点S0放入OPEN表31状态图搜索——有界深度优先算法：对于深度优先算法中需放入OPEN中的顶点若其深度不超过规定的上界d，则放入OPEN的头部，并为每一个顶点配置指向父顶点的指针。特点：不一定能找到解，且解一般不是最优解。效率较高。关键：d的选择状态图搜索——有界深度优先算法：对于深度优先算法中需放入OP32状态图搜索——启发式搜索启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。目的：引入与应用领域相关的启发式知识来指导OPEN表中节点的排序，使最有希望出现在较短解答路径上的节点优先考察，就能显著提高搜索的有效性。状态图搜索——启发式搜索启发式搜索就是利用知识来引导搜索，达33状态图搜索——启发式搜索启发性信息用途：(1)决定扩展节点的先后顺序；(2)决定生成后续节点的多少；(3)决定删除哪些无用的节点。状态图搜索——启发式搜索启发性信息用途：34状态图搜索——启发式搜索启发函数（Heuristicfunction）启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数，通常记为h(x)。如何定义一个启发函数一个节点处在最佳路径上的概率；求出任意一个节点与目标节点集之间的距离度量或差异度量；根据格局（博弈问题）或状态的特点来打分。即根据问题的启发信息，从概率角度、差异角度或记分法给出计算启发函数的方法。状态图搜索——启发式搜索启发函数（Heuristicfun35状态图搜索——全局择优搜索

对OPEN表中的所有节点排序，使最有希望的节点排在表首。步1、把初始节点S0放入OPEN表中，计算h(S0)；步2、若OPEN表为空，则搜索失败；退出。步3、取OPEN表中第一个节点N放入CLOSED表中，并冠以顺序号n；步4、若目标节点Sg=N，则搜索成功，结束。步5、若N不可扩展，则转步2；步6、扩展N，计算每个子节点的函数值h(x)，将所有子节点配上指向N的指针，依次放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小升序排列，转步2。状态图搜索——全局择优搜索对OPEN表中的所有节点排序，使36状态图搜索——局部择优这是对于上述深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展。步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。状态图搜索——局部择优这是对于上述深度优先法的改进，仅对新37加权状态图加权状态图：具有权值的状态图。代价树：属性的加权状态图。代价：表示两点之间的距离、交通费用或所需的时间。通常用g(x)表示从初始节点S0到节点x的代价，用c(xi,xj)表示父节点xi到子节点xj的代价，即边(xi,xj)的代价。g(xj)=g(xi)+c(xi,xj)g(S0)=0加权状态图加权状态图：具有权值的状态图。38加权状态图搜索——分支界限法分支界限法是优先扩展当前具有最小代价分支路径的端节点n，其启发函数为f(n)=g(n)。算法的基本思想建立一个局部路径（或分支）的队列表，每次都选代价最小的那个分支上的端节点来扩展，直到生成出含有目标节点的路径为止。加权状态图搜索——分支界限法分支界限法是优先扩展当前具有最39加权状态图搜索——最近择优法最近择优法（瞎子爬山法）：类似于局部择优法h(n)。特点：只能向上，不准后退，从而简化了搜索算法；爬山法对于单一极值问题（登单一山峰）十分有效而又简便。对于具有多极值的问题无能为力——会错登上次高峰而失败：不能到达最高峰。加权状态图搜索——最近择优法最近择优法（瞎子爬山法）：类似于40启发式图搜索——估价函数估价函数（Evaluationfunction）估价函数f设计为：f(n)=g(n)+h(n)n——搜索图中的某个当前被扩展的节点；f(n)——从初始状态节点s,经由节点n到达目标节点ng，，估计的最小路径代价；g(n)——从s到n,估计的最小路径代价；h(n)——从n到ng,估计的最小路径代价。启发式图搜索——估价函数估价函数（Evaluationf41启发式图搜索——A算法利用估价函数f（n）＝g（n）＋h（n）来排列OPEN表节点顺序的图搜索算法称为算法A。g(n)值——取至今已发现的自s到n的最短路径.h(n)值——依赖于启发式知识来加以估算.每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。启发式图搜索——A算法利用估价函数f（n）＝g（n）＋h42最佳图搜索算法——A*算法当在算法A的估价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)≤h*(n)时，则我们把这个算法称为算法A*。h*(n)：表示从节点n到目标节点g的最小代价。最佳图搜索算法——A*算法当在算法A的估价函数中，使用的启432.3问题归约法问题归约描述先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.3问题归约法问题归约描述44与或图表示

用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。

与或图表示用一个类似图的结构来表示把问题归约为后继问题的替45与或图搜索与或图基本概念与或图搜索启发式与或树搜索解树代价计算方法最大代价法和代价法与或树的有序搜索与或图搜索与或图基本概念46与或图基本概念与或图：图中既有与关系又有或关系，与关系的边之间用弧线表示，或关系不用弧线表示。与或图与状态图的关系：与或图是状态图的推广，状态图是与或图的特例。解图（解树）：与或图的解是一个图或路径，因此称为解图或解树。即由可解节点形成的一个子图（树）。与或图基本概念与或图：图中既有与关系又有或关系，与关系的边之47与或图基本概念本原问题：直接可解的简单问题。终止节点：本原问题对应的节点称为终止节点。可解的端节点。端节点：无子节点的节点。与节点：一个节点的子节点如果是“与”关系，该节点称为与节点。或节点：一个节点的子节点如果是“或”关系，该节点称为或节点。终止节点和端节点的关系：终止节点一定是端节点，端节点不一定是终止节点。与或图基本概念本原问题：直接可解的简单问题。48与或图搜索——可解性判别节点可解的判断，满足下列条件之一：终止节点是可解的。一个与节点是可解的，当且仅当其子节点全部都可解。一个或节点是可解的，只要其子节点至少有一个可解。与或图搜索——可解性判别节点可解的判断，满足下列条件之一：49与或图搜索——不可解性判别节点不可解的判断，满足下列条件之一：非终止节点是不可解的。一个与节点是不可解的，只要其子节点至少有一个不可解。一个或节点是可解的，当且仅当其子节点全部都不可解。与或图搜索——不可解性判别节点不可解的判断，满足下列条件之一50与或图搜索搜索方式同状态图一样。树式搜索线式搜索与或图搜索搜索方式51与或图搜索——搜索策略盲目搜索穷举搜索深度优先和广度优先盲目碰撞搜索启发式搜索与或图搜索——搜索策略盲目搜索52与或图搜索算法注意：考察节点的可解性。CLOSED表中放的是可解节点。与或图搜索算法注意：53启发式与或树搜索有序搜索根据代价决定搜索路线的方法称为与或树的有序搜索。解树的代价（树根的代价）：从树叶开始自下而上逐层计算。与状态图刚好相反。

启发式与或树搜索有序搜索54解树代价计算方法终止节点的代价为0；或节点的代价为各子节点到该节点的最小代价。与节点的代价有两种计算方法：和代价法：各子节点到该节点的代价之和；最大代价法：各子节点到该节点的最大代价。解树代价计算方法终止节点的代价为0；55启发式与或树搜索——希望树最有希望成为最优解树一部分的节点及其先辈节点所构成的与或树称为希望树。启发式与或树搜索——希望树最有希望成为最优解树一部分的节点及56与或树的有序搜索过程类似于加权状态图中的全局择优搜索法，有两点区别：考察节点的可解性；重新计算代价。与或树的有序搜索过程类似于加权状态图中的全局择优搜索法，有两57博弈博弈的概念极小极大分析法（Minimax）α－β剪枝法（Alpha-betaPruning）博弈博弈的概念58博弈的概念双人对弈，对垒的双方轮流走步。全信息，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。博弈的概念双人对弈，对垒的双方轮流走步。59博弈树的概念描述博弈过程的与或树称为博弈树。特点：博弈的初始格局是初始节点。在博弈中，“或”节点和“与”节点逐层交替出现。自己一方扩展的节点是“或”关系，对方扩展的节点是“与”关系。双方轮流地扩展节点。所有自己一方获胜的终局都是本原问题，相应的节点是可解节点，所有使对方获胜的终局都是不可解节点。博弈树的概念描述博弈过程的与或树称为博弈树。60博弈树的搜索——极小极大分析法（Minimax）极小极大搜索方法是博弈树搜索的基本方法。按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。博弈树的搜索——极小极大分析法（Minimax）极小极大搜索61博弈树的搜索——极小极大分析法（Minimax）从d-1层节点开始逆向计算：对于我方要走的节点（用MAX标记，称为极大节点）取其子节点中的最大值为该节点的值（因为我方总是选择对我方有利的棋）；对于对方要走的节点（用MIN标记，称为极小节点）取其子节点中的最小值为该节点的值（对方总是选择对我方不利的棋）。一直到计算出根节点的值为止。获得根节点取值的那一分枝，即为所选择的最佳走步。

博弈树的搜索——极小极大分析法（Minimax）从d-1层节62博弈树的搜索——极小极大分析法静态估计函数f功能：对棋局的势态（节点）作出优劣估值。定义方法：根据势态优劣特征来定义（主要用于对端节点的“价值”进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值；势均力敌的势态，f（p）取0值；若f（p）＝＋∞，则表示MAX赢；若f（p）＝－∞，则表示MIN赢。博弈树的搜索——极小极大分析法静态估计函数f功能：63博弈树的搜索倒推值计算方法由静态估计函数求得父节点的倒推值方法是：从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。博弈树的搜索倒推值计算方法由静态估计函数求得父节点的倒推值方64极小极大分析法例子——3×3棋盘的一字棋设程序方MAX的棋子用（×）表示，对手MIN的棋子用（○）表示，MAX先走。静态估计函数f(p)规定如下：若p对任何一方来说都不是获胜的格局，则f(p)＝(所有空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角）的总数－(所有空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)若p是MAX获胜的格局，则f(p)＝∞；若p是MIN获胜的格局，则f(p)＝－∞。例如，当p的格局如上时，则可得f(p)＝6－4＝2极小极大分析法例子——3×3棋盘的一字棋设程序方MAX的棋65极小极大分析法例子——3×3棋盘的一字棋第一阶段搜索树极小极大分析法例子——3×3棋盘的一字棋第一阶段66第二阶段搜索树第二阶段搜索树67第三阶段搜索树第三阶段搜索树68博弈树的搜索——α－β剪枝法（Alpha-betaPruning）极小极大搜索方法存在的问题：把搜索树的生成和格局估值这两个过程分开来进行，即先生成全部搜索树，然后再进行端节点静态估值和倒推值计算，这显然会导致低效率。要先生成指定深度以内的所有节点，其节点数将随着搜索深度的增加呈现指数增长的