人工智能及其应用2(蔡自兴)78

1第二章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结22.1状态空间法（StateSpaceRepresentation）问题求解技术主要是两个方面：–问题的表示–求解的方法状态空间法–状态（state）:表示问题解法中每一步问题状况的数据结构–算符（operator):把问题从一种状态变换为另一种状态的手段–状态空间方法:基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的32.1.1问题状态描述定义–状态(State)：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。–算符(Operate)：使问题从一种状态变化为另一种状态的手段称为操作符或算符。–问题的状态空间(StateSpace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1状态空间法4状态空间表示概念详释状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的实验序列，直到达到目标状态止。例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1状态空间法……5例:三数码难题（3puzzleproblem）123123123312312312初始棋局目标棋局2.1状态空间法6有向图一对节点用弧线连接起来，从一个节点指向另一个节点这种图叫做有向图。路径某个节点序列（ni1，ni2，…，nik）当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点ni，j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径代价用c（ni，nj）来表示从节点ni指向节点nj的那段弧线的代价。两点间路径的代价等于连接该路径上各节点的所有弧线代价之和.2.1.2状态图示法2.1状态空间法AB7图的显示说明对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价(举例：邻接表，邻接矩阵)图的隐示说明说明节点的无限集合｛si｝作为起始节点是已知的。后继节点算符Γ（gamma）也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。（举例：棋局）表示方法的多样性如十五数码难题中–规则1：移动数码（15X4条规则）–规则2：移动空格（4条规则）8产生式系统搜索过程描述产生式系统（productionsystem）–一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。–一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。–一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1状态空间法9状态空间表示实例（1）例：猴子和香蕉问题2.1状态空间法10解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态.–W猴子的水平位置–x当猴子在箱子顶上时取x=1；否则取x=0–Y箱子的水平位置–z当猴子摘到香蕉时取z=1；否则取z=0这个问题的操作（算符）如下：–goto（U）表示猴子走到水平位置U–或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1状态空间法11pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）提问：应用算符climbbox的先决条件是什么？2.1状态空间法12grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）令初始状态为(a，0，b，0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图，如下图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为{goto(b),pushbox(c),climbbox,grasp}2.1状态空间法13(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图goto（U）U=V2.1状态空间法14猴子和香蕉问题自动演示：•猴子香蕉箱子•猴子香蕉箱子••••••••••Ha!Ha!2.1状态空间法15状态空间表示实例（2）推销员旅行问题一个推销员计划出访推销产品。他从一个城市(如A)出发,访问每个城市一次,且最多一次,然后A返回城市A。要求寻找最短路线,如图2.3所示。为了确定这个问题,作如下规定:(1)总数据库是到目前为止所访问过的城市表.初始数据库被描述为表(A)。不允许目录表中任一城市出现多于一次,只有城市A例外,但也只有当所有其他城市均已出现之后,才能再次出现A。(2)规则对应于决策:即下一步走向城市A;下一步走向城市B;……;下一步走向城市E。一条规则除非能够把某个数据库变为一个合法数据库,否则就不适用于这个数据库。例如,应用下一步走向城市A这条规则就不适用于尚未出现所有其他城市的任一数据库。(3)任一以A为起点和终点,并出现所有其他城市的总数据库,都满足终止条件。可以使用下图的距离图表来计算任一旅程的总距离。提出作为解答的任一旅程,必须是具有最短距离的旅程。2.1状态空间法16ABDE(ACDEBA)推销员旅行问题状态空间图(A)起始节点2.1状态空间法172.2问题归约法（ProblemReductionRepresentation）问题归约法思想先把问题分解为子问题及子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答子问题1子问题n原始问题子问题集本原问题18问题归约表示的组成部分：–（1）一个初始问题描述；–（2）一套把问题变换为子问题的操作符；–（3）一套本原问题描述。问题归约的实质：–从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2问题规约法192.2.1问题归约描述（ProblemReductionDescription）梵塔难题123CBA2.2问题规约法思考：用状态空间法有多少个节点？为什么？20解题过程将原始问题归约为一个较简单问题集合将原始梵塔难题归约（简化）为下列子难题–移动圆盘A和B至柱子2的双圆盘难题–移动圆盘C至柱子3的单圆盘难题–移动圆盘A和B至柱子3的双圆盘难题详细过程参看下图21解题过程（3个圆盘问题）1231231231231231231232.2问题规约法12322梵塔问题归约图2.2问题规约法23多圆盘梵塔难题思考？2.2问题规约法24问题归约的描述问题归约方法应用算符把问题描述转化为子问题描述，可以采用各种数据结构：表列、树、字符串、矢量、数组等；–例如梵塔问题的表示：包含两个数列的表列：[(113),(333)]也可以用状态空间表示法的三元组（S，F，G）表示；其子问题描述规定了最后解答路径将要通过的中间状态；可以把问题归约发看成比状态空间法更通用的问题求解方法；其核心实现是不断简化问题，直至问题成为本原问题（已知问题、易解问题）；2.2问题规约法252.2.2与或图表示1.与图、或图、与或图一般，我们用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归约图，或叫与或图。如下所示2.2问题规约法ABCD与图ABC或图262.2问题规约法BCDEFGAHMBCDEFGAN•与或图增加附加节点后的规范化与或图表示：272.一些关于与或图的术语2.2问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点28一些关于与或图的术语父节点、子（后继）节点、弧线起始节点终叶节点：对应于原问题的本原节点或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B，C）和（D，E，F）。各个节点之间用一端小圆弧连接标记。与或图：由与节点及或节点组成的结构图。2.2问题规约法293.定义可解节点的一般定义：•终叶节点是可解节点(因为它们与本原问题相关连)。：•如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。•如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。2.2问题规约法30不可解节点的一般定义：没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。2.2问题规约法31如图所示2.2问题规约法与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点32与或图构成规则（1）与或图中的每个节点代表一个要解决的单一问题或问题集合。起始节点对应于原始问题。（2）对应于本原问题的节点，叫做终叶节点（3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点，表示所求得的子问题集合，只要其中任意一个有解，问题A就可解，所有这些子问题节点称为或节点；（4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点,只有所有子问题都有解，这个子问题的集合才有解，所有这些子问题节点叫做与节点。这些具有共同父节点的与节点用小圆弧连接，以表示与或节点的区别；（5）在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。（即不增加附加节点的情况下）2.2问题规约法33梵塔问题归约图（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.2问题规约法•数据结构介绍•思考题：四圆盘问题342.3谓词逻辑法(PredicateLogic)逻辑语句：一种形式语言，它能够把逻辑论证符号化，并用于证明定理，求解问题。形式语言：严格地按照相关领域的特定规则，以数学符号（符号串）形式描述该领域有关客体的表达式2.3.1谓词演算语法与语义–基本符号：谓词符号、变量符号、函数符号、常量符号、括号和逗号–谓词演算的解释：•谓词符号——对应关系，•常量符号——论域实体，•函数符号——对应函数；35–原子公式：由若干谓词符号和项组成的谓词演算。原子公式是谓词演算基本积木块。项包括常量符号、变量符号、函数符号等。定义原子公式为真值或假值就表示了某种语义。–无变量的原子公式取值确定，包含变量的原子公式取值不定。–例如：•INROOM（ROBOT，r1）为真•INROOM（ROBOT，r2）为假•MARRIED[father(wang),mother(wang)]2.3谓词逻辑法36连词和量词(Connective&Quantifiers)–连词与、合取（conjunction)：用连词∧把几个公式连接起来而构成的公式。合取项是合取式的每个组成部分。例：LIKE(I，MUSIC)∧LIKE(I，PAINTING)（我喜