人工智能第二章课件.ppt

中南大学 智能系统与智能软件研究所 2.1 知识表示(Knowledge Representation)概述 知识表示是人工智能研究中最基本的问题之一。 2.2 状态空间法（State Space Representation） 问题求解技术主要是两个方面： 问题的表示 求解的方法 2.2.1 问题状态描述 定义 状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。 问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。 状态空间表示概念详释 例如下棋、迷宫及各种游戏。 例:三数码难题（3 puzzle problem） 实例：十五数码难题（15 puzzle problem） 2.2.2 状态图示法 有向图 路径 代价 图的显示说明 图的隐示说明 2.2.2 状态图示法 2.2.3 状态空间表示举例 产生式系统（production system） 一个总数据库：它含有与具体任务有关的信息。随着应用情况的不同，这些数据库可能简单，或许复杂。 状态空间表示举例 例：猴子和香蕉问题 解题过程 用一个四元表列（W，x，Y，z）来表示这个问题状态。 这个问题中的操作（算符）如下： 1、goto（U）猴子走到水平位置U，表示为 goto(U) 　（W，0，Y，z） --------------（U ，0 ，Y ，z ） 即把状态（W，0，Y，z）变换为状态（U，0，Y，z）。 3、climbbox猴子爬上箱顶，即有 climbbox （W，0，W，z）------------------（W，1，W，z） 条件：猴子和箱子应当在同一位置上，而且猴子不在箱顶上。 猴子和香蕉问题自动演示： 2.3 问题归约法（Problem Reduction Representation） 问题归约表示法的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。 问题归约的实质： 从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。 梵塔问题? 相传印度教的天神梵天在创造地球这一世界时，建了一座神庙，神庙里竖有三根宝石柱子，柱子由一个铜座支撑。梵天将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，即所谓的梵塔(又称汉诺塔)。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则： (1)每次只能移动一个盘子； (2)盘子只能在三根柱子上来回移动，不能放在他处； (3)在移动过程中，三根柱子上的盘子必须始终保持大盘 在下，小盘在上。 天神说：“当这64个盘子全部移到第三根柱子上后,世界末日就要到了”。这就是著名的梵塔问题。 用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，以便调试、编译、连接和运行，从而形成该问题的求解。 从实际问题中抽象出一个数学模型的实质，其实就是要用数学的方法抽取其主要的，本质的内容，最终实现对该问题的正确认识。 2.3.1 问题归约描述 （Problem Reduction Description） 梵塔难题 原始问题归约（简化）为三个子问题： 1、移动A，B盘至柱子2的双圆盘难题 2、移动圆盘C至柱子3的单圆盘问题 3、移动A，B盘至柱子3的双圆盘难题 归约过程 求解过程（3圆盘难题） 这样的问题求解算法可以设计成一个递归结构的算法。 如图所示，求解n个圆盘的汉诺塔问题的算法 为： (1) 递归调用n-1个圆盘的汉诺塔问题算法，把 上面的n-1个圆盘从A柱移到B柱； (2) 把最下面的一个圆盘从A柱直接移到C柱； (3) 递归调用n-1个圆盘的汉诺塔问题算法，把 B柱上临时存放的n-1个圆盘移到C柱。 梵塔问题是一个典型的只有用递归方法(而不能用 其他方法)来解决的问题，递归是计算学科中的一个重要 概念，所谓递归，就是将一个较大的问题归约为一个与 原问题相同的小问题。 再由1