湘潭大学人工智能课件知识表示方法part1

ArtificialIntelligence(AI)

人工智能第二章：知识表示与推理ArtificialIntelligence(AI)

人预备知识人类的智能活动过程主要是一个获得并运用知识的过程按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识首先需要明确一下几个问题什么是知识知识的划分人工智能系统中的知识什么是知识表示知识表示方法预备知识人类的智能活动过程主要是一个获得并运用知识的过程知识知识的概念知识的一般概念：知识是人们在改造客观世界的实践中积累起来的认识和经验认识：包括对事物现象、本质、属性、状态、联系等的认识经验：包括解决问题的微观方法和宏观方法微观方法：如步骤、操作、规则、过程、技巧等宏观方法：如战略、战术、计谋、策略等

eg：“if

大雁向南飞，then

冬天就要来临了。”这样一条知识就是人们经过长期的观察，将“大雁向南飞”与“冬天来临”这两条信息关联在一起。“雪是白色的”反映雪与颜色的一种关系。知识的概念知识的一般概念：知识是人们在改造客观世界的实践中积知识的概念知识、信息、数据及其关系数据：是信息的载体，本身无确切含义。如：水的温度是100℃，木头的长度是2米，大楼的高度是100层……信息：是数据的关联，赋予数据特定的含义，仅可理解为描述性知识。数据是没有联系的，孤立的，只有当数据用来描述一个客观事物和客观事物的关系，形成有逻辑的数据流，他们才能被称为信息。知识：可以是对信息的关联，也可以是对已有知识的再认识。如：湘潭7月1日气温为30度，12月1日气温为3度。当对这类信息进行归纳和对比就会发现湘潭每年7月气温比较高，12月气温比较低。于是有价值的信息沉淀并结构化后就形成了知识。知识的概念知识、信息、数据及其关系知识的划分知识的划分按知识的性质：概念、命题、公理、定理、规则和方法按知识的作用域：常识性知识，领域性知识按知识的等级：零级知识：事实性知识。用于描述事物的概念、定义、属性等；或用于描述问题的状态、环境、条件等。一级知识：过程性知识。用于问题求解过程的操作、演算和行为的知识。表示方式：产生式、谓词、语义网络等。二级知识：控制性知识，元知识或超知识。是关于如何使用过程性知识的知识。例如：推理策略、搜索策略、不确定性的传播策略。知识的划分知识的划分知识的划分按知识的层次：表层知识：描述客观事物的现象的知识。例如：感性、事实性知识深层知识：描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性：确定性知识：可以说明其真值为真或为假的知识不确定性知识：包括不精确、模糊、不完备知识不精确：知识本身有真假，但由于认识水平限制却不能肯定知识的真假。表示：用可信度、概率等描述模糊：知识本身的边界就是不清楚的。例如：大，小等。表示：用可能性、隶属度来描述不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病知识的划分按知识的层次：知识的划分按人类的思维及认识方法：逻辑性知识：是反映人类逻辑思维过程的知识，一般具有因果关系或难以精确描述的特点，是人类的经验性知识和直观感觉；如：人的为人处事的经验与风格形象性知识：通过事物的形象建立起来的知识。如:什么是人？按知识的获取方式：显性知识：指可通过文字、语言、图形、声音等形式编码记录和传播的知识；如：教材、音视频光盘。隐性知识：指人们长期实践中积累获得的知识，不易用显性知识表达的知识。如：每个人都有不同的审美观。知识的划分按人类的思维及认识方法：人工智能系统中的知识一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。事实知识：是有关问题环境的一些事物的知识，常以“…是…”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等事实是静态的为人们共享的可公开获得的公认的知识，在知识库中属低层的知识。如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的……规则知识：是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现。人工智能系统中的知识一个智能程序高水平的运行需要有关的事实知人工智能系统中的知识控制知识：是有关问题的求解步骤、技巧的知识，告诉人们怎么做一件事，也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。控制知识常与程序结合在一起出现，如一个问题求解的算法可以看做是一种知识表示。元知识：是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。元知识与控制知识是有重迭的，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改。

人工智能系统中的知识控制知识：是有关问题的求解步骤、技巧的知知识表示知识表示：是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示的要求：表示能力：能否正确、有效地表示问题。包括：表范围的广泛性、领域知识表示的高效性、对非确定性知识表示的支持程度。可利用性：可利用这些知识进行有效推理。包括：对推理的适应性，对高效算法的支持程度。可实现性：要便于计算机直接对其进行处理

可组织性：可以按某种方式把知识组织成某种知识结构可维护性：便于对知识的增、删、改等操作自然性：符合人们的日常习惯可理解性：知识应易读、易懂、易获取等知识表示知识表示：是研究用机器表示知识的可行性、有效性的一般内容提要第二章：知识表示与推理一、知识表示方法二、确定性推理内容提要第二章：知识表示与推理一、知识表示方法二、确定性推理内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3状态空间法人工智能虽然有多个研究领域，而且每个研究领域又各有自己的规律和特点，都可抽象为一个“问题求解”的过程。问题求解过程实际上是一个搜索过程。问题求解技术主要是两个方面：问题的表示求解的方法状态空间法（StateSpaceRepresentation）：

状态空间法就是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的形式化方法，用“状态（state）”和“算符（operator）”来表示问题。状态空间法人工智能虽然有多个研究领域，而且每个研究领域又各有状态空间法状态空间法的三要素(1)状态（state）：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，是表示问题解法中每一步问题状况的数据结构。有序集合中每个元素qi（i=0,1,...,n）为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态。

(2)算符（operator）：使问题从一种状态变化为另一种状态的手段称为操作符或算符。

(3)状态空间方法：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。S：所有可能的问题初始状态集合；F：操作符集合；G：目标状态集合。状态空间法状态空间法的三要素状态空间法状态空间法举例：下棋、迷宫及各种游戏。十五数码难题(15puzzle)：由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。119415131275861321014123456789101112131415初始棋局目标棋局状态空间法状态空间法举例：下棋、迷宫及各种游戏。119415十五数码难题119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014123456789101112131415初始状态目标状态如何把初始棋局变成目标棋局？首先把适用的算符用于初始状态，以产生新的状态再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止十五数码难题119415131275861321014119状态空间法问题的表示对求解工作有很大影响。人们希望有较小的状态空间表示。例如，对于十五数码问题：可以规定15×4＝60条规则“上移棋子1，下移棋子1，左移棋子1，右移棋子1”“上移棋子2，下移棋子2，左移棋子2，右移棋子2”......如果用“上下左右移动空格”，则只需4条规则。所以，移动空格是一种较好的表示。状态空间法问题的表示对求解工作有很大影响。人们希望有较小的状状态空间法状态空间法举例：旅行商问题旅行商问题(TravelingSalesmanProblem，TSP)：假定起始城市为A状态空间法状态空间法举例：旅行商问题假定起始城市为A状态空间法旅行商问题(TravelingSalesmanProblem，TSP)：算符的代价状态空间法旅行商问题(TravelingSalesman状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态图中有几个术语。节点(Node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合。弧线(Arc)：节点间的连接线，表示算符；有向图(DirectedGraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(Descendantnode)与父辈节点(Parentnode)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态图中有几个术语。路径(Path)：某个节点序列(ni1,ni2,…,nik)当j=2,3,…,k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(Cost)：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。图的显示说明/隐示说明：指各节点及其具有代价的弧线可以/不可以由一张表明确给出。显然，显示说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态状态空间法各种问题都可用状态空间加以表示，并用状态空间搜索法来求解。下面简单介绍一种产生式系统（productionsystem）描述的搜索算法。产生式系统（productionsystem）由三部分组成：一个总数据库：0级知识。它含有与具体任务有关的信息。一套规则：1级知识。它对数据库进行操作运算。一个控制策略（程序）：2级知识。它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。状态空间法各种问题都可用状态空间加以表示，并用状态空间搜索法状态空间法状态空间法举例：猴子和香蕉问题：在一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?状态空间法状态空间法举例：猴子和香蕉问题解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态W：猴子的水平位置；x：当猴子在箱子顶上时取1；否则取0；Y：箱子的水平位置；z：当猴子摘到香蕉时取1；否则取0。初始状态为(a,0,b,0)，目标状态为(c,1,c,1)这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置Upushbox（V）猴子把箱子推到水平位置Vclimbbox猴子爬上箱顶grasp猴子摘到香蕉猴子和香蕉问题解题过程猴子和香蕉问题解题过程该初始状态变换为目标状态的操作序列为：Step1:goto(b)Step2:pushbox(c)Step3:climbboxStep4:grasp猴子和香蕉问题解题过程猴子和香蕉问题状态空间图(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=VV=c，climbboxgrasp猴子和香蕉问题状态空间图(b，1，b，0)（U，0，b，0）内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3问题归约法问题归约（ProblemReduction）是另外一种基于状态空间的问题描述与求解方法已知问题的描述，通过一系列变换把此问题变为一个子问题集合这些子问题的解可以直接得到（本原问题），从而解决了初始问题问题归约法问题归约（ProblemReduction）问题归约法问题归约法的组成部分一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。(本原问题:不能再分解或变换且直接可解的子问题)问题归约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题归约为一个本原问题集合。问题归约法问题归约法的组成部分问题归约法问题归约法举例：汉诺塔问题（Hanoi）从1移到3每次移动一个盘子大盘在下小盘在上123CBA初始状态（111）目标状态（333）CBA问题归约法问题归约法举例：123CBA初始状态（111）目标汉诺塔问题原始问题可以归约为下列3个子问题：子问题1：移动圆盘A和B至柱子2（借助柱子3）子问题2：移动圆盘C至柱子3子问题3：把圆盘A和B移至柱子3（借助柱子1）汉诺塔问题原始问题可以归约为下列3个子问题：子问题1：移动圆汉诺塔问题归约过程（3个圆盘）汉诺塔问题归约过程（3个圆盘）汉诺塔问题汉诺塔问题归约图本原问题本原问题与或图CBA汉诺塔问题汉诺塔问题归约图本原问题本原问题与或图CBA问题归约法与或图表示：用一个类似于图的结构来表示,把问题归约为后继问题的替换集合。与图：把一个复杂问题分解为若干个较为简单的子问题，形成“与”树。或图：把原问题变换为若干个较为容易求解的新问题，形成“或”树。问题归约法与或图表示：用一个类似于图的结构来表示,把问题归约问题归约法与或图表示：BCDEFGAHMBCDEFGAN子问题替代集合结构图与或图问题归约法与或图表示：BCDEFGAHMBCDEFGAN子问问题归约法一些关于与或图的术语起始节点对应于原始问题描述终叶节点对应于本原问题问题归约法一些关于与或图的术语起始节点对应于原始问题描述终叶问题归约法与或图的构成规则1）与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题A。2）对应于本原问题的节点称为终叶节点，它没有后继节点。3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合。HMBCDEFGAN问题归约法与或图的构成规则HMBCDEFGAN问题归约法与或图的构成规则4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向次子问题集合中的各个节点。由于只有当集合中所有项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。5）特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3）和规则4）所产生的图可以得到简化。MDEFAADEF简化问题归约法与或图的构成规则MDEFAADEF简化问题归约法与或图的搜索：目的在于表明起始节点是有解的。可解节点终叶节点是可解节点（对应于本原问题）。如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。问题归约法与或图的搜索：目的在于表明起始节点是有解的。问题归约法不可解节点没有后裔的非终叶节点为不可解节点。如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。解树由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。解树中一定包含初始节点，它对应于原始问题。问题归约法不可解节点问题归约法ttttttttt有解节点无解节点终叶节点与或图例子原始问题有一个以上的解原始问题有解问题归约法ttttttttt有解节点无解节点终叶节点与或图例ArtificialIntelligence(AI)

人工智能第二章：知识表示与推理ArtificialIntelligence(AI)

人预备知识人类的智能活动过程主要是一个获得并运用知识的过程按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识首先需要明确一下几个问题什么是知识知识的划分人工智能系统中的知识什么是知识表示知识表示方法预备知识人类的智能活动过程主要是一个获得并运用知识的过程知识知识的概念知识的一般概念：知识是人们在改造客观世界的实践中积累起来的认识和经验认识：包括对事物现象、本质、属性、状态、联系等的认识经验：包括解决问题的微观方法和宏观方法微观方法：如步骤、操作、规则、过程、技巧等宏观方法：如战略、战术、计谋、策略等

eg：“if

大雁向南飞，then

冬天就要来临了。”这样一条知识就是人们经过长期的观察，将“大雁向南飞”与“冬天来临”这两条信息关联在一起。“雪是白色的”反映雪与颜色的一种关系。知识的概念知识的一般概念：知识是人们在改造客观世界的实践中积知识的概念知识、信息、数据及其关系数据：是信息的载体，本身无确切含义。如：水的温度是100℃，木头的长度是2米，大楼的高度是100层……信息：是数据的关联，赋予数据特定的含义，仅可理解为描述性知识。数据是没有联系的，孤立的，只有当数据用来描述一个客观事物和客观事物的关系，形成有逻辑的数据流，他们才能被称为信息。知识：可以是对信息的关联，也可以是对已有知识的再认识。如：湘潭7月1日气温为30度，12月1日气温为3度。当对这类信息进行归纳和对比就会发现湘潭每年7月气温比较高，12月气温比较低。于是有价值的信息沉淀并结构化后就形成了知识。知识的概念知识、信息、数据及其关系知识的划分知识的划分按知识的性质：概念、命题、公理、定理、规则和方法按知识的作用域：常识性知识，领域性知识按知识的等级：零级知识：事实性知识。用于描述事物的概念、定义、属性等；或用于描述问题的状态、环境、条件等。一级知识：过程性知识。用于问题求解过程的操作、演算和行为的知识。表示方式：产生式、谓词、语义网络等。二级知识：控制性知识，元知识或超知识。是关于如何使用过程性知识的知识。例如：推理策略、搜索策略、不确定性的传播策略。知识的划分知识的划分知识的划分按知识的层次：表层知识：描述客观事物的现象的知识。例如：感性、事实性知识深层知识：描述客观事物本质、内涵等的知识。例如：理论知识按知识的确定性：确定性知识：可以说明其真值为真或为假的知识不确定性知识：包括不精确、模糊、不完备知识不精确：知识本身有真假，但由于认识水平限制却不能肯定知识的真假。表示：用可信度、概率等描述模糊：知识本身的边界就是不清楚的。例如：大，小等。表示：用可能性、隶属度来描述不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病知识的划分按知识的层次：知识的划分按人类的思维及认识方法：逻辑性知识：是反映人类逻辑思维过程的知识，一般具有因果关系或难以精确描述的特点，是人类的经验性知识和直观感觉；如：人的为人处事的经验与风格形象性知识：通过事物的形象建立起来的知识。如:什么是人？按知识的获取方式：显性知识：指可通过文字、语言、图形、声音等形式编码记录和传播的知识；如：教材、音视频光盘。隐性知识：指人们长期实践中积累获得的知识，不易用显性知识表达的知识。如：每个人都有不同的审美观。知识的划分按人类的思维及认识方法：人工智能系统中的知识一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元知识。事实知识：是有关问题环境的一些事物的知识，常以“…是…”的形式出现。如事物的分类、属性、事物间关系、科学事实、客观事实等事实是静态的为人们共享的可公开获得的公认的知识，在知识库中属低层的知识。如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的……规则知识：是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现。人工智能系统中的知识一个智能程序高水平的运行需要有关的事实知人工智能系统中的知识控制知识：是有关问题的求解步骤、技巧的知识，告诉人们怎么做一件事，也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。控制知识常与程序结合在一起出现，如一个问题求解的算法可以看做是一种知识表示。元知识：是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。元知识与控制知识是有重迭的，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改。

人工智能系统中的知识控制知识：是有关问题的求解步骤、技巧的知知识表示知识表示：是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示的要求：表示能力：能否正确、有效地表示问题。包括：表范围的广泛性、领域知识表示的高效性、对非确定性知识表示的支持程度。可利用性：可利用这些知识进行有效推理。包括：对推理的适应性，对高效算法的支持程度。可实现性：要便于计算机直接对其进行处理

可组织性：可以按某种方式把知识组织成某种知识结构可维护性：便于对知识的增、删、改等操作自然性：符合人们的日常习惯可理解性：知识应易读、易懂、易获取等知识表示知识表示：是研究用机器表示知识的可行性、有效性的一般内容提要第二章：知识表示与推理一、知识表示方法二、确定性推理内容提要第二章：知识表示与推理一、知识表示方法二、确定性推理内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3状态空间法人工智能虽然有多个研究领域，而且每个研究领域又各有自己的规律和特点，都可抽象为一个“问题求解”的过程。问题求解过程实际上是一个搜索过程。问题求解技术主要是两个方面：问题的表示求解的方法状态空间法（StateSpaceRepresentation）：

状态空间法就是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的形式化方法，用“状态（state）”和“算符（operator）”来表示问题。状态空间法人工智能虽然有多个研究领域，而且每个研究领域又各有状态空间法状态空间法的三要素(1)状态（state）：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，是表示问题解法中每一步问题状况的数据结构。有序集合中每个元素qi（i=0,1,...,n）为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态。

(2)算符（operator）：使问题从一种状态变化为另一种状态的手段称为操作符或算符。

(3)状态空间方法：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。S：所有可能的问题初始状态集合；F：操作符集合；G：目标状态集合。状态空间法状态空间法的三要素状态空间法状态空间法举例：下棋、迷宫及各种游戏。十五数码难题(15puzzle)：由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。119415131275861321014123456789101112131415初始棋局目标棋局状态空间法状态空间法举例：下棋、迷宫及各种游戏。119415十五数码难题119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014123456789101112131415初始状态目标状态如何把初始棋局变成目标棋局？首先把适用的算符用于初始状态，以产生新的状态再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止十五数码难题119415131275861321014119状态空间法问题的表示对求解工作有很大影响。人们希望有较小的状态空间表示。例如，对于十五数码问题：可以规定15×4＝60条规则“上移棋子1，下移棋子1，左移棋子1，右移棋子1”“上移棋子2，下移棋子2，左移棋子2，右移棋子2”......如果用“上下左右移动空格”，则只需4条规则。所以，移动空格是一种较好的表示。状态空间法问题的表示对求解工作有很大影响。人们希望有较小的状状态空间法状态空间法举例：旅行商问题旅行商问题(TravelingSalesmanProblem，TSP)：假定起始城市为A状态空间法状态空间法举例：旅行商问题假定起始城市为A状态空间法旅行商问题(TravelingSalesmanProblem，TSP)：算符的代价状态空间法旅行商问题(TravelingSalesman状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态图中有几个术语。节点(Node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合。弧线(Arc)：节点间的连接线，表示算符；有向图(DirectedGraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点(Descendantnode)与父辈节点(Parentnode)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态图中有几个术语。路径(Path)：某个节点序列(ni1,ni2,…,nik)当j=2,3,…,k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。代价(Cost)：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。图的显示说明/隐示说明：指各节点及其具有代价的弧线可以/不可以由一张表明确给出。显然，显示说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。状态空间法状态图示法：状态空间的图示形式称为状态空间图。状态状态空间法各种问题都可用状态空间加以表示，并用状态空间搜索法来求解。下面简单介绍一种产生式系统（productionsystem）描述的搜索算法。产生式系统（productionsystem）由三部分组成：一个总数据库：0级知识。它含有与具体任务有关的信息。一套规则：1级知识。它对数据库进行操作运算。一个控制策略（程序）：2级知识。它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。状态空间法各种问题都可用状态空间加以表示，并用状态空间搜索法状态空间法状态空间法举例：猴子和香蕉问题：在一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?状态空间法状态空间法举例：猴子和香蕉问题解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态W：猴子的水平位置；x：当猴子在箱子顶上时取1；否则取0；Y：箱子的水平位置；z：当猴子摘到香蕉时取1；否则取0。初始状态为(a,0,b,0)，目标状态为(c,1,c,1)这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置Upushbox（V）猴子把箱子推到水平位置Vclimbbox猴子爬上箱顶grasp猴子摘到香蕉猴子和香蕉问题解题过程猴子和香蕉问题解题过程该初始状态变换为目标状态的操作序列为：Step1:goto(b)Step2:pushbox(c)Step3:climbboxStep4:grasp猴子和香蕉问题解题过程猴子和香蕉问题状态空间图(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=VV=c，climbboxgrasp猴子和香蕉问题状态空间图(b，1，b，0)（U，0，b，0）内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3.谓词逻辑法4.语义网络法5.其他方法一、知识表示方法内容提要第二章：知识表示与推理1.状态空间法2.问题归约法3问题归约法问题归约（ProblemReduction）是另外一种基于状态空间的问题描述与求解方法已知问题的描述，通过一系列变换把此问题变为一个子问题集合这些子问题的解可以直接得到（本原问题），从而解决了初始问题问题归约法问题归约（ProblemReduction）问题归约法问题归约法的组成部分一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。(本原问题:不能再分解或变换且直接可解的子问题)问题归约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直到最后把初始问题归约为一个本原问题集合。问题归约法问题归约法的组成部分问题归约法