《人工智能第二章.ppt》由会员分享，可在线阅读，更多相关《人工智能第二章.ppt（156页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人人工工智智能能原原理理ArtificialIntelligencePrinciple 信息工程学院信息工程学院张永梅张永梅1第二章第二章知识表示方法知识表示方法2.1知识表示概述知识表示概述2.2状态空间法状态空间法2.3问题归约法问题归约法2.4产生式表示法产生式表示法2.5谓词逻辑法谓词逻辑法2.6语义网络法语义网络法2.7框架表示框架表示2.8剧本（脚本）表示剧本（脚本）表示2.9其他方法其他方法2第二章第二章知识表示方法知识表示方法作业：作业：2-1，2-2，2-8，2-93第二章第二章知识表示方法知识表示方法实验：实验：实验实验1：梵塔问题实验。熟悉和掌握问题规约法的原梵塔问题实验
2、。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法。理、实质和规约过程；理解规约图的表示方法。实验实验2：机器人简单行为实验。掌握谓词逻辑的表达机器人简单行为实验。掌握谓词逻辑的表达方法，了解机器人（或机械手）的状态、条件、动作方法，了解机器人（或机械手）的状态、条件、动作或行为等处理流程。或行为等处理流程。实验实验3：从前有一条河，河的左岸有从前有一条河，河的左岸有m个传教士、个传教士、m个个野人和一艘最多可乘野人和一艘最多可乘n人的小船。约定左岸，右岸和船人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野上或者没有传教士，或者野人数量少于传教士，否
3、则野人会把传教士吃掉。搜索一条可使所有的野人和传教士人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。安全渡到右岸的方案。4联系方式联系方式 电子邮件电子邮件：联系方式联系方式：1381084203752.1知识表示知识表示(KnowledgeRepresentation)概述概述 按照符号主义的观点，知识是一切智能行为的基按照符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首先必须使它拥有知识。础，要使计算机具有智能，首先必须使它拥有知识。知识表示是人工智能研究中最基本的问题之一。知识表示是人工智能研究中最基本的问题之一。在知识处理中总要问到：在知识处理中总要
4、问到：“如何表示知识？如何表示知识？”，“知识是用什么来表示的知识是用什么来表示的?”。怎样使机器能。怎样使机器能懂，能对之进行处理，并能以一种人类能理懂，能对之进行处理，并能以一种人类能理解的方式将处理结果告诉人们。解的方式将处理结果告诉人们。在在AI系统中，给出一个清晰简洁的描述是很系统中，给出一个清晰简洁的描述是很困难的。有研究报道认为，严格地说困难的。有研究报道认为，严格地说AI对知对知识表示的认真、系统的研究才刚刚开始。识表示的认真、系统的研究才刚刚开始。6知识的定义知识的定义难以给出明确的定义只能从不同侧面加以理解。难以给出明确的定义只能从不同侧面加以理解。lFeigenbaum：
5、知识是经过消减、塑造、解释和知识是经过消减、塑造、解释和转换的信息。转换的信息。lBernstein：知识是由特定领域的描述、关系和知识是由特定领域的描述、关系和过程成的。过程成的。lHayes-roth：知识是事实、信念和启发式规则。知识是事实、信念和启发式规则。l知识库的观点：知识库的观点：知识是某领域中所涉及的各有知识是某领域中所涉及的各有关方面的一种符号表示。关方面的一种符号表示。7知识的类型知识的类型v按知识的性质按知识的性质概念、命题、公理、定理、规则和方法。概念、命题、公理、定理、规则和方法。v按知识的作用域按知识的作用域常识性知识：常识性知识：通用通识的知识。人们普遍知道的、通
6、用通识的知识。人们普遍知道的、适应所有领域的知识。适应所有领域的知识。领域性知识：领域性知识：面向某个具体专业领域的知识。面向某个具体专业领域的知识。例例如：如：专家经验。专家经验。8知识的种类知识的种类v事实性知识事实性知识：采用直接表示的形式。：采用直接表示的形式。如：凡是猴子都有尾巴如：凡是猴子都有尾巴v过程性知识过程性知识：描述做某件事的过程。：描述做某件事的过程。如：电视维修法如：电视维修法v控制性知识：控制性知识：(元知识或超知识元知识或超知识)：是关于：是关于如何使用过程性知识的知识。如何使用过程性知识的知识。如：推理策略、搜索策略、不确定性的传播策略。如：推理策略、搜索策略、不
7、确定性的传播策略。9v按知识的层次按知识的层次表层知识：表层知识：描述客观事物的现象的知识。例如：感描述客观事物的现象的知识。例如：感性、事实性知识性、事实性知识深层知识：深层知识：描述客观事物本质、内涵等的知识。例描述客观事物本质、内涵等的知识。例如：理论知识如：理论知识知识的种类知识的种类v按知识的等级按知识的等级零级知识：零级知识：叙述性知识叙述性知识一级知识：一级知识：过程性知识过程性知识二级知识：二级知识：控制性知识（元知识或超知识）控制性知识（元知识或超知识）10v按知识的确定性按知识的确定性确定性知识：确定性知识：可以说明其真值为真或为假的知识可以说明其真值为真或为假的知识不确定
8、性知识：不确定性知识：包括不精确、模糊、不完备知识包括不精确、模糊、不完备知识不精确：不精确：知识本身有真假，但由于认识水平限制却不能肯定知识本身有真假，但由于认识水平限制却不能肯定其真假其真假表示：表示：用可信度、概率等描述用可信度、概率等描述知识的种类知识的种类模糊：模糊：知识本身的边界就是不清楚的。例如：大，小等知识本身的边界就是不清楚的。例如：大，小等表示：表示：用可能性、隶属度来描述用可能性、隶属度来描述不完备：不完备：解决问题时不具备解决该问题的全部知识。例如：解决问题时不具备解决该问题的全部知识。例如：医生看病医生看病11知识的要素知识的要素v事实事实：事物的分类、属性、事物间关
9、系、科学：事物的分类、属性、事物间关系、科学事实、客观事实等。（最低层的知识）事实、客观事实等。（最低层的知识）v规则规则：事物的行动、动作和联系的因果关系知：事物的行动、动作和联系的因果关系知识。（启发式规则）。识。（启发式规则）。v元知识元知识：当有多个动作同时被激活时，选择：当有多个动作同时被激活时，选择哪一个动作来执行的知识。（高层知识）哪一个动作来执行的知识。（高层知识）12知识表示的定义知识表示的定义v知识表示研究用机器表示知识的可行性、有效知识表示研究用机器表示知识的可行性、有效性的一般方法。性的一般方法。v是一种数据结构与控制结构的统一体，既考虑是一种数据结构与控制结构的统一体
10、，既考虑知识的存储又考虑知识的使用。知识的存储又考虑知识的使用。v知识表示可看成是一组描述事物的约定，以把知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。人类知识表示成机器能处理的数据结构。13知识表示研究的特点知识表示研究的特点v智能行为特有的灵活性。智能行为特有的灵活性。“常识问题常识问题”不能概括不能概括为一类简洁的理论，是大量小理论的集合。为一类简洁的理论，是大量小理论的集合。vAI的任务受到计算装置的约束。这导致了所采的任务受到计算装置的约束。这导致了所采用的用的“表示表示”必须同时满足必须同时满足“刻画智能现象刻画智能现象”与与“计算装置可以接受计算装置
11、可以接受”，这两个有时是矛盾的条，这两个有时是矛盾的条件。件。14第二章第二章知识表示方法知识表示方法2.1知识表示概述知识表示概述2.2状态空间法状态空间法2.3问题归约法问题归约法2.4产生式表示法产生式表示法2.5谓词逻辑法谓词逻辑法2.6语义网络法语义网络法2.7框架表示框架表示2.8剧本表示剧本表示2.9其他方法其他方法152.2状态空间法状态空间法（StateSpaceRepresentation）l问题求解技术主要是两个方面：问题求解技术主要是两个方面：问题的表示问题的表示求解的方法求解的方法l状态空间法状态空间法状态状态（state）算符算符（operator）状态空间方法状态
12、空间方法162.2.1问题状态描述问题状态描述v定义定义v状态：状态：描述某类不同事物间的差别而引入的描述某类不同事物间的差别而引入的一组最少变量一组最少变量q0，q1，qn的有序集合。的有序集合。v算符：使问题从一种状态变化为另一种状态算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。的手段称为操作符或算符。v问题的状态空间：问题的状态空间：是一个表示该问题全部可是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集能状态及其关系的图，它包含三种说明的集合，即三元状态合，即三元状态（S，F，G）。2.2 2.2 状态空间法状态空间法所有可能的问题初始状态集合所有可能的问题初
13、始状态集合S、操作、操作符集合符集合F以及目标状态集合以及目标状态集合G。17状态空间表示概念详释状态空间表示概念详释v例如下棋、迷宫及各种游戏。例如下棋、迷宫及各种游戏。2.2 2.2 状态空间法状态空间法18例例:三数码难题三数码难题（3puzzleproblem）2.2 2.2 状态空间法状态空间法192.2 2.2 状态空间法状态空间法实例：十五数码难题（实例：十五数码难题（15puzzleproblem）初始状态初始状态目标状态目标状态202.2 2.2 状态空间法状态空间法v状态空间法状态空间法从某个初始状态开始，每次增加一个从某个初始状态开始，每次增加一个操作符，递增地建立起操作
14、符的试验序列，操作符，递增地建立起操作符的试验序列，直到达到目标状态止。直到达到目标状态止。212.2 2.2 状态空间法状态空间法v总结总结完成问题的状态描述要做三件事：完成问题的状态描述要做三件事：（1）初始状态的描述）初始状态的描述（2）操作符集合及其对状态改变的作用）操作符集合及其对状态改变的作用（3）目标状态的描述）目标状态的描述22v有向图有向图v路径路径v代价代价v图的显示说明图的显示说明v图的隐示说明图的隐示说明2.2.2状态图示法状态图示法AB2.2 2.2 状态空间法状态空间法232.2.2状态图示法状态图示法2.2 2.2 状态空间法状态空间法图图由节点由节点(不一定是有
15、限的节点不一定是有限的节点)的集合构成。一对节点用弧的集合构成。一对节点用弧线连接起来，从一个节点指向另一个节点。这种图叫做线连接起来，从一个节点指向另一个节点。这种图叫做有向图有向图(directedgraph)。某个节点序列某个节点序列(ni1,ni2,nik)，当，当j=2,3,k时，如果对于每一时，如果对于每一个个ni,j-1都有一个后继节点都有一个后继节点nij存在，那么就把这个节点序列叫做存在，那么就把这个节点序列叫做从节点从节点ni1至节点至节点nik的长度为的长度为k-1的的路径路径。代价代价(cost)是给各弧线指定数值以表示加在相应算符上的代是给各弧线指定数值以表示加在相应
16、算符上的代价。价。图的显式说明图的显式说明是指各节点及其具有代价的弧线由一张表明确是指各节点及其具有代价的弧线由一张表明确给出。给出。图的隐式说明图的隐式说明是指各节点及其具有代价的弧线不能由一张表是指各节点及其具有代价的弧线不能由一张表明确给出。明确给出。242.2.3状态空间表示举例状态空间表示举例v产生式系统产生式系统（productionsystem）v一个总数据库：一个总数据库：它含有与具体任务有关的信息它含有与具体任务有关的信息。随着随着应用情况的不同，这些数据库可能简单，或许复杂应用情况的不同，这些数据库可能简单，或许复杂。2.2 2.2 状态空间法状态空间法v一套规则：一套规则
17、：它对数据库进行操作运算。每条规则由左部它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。所完成的动作。v一个控制策略：一个控制策略：它确定应该采用哪一条适用规则，而它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。且当数据库的终止条件满足时，就停止计算。25 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题例：猴子和香蕉问题2.2 2.2 状态空间法状态空间法26解题过程解题过程v 用一个四元表列用一个四元表列（W，x，Y，z）来表示来表示这个问题状态。这个问题状态。2
18、.2 2.2 状态空间法状态空间法v其中：其中：W猴子的水平位置猴子的水平位置x当猴子在箱子顶上时取当猴子在箱子顶上时取x=1；否则取；否则取x=0Y箱子的水平位置箱子的水平位置z当猴子摘到香蕉时取当猴子摘到香蕉时取z=1；否则取；否则取z=0272.2 2.2 状态空间法状态空间法v这个问题中的操作（算符）如下：这个问题中的操作（算符）如下：1、goto（U）猴子走到水平位置猴子走到水平位置U，表示为，表示为goto(U)（W，0，Y，z）-（U，0，Y，z）即把状态（即把状态（W，0，Y，z）变换为状态（）变换为状态（U，0，Y，z）。）。2、pushbox（V）猴子把箱子推到水平位置猴子
19、把箱子推到水平位置V，即有，即有pushbox(V)（W，0，W，z）-（V，0，V，z）条件：猴子与箱子必须在同一位置上，并且，猴子不条件：猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。是在箱子顶上。282.2 2.2 状态空间法状态空间法v3、climbbox猴子爬上箱顶猴子爬上箱顶，即有，即有climbbox（W，0，W，z）-（W，1，W，z）条件：猴子和箱子应当在同一位置上，而且猴子不在条件：猴子和箱子应当在同一位置上，而且猴子不在箱顶上。箱顶上。v4、grasp猴子摘到香蕉猴子摘到香蕉，即有，即有grasp（c，1，c，0）-（c，1，c，1）条件：猴子和箱子都在位置条件：
20、猴子和箱子都在位置c上，并且猴子已在箱子上，并且猴子已在箱子顶上。顶上。其中，其中，c是香蕉正下方的地板位置，是香蕉正下方的地板位置，该初始状态变换为目标状态的操作序列为：该初始状态变换为目标状态的操作序列为：goto(b),pushbox(c),climbbox,grasp29 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题例：猴子和香蕉问题2.2 2.2 状态空间法状态空间法30解题过程解题过程v 用一个四元表列用一个四元表列（W，x，Y，z）来表示来表示这个问题状态。这个问题状态。2.2 2.2 状态空间法状态空间法v其中：其中：W猴子的水平位置猴子的水平位置x当猴子在箱子顶上时取
21、当猴子在箱子顶上时取x=1；否则取；否则取x=0Y箱子的水平位置箱子的水平位置z当猴子摘到香蕉时取当猴子摘到香蕉时取z=1；否则取；否则取z=031猴子与香蕉问题状态空间图猴子与香蕉问题状态空间图32猴子和香蕉问题自动演示：猴子和香蕉问题自动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.2 2.2 状态空间法状态空间法33第二章第二章知识表示方法知识表示方法2.1知识表示概述知识表示概述2.2状态空间法状态空间法2.3问题归约法问题归约法2.4产生式表示法产生式表示法2.5谓词逻辑法谓词逻辑法2.6语义网络法语义网络法2.7框架表示框架表示2.8剧本表示剧本表示2.
22、9其他方法其他方法342.3问题归约法问题归约法（ProblemReductionRepresentation）子问题子问题1子问题子问题n原始问题原始问题子问题集子问题集本本原原问问题题35v 问题归约表示问题归约表示法法的组成部分：的组成部分：l一个初始问题描述；一个初始问题描述；l一套把问题变换为子问题的操作符；一套把问题变换为子问题的操作符；l一套本原问题描述。一套本原问题描述。v问题归约的实质：问题归约的实质：v从目标从目标(要解决的问题要解决的问题)出发逆向推理，建立子问出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题以及子问题的子问题，直至最后把初始问题归题归约为一
23、个平凡的本原问题集合。约为一个平凡的本原问题集合。2.3 2.3 问题规约法问题规约法362.3 2.3 问题规约法问题规约法vv梵塔问题梵塔问题梵塔问题梵塔问题 相传印度教的天神梵天在创造地球这一世界时，建了一相传印度教的天神梵天在创造地球这一世界时，建了一座神庙，神庙里竖有三根宝石柱子，柱子由一个铜座支撑。座神庙，神庙里竖有三根宝石柱子，柱子由一个铜座支撑。梵天将梵天将64个直径大小不一的金盘子，按照从大到小的顺序依个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，即所谓的次套放在第一根柱子上，形成一座金塔，即所谓的梵塔梵塔(又又称称汉诺塔汉诺塔)。天神让庙里
24、的僧侣们将第一根柱子上的。天神让庙里的僧侣们将第一根柱子上的64个盘个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下同时定下3条规则：条规则：(1)每次只能移动一个盘子；每次只能移动一个盘子；(2)盘子只能在三根柱子上来回移动，不能放在他处；盘子只能在三根柱子上来回移动，不能放在他处；(3)在移动过程中，三根柱子上的盘子必须始终保持大盘在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。在下，小盘在上。372.3 2.3 问题规约法问题规约法v天神说：天神说：“当这当这64个盘子全部移到第三根柱子上个盘子全部移到
25、第三根柱子上后后,世界末日就要到了世界末日就要到了”。这就是著名的。这就是著名的梵塔问题梵塔问题。v用用计算机求解一个实际问题，首先要从这个实际计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，以便数学模型的算法，最后根据算法编写程序，以便调试、编译、连接和运行，从而形成该问题的求调试、编译、连接和运行，从而形成该问题的求解。解。v从实际问题中抽象出一个数学模型的实质，其实从实际问题中抽象出一个数学模型的实质，其实就是要用数学的方法抽取其主要的，本质的内容，就是要用数学的方法抽取其主
26、要的，本质的内容，最终实现对该问题的正确认识。最终实现对该问题的正确认识。3839用计算机解决问题的关键用计算机解决问题的关键 任任何何一一项项计计算算，总总要要事事先先拟拟定定计计算算方方案案和和规规划划计计算算步步骤骤。为为使使计计算算机机的的计计算算过过程程能能够够解解决决某某一一问问题题，必必须须为为计计算算机机设设计计执执行行的的解解决决方方案案中中的的每每个个详详细细步步骤骤，并并且且将将此此过过程程完完整整地地描描述述出出来来。所谓所谓算法算法是对某个问题求解方案的完整而明确的描述。是对某个问题求解方案的完整而明确的描述。与算法有关的还有一个大家熟悉的公式：与算法有关的还有一个大
27、家熟悉的公式：程序程序=算法十数据结构算法十数据结构 算算法法设设计计和和程程序序设设计计是是不不完完全全相相同同的的。由由于于数数字字计计算算机机运运算算速速度度很很高高，是是人人工工手手算算所所不不能能比比拟拟的的。为为了了充充分分发发挥挥计计算算机机的的这这种种优优点点，在在用用计计算算机机求求解解问问题题过过程程中中，应应尽尽量量减减少少人人工工干干预预。因因此此，必必须须先先将将所所制制定定的的解解决决方方案案“告告诉诉”计计算算机机，使使计计算算机机按按照照人人们们规规定定的的计计算算顺顺序序去去自自动动执执行行。用用计计算算机机能能接接受受的的“语语言言”来来描描述述解题步骤，即
28、程序设计，它还包含了合适的数据结构。解题步骤，即程序设计，它还包含了合适的数据结构。40解决计算问题一般步骤解决计算问题一般步骤算法设计41算算法法 为解决某一具体问题制定的，经为解决某一具体问题制定的，经过严谨定义其运算顺序的一组规则。过严谨定义其运算顺序的一组规则。其中每一个规则都是有效、明确的，其中每一个规则都是有效、明确的，且这一顺序将在有限次数下终止。且这一顺序将在有限次数下终止。42n自然语言自然语言n专用工具专用工具流程图、流程图、PAD图、图、N-S图图n算法描述工具算法描述工具Pascal、C算法的描述43PAD图图(ProblemAnalysisDiagram，问题分析图问
29、题分析图)nPAD图图是是日日本本日日立立公公司司提提出出，是是由由程程序序流流程程图图演演化化来来的的，用用结结构构化化程程序序设设计计思思想想表表现现程程序序逻逻辑辑结结构构的的图图形形工工具具。现现在在已为已为ISO认可。认可。nPAD图图设设置置了了五五种种基基本本控控制制结结构构的的图图式式，并允许递归使用。并允许递归使用。442.3.1问题归约描述问题归约描述（ProblemReductionDescription）2.3 2.3 问题规约法问题规约法v梵塔难题梵塔难题(a)初始状态初始状态(b)目标状态目标状态452.3 2.3 问题规约法问题规约法v原始问题归约（简化）为三个子
30、问题：原始问题归约（简化）为三个子问题：1、移动、移动A，B盘至柱子盘至柱子2的双圆盘难题的双圆盘难题2、移动圆盘、移动圆盘C至柱子至柱子3的单圆盘问题的单圆盘问题3、移动、移动A，B盘至柱子盘至柱子3的双圆盘难题的双圆盘难题462.3 2.3 问题规约法问题规约法v归约过程归约过程472.3 2.3 问题规约法问题规约法v求解过程（求解过程（3圆盘难题）圆盘难题）482.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法 这样的问题求解算法可以设计成一个递归结构这样的问题求解算法可以设计成一个递归结构的算法。的算法。如图所示，求解如图所示，求解n个圆盘的汉诺塔问题的算法个圆
31、盘的汉诺塔问题的算法为：为：(1)递归调用递归调用n-1个圆盘的汉诺塔问题算法，把个圆盘的汉诺塔问题算法，把上面的上面的n-1个圆盘从个圆盘从A柱移到柱移到B柱；柱；(2)把最下面的一个圆盘从把最下面的一个圆盘从A柱直接移到柱直接移到C柱；柱；(3)递归调用递归调用n-1个圆盘的汉诺塔问题算法，把个圆盘的汉诺塔问题算法，把B柱上临时存放的柱上临时存放的n-1个圆盘移到个圆盘移到C柱。柱。492.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法502.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法梵塔问题梵塔问题是一个典型的只有用递归方法是一个典型的只有
32、用递归方法(而不能用而不能用其他方法其他方法)来解决的问题，递归是计算学科中的一个重要来解决的问题，递归是计算学科中的一个重要概念，所谓递归，就是将一个较大的问题归约为一个与概念，所谓递归，就是将一个较大的问题归约为一个与原问题相同的小问题。原问题相同的小问题。根据递归方法，我们可发现将根据递归方法，我们可发现将64个盘子的梵塔问题个盘子的梵塔问题转化为求解转化为求解63个盘子先移动到第二个柱子上，再将最后个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将一个盘子直接移动到第三个柱子上，最后又一次将63个个盘子从第二个柱子移动到第三个柱子上，这样则可以解盘子从第二
33、个柱子移动到第三个柱子上，这样则可以解决决64个盘子的梵塔问题。依此类推，个盘子的梵塔问题。依此类推，63个盘子的梵塔求个盘子的梵塔求解问题可以转化为解问题可以转化为62个盘子的梵塔求解问题，个盘子的梵塔求解问题，62个盘子个盘子的梵塔求解问题又可以转化为的梵塔求解问题又可以转化为61个盘子的梵塔求解问题，个盘子的梵塔求解问题，直到直到1个盘子的梵塔求解问题。个盘子的梵塔求解问题。512.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法再由再由1个盘子的梵塔的求解求出个盘子的梵塔的求解求出2个盘子的梵塔，直到解个盘子的梵塔，直到解出出64个盘子的梵塔问题。下面，用个盘子的梵
34、塔问题。下面，用C语言对该问题的求解算语言对该问题的求解算法进行描述。法进行描述。hanoi(intn,charleft,charmiddle,charright)if(n=1)move(1,one,_,three)；elsehanoi(n-1,left,right,middle)；move(1,left,_,right)；hanoi(n-1,middle,left,right)；522.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法注：注：n表示表示n个盘子的梵塔问题，个盘子的梵塔问题，left表示第一个柱子，表示第一个柱子，middle表示第二个柱子，表示第二个柱子，
35、right表示第三个柱子。函数表示第三个柱子。函数hanoi(n-1,left,right,middle)表示表示n-1阶梵塔从第一个柱子阶梵塔从第一个柱子借助第三个柱子先移到第二个柱子上，函数借助第三个柱子先移到第二个柱子上，函数move(1,left,_,right)表示将第一个柱子上最后一个盘子直接表示将第一个柱子上最后一个盘子直接放到第三个柱子上，函数放到第三个柱子上，函数hanoi(n-1,middle,left,right)表示表示n-1个个盘子借助第一个柱子移到第三个柱子上。盘子借助第一个柱子移到第三个柱子上。在以上在以上C语言描述的算法基础上，作适当扩充就可以语言描述的算法基础
36、上，作适当扩充就可以形成一个完整的程序，经过编译和连接后，计算机就可形成一个完整的程序，经过编译和连接后，计算机就可以执行这个程序，按照递归的方法将问题求解出来。以执行这个程序，按照递归的方法将问题求解出来。532.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法现在的问题目是当现在的问题目是当n=64时，即有时，即有64个盘子时，需个盘子时，需要移动多少次盘子，要用多少时间。要移动多少次盘子，要用多少时间。按照上面的算法，按照上面的算法，n个盘子的梵塔问题目需要移动的个盘子的梵塔问题目需要移动的盘子数是盘子数是n-1个盘子的梵塔问题目需要移动的盘子数的个盘子的梵塔问题目需
37、要移动的盘子数的2倍加倍加1。于是。于是h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1=2nh(0)+2n-1+22+2+1=2n-1+22+2+1=2n-1因此，要完成梵塔的搬迁，需要移动盘子的次数为：因此，要完成梵塔的搬迁，需要移动盘子的次数为：2n-1=18446744073709551615542.3 2.3 问题规约法问题规约法2.3 2.3 问题规约法问题规约法 如果每秒移动一次，一年有如果每秒移动一次，一年有31536000秒，秒，则僧侣们一刻不停地来回搬动，也需要花费则僧侣们一刻不停地来回搬动，也需要花费58
38、49亿年的时间。假定计算机以每秒亿年的时间。假定计算机以每秒1000万个盘子的万个盘子的速度进行搬迁，则需要花费大约速度进行搬迁，则需要花费大约58490年的时间。年的时间。就这个例子，可以了解到理论上可以计算就这个例子，可以了解到理论上可以计算的问题，实际上并不一定能行，这属于算法复杂的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。性方面的研究内容。552.3.2与或图表示与或图表示2.3 2.3 问题规约法问题规约法 复复杂杂问问题题很很难难或或没没法法直直接接求求解解，但但可可以以分分解解成成一一系系列列（类类型型不不同同）的的子子问问题题，而而这这些些子子问问题题又又可可反
39、反复复细细分分成成一一些些更更小小的的子子问问题题，一一直直到到分分成成一一些些可可普普通通求求解解的的、相相当当基基本本的的问问题题为为止止。然然后后由由这这些些分分解解成成的的子子问问题题的的全全部部或或部部分分解再导出原问题的解。解再导出原问题的解。这这种种将将一一个个问问题题分分解解成成若若干干个个子子问问题题，又又由由子子问问题题的的解解导导出出原原问问题题解解的的方方法法称称为为问问题题化化简简。问问题题化化简简已已在在工工业业调调度度分分析析、定定理理证证明明等等方面得到应用。方面得到应用。562.3.2与或图表示与或图表示v与图、或图、与或图与图、或图、与或图2.3 2.3 问
40、题规约法问题规约法ABCD与图与图ABC或图或图572.3 2.3 问题规约法问题规约法BCDEFGAHMBCDEFGAN使图中的每个结点含意单一化。使图中的每个结点含意单一化。使图中的每个结点含意单一化。使图中的每个结点含意单一化。582.3 2.3 问题规约法问题规约法父节点父节点子节点子节点或节或节点点与节点与节点终叶节点终叶节点v一些关于与或图的术语一些关于与或图的术语592.3 2.3 问题规约法问题规约法v定义定义v可解节点可解节点：与或图中一个可解节点的一般定：与或图中一个可解节点的一般定义可以归纳如下：义可以归纳如下：1、终叶节点是可解节点终叶节点是可解节点(因为它们与本原问因
41、为它们与本原问题相关连题相关连)。2、如果某个非终叶节点含有、如果某个非终叶节点含有或后继节点或后继节点，那，那么只有当其后继节点至少有一个是可解的时，么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。此非终叶节点才是可解的。3、如果某个非终叶节点含有、如果某个非终叶节点含有与后继节点与后继节点，那么，那么只要当其后继节点全部为可解时，此非终叶节点只要当其后继节点全部为可解时，此非终叶节点才是可解的。才是可解的。602.3 2.3 问题规约法问题规约法v定义定义v不可解节点不可解节点 不可解节点的一般定义归纳于下：不可解节点的一般定义归纳于下：1、没有后裔的非终叶节点为不可解节点
42、。、没有后裔的非终叶节点为不可解节点。2、如果某个非终叶节点含有、如果某个非终叶节点含有或后继节点或后继节点，那么，那么只有当其全部后裔为不可解时，此非终叶节点只有当其全部后裔为不可解时，此非终叶节点才是不可解的。才是不可解的。3、如果某个非终叶节点含有、如果某个非终叶节点含有与后继节点与后继节点，那么只，那么只要当其后裔至少有一个为不可解时，此非终叶节要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。点才是不可解的。612.3 2.3 问题规约法问题规约法v定义定义有解节点有解节点无解节无解节点点终叶节点终叶节点622.3 2.3 问题规约法问题规约法v对原问题的求解即是对对应的与或
43、图进行搜对原问题的求解即是对对应的与或图进行搜索，目的在于表明起始节点是有解的。索，目的在于表明起始节点是有解的。v与或图构成规则与或图构成规则v每个节点代表一个明显的问题或者问题集合，每个节点代表一个明显的问题或者问题集合，除了起始节点外，每个节点只有一个父节点。除了起始节点外，每个节点只有一个父节点。此时，这些图就是与或树。此时，这些图就是与或树。632.3 2.3 问题规约法问题规约法v某人一星期天洗一次衣服，所要做的事有：收集某人一星期天洗一次衣服，所要做的事有：收集脏衣服、洗衣服、把衣服弄干、熨平、叠好并归脏衣服、洗衣服、把衣服弄干、熨平、叠好并归堆。其中，某些事可采用不同的方法，如
44、洗衣服堆。其中，某些事可采用不同的方法，如洗衣服一项可以是手洗也可以是机器洗。一项可以是手洗也可以是机器洗。v对于这个问题可以构造出下图所示的一棵与对于这个问题可以构造出下图所示的一棵与或或树。图中手洗的那个结点没有子孙也不是方形结树。图中手洗的那个结点没有子孙也不是方形结点，它表示此人不采用手洗的方法。当然，洗衣点，它表示此人不采用手洗的方法。当然，洗衣服问题是个非常简单的问题，而实际应用中很多服问题是个非常简单的问题，而实际应用中很多问题远非如此简单，因此使用问题化简就有了现问题远非如此简单，因此使用问题化简就有了现实意义。实意义。642.3 2.3 问题规约法问题规约法652.3 2.3
45、 问题规约法问题规约法梵塔问题归约图（与或图）梵塔问题归约图（与或图）662.3 2.3 问题规约法问题规约法v归约过程归约过程672.3 2.3 问题规约法问题规约法v求解过程（求解过程（3圆盘难题）圆盘难题）68第二章第二章知识表示方法知识表示方法2.1知识表示概述知识表示概述2.2状态空间法状态空间法2.3问题归约法问题归约法2.4产生式表示法产生式表示法2.5谓词逻辑法谓词逻辑法2.6语义网络法语义网络法2.7框架表示框架表示2.8剧本表示剧本表示2.9其他方法其他方法692.4产生式表示法（产生式表示法（ProductionSystem）v产生式系统产生式系统l1943年年,由美国数
46、学家由美国数学家PostPost提出。提出。l20世世纪纪60年年代代，成成为为认认知知心心理理学学研研究究人人类类心心理理活活动中信息加工过程的基础。动中信息加工过程的基础。l专家系统采用产生式系统的结构来建造。专家系统采用产生式系统的结构来建造。v采用产生式系统理由：采用产生式系统理由：l用用产产生生式式系系统统结结构构求求解解问问题题的的过过程程和和人人类类求求解解问问题题时时的的思思维过程很相象。维过程很相象。l可以把产生式系统作为人工智能系统的基本结构单元或基可以把产生式系统作为人工智能系统的基本结构单元或基本模式看待。到目前为止，产生式系统已发展成为人工智本模式看待。到目前为止，产
47、生式系统已发展成为人工智能系统中最典型最普遍的一种结构。能系统中最典型最普遍的一种结构。702.4产生式表示法（产生式表示法（ProductionSystem）又称为产生式规则表示法，它和图又称为产生式规则表示法，它和图灵机有相同的计算能力。目前产生灵机有相同的计算能力。目前产生式表示法已成为人工智能中应用最式表示法已成为人工智能中应用最多的一种知识表示方法。多的一种知识表示方法。产生式知识产生式知识产生式知识产生式知识表示方法表示方法表示方法表示方法712.4产生式表示法（产生式表示法（ProductionSystem）2.4.1产生式的基本形式产生式的基本形式产生式通常用于表示具有因果关系
48、的知识，其基本形式产生式通常用于表示具有因果关系的知识，其基本形式是是:PQ或或IFPTHENQ其中，其中，P是产生式的前提或条件，用于指出该产生式是是产生式的前提或条件，用于指出该产生式是否是可用的条件；否是可用的条件；Q是一组结论或动作，用于指出该产生式是一组结论或动作，用于指出该产生式的前提条件的前提条件P被满足时，应该得出的结论或应该执行的操作。被满足时，应该得出的结论或应该执行的操作。P和和Q都可以是一个或一组数学表达式或自然语言。都可以是一个或一组数学表达式或自然语言。722.4产生式表示法（产生式表示法（ProductionSystem）2.4.2产生式表示知识方法产生式表示知识
49、方法确定性和不确定性规则知识的产生式表示。确定性和不确定性规则知识的产生式表示。确定性和不确定性规则知识的产生式表示。确定性和不确定性规则知识的产生式表示。确定性规则知识确定性规则知识 可用前面介绍的产生式的基本形式表示即可用前面介绍的产生式的基本形式表示即可。可。不确定性规则知识不确定性规则知识 用如下形式表示用如下形式表示 PQ （可信度）（可信度）或者或者 IFPTHENQ （可信度）（可信度）其中，其中，P是产生式的前提或条件，用于指出该产生式是否是是产生式的前提或条件，用于指出该产生式是否是可用的条件；可用的条件；Q是一组结论或动作，用于指出该产生式的前提是一组结论或动作，用于指出该
50、产生式的前提条件条件P P被满足时，应该得出的结论或应该执行的操作。被满足时，应该得出的结论或应该执行的操作。732.4产生式表示法（产生式表示法（ProductionSystem）2.4.2产生式表示知识方法产生式表示知识方法产生式规则的例子产生式规则的例子r6:IF动物有犬齿动物有犬齿AND有爪有爪AND眼盯前方眼盯前方THEN该动物是食肉动物该动物是食肉动物其中，其中，r6是该产生式的编号；是该产生式的编号；“动物有犬齿动物有犬齿AND有爪有爪AND眼盯前方眼盯前方”是产生式的前提是产生式的前提P；“该该动物是食肉动物动物是食肉动物”是产生式的结论是产生式的结论Q。742.4产生式表示法