2-1 第二章 知识表示与推理.doc

第二部分 知识表示方法 问题求解(Problem solving)涉及许多研究领域，但知识表示是其三大基本功能之一。本章主要讨论几中基本的知识表示方法技术，如状态空间表示法、问题归约法、谓词逻辑法、语义网络法等方法。 2-1状态(state)空间表示法 2-1-1 问题Q的状态描述 State:为描述某类不同事物间差异而引入的一组变量之有序集合。即,其中，表示状态分量或状态变量。表示Q的每一元素都赋予一个值之后的某种状态。 操作符/算符：是问题从一种状态变迁到另外一种状态的过程或手段。如走步、过程、规则、算子、逻辑运算符号等。 问题状态空间：表示问题全部可能状态及其关系的图。其构成由三部分构成（如图所示） 15数码难题（15 puzzle problem） 1 14 12 13 2 10 11 3 15 9 8 4 5 6 7 4 12 11 13 2 10 14 3 15 9 8 1 5 6 7 需要解决的问题如下： ① 问题的状态描述方法 ② 问题的初始状态描述 ③ 问题的目标状态描述 ④ 问题描述状态转换的操作算子及其对状态描述的作用 ⑤ 两种状态的比较 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14 11 9 15 1 3 4 12 7 5 8 6 13 2 10 14 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14 11 9 4 15 1 3 8 12 7 5 6 13 2 10 14 11 9 4 15 1 3 12 7 5 8 6 13 2 10 14 11 9 15 1 3 4 12 7 5 8 6 13 2 10 14 11 9 15 1 3 4 12 7 5 8 6 13 2 10 14 2-1-2 问题的状态图示法 （1）基本概念  （2）能够表示的问题 ① 求解问题状态图中指定节点（初始状态）与另一节点（目标状态）之间的一条路径（或所有路径）。 ② 求节点与节点集合中任一个节点之间的距离（最小距离，最大距离等）。 ③ 求节点集合中任一个节点与节点集合中任一个节点之间的路径。 2-1-3 状态空间表示举例（从要解决的五个基本问题分析） 例1 十五数码问题（表示如图2-1，可用矩阵形式表示） 原始问题描述：有一个4×4的方格棋盘，其中的每一方格放入一1-15之间的数字值，一个空格方格，每次（只能）通过交换空格方格和其（水平和垂直方向上）相邻四个方格中的一个数进入下一状态。问是否能从给定棋盘初始状态，进入目标状态？或给定两棋盘格局，能否从一个状态达到另一状态？等等。 例2 推销员旅行问题（如图2-2的形式表示，其状态空间图如2-3）。 原始问题描述：推销员要在n个城市之间旅行推销产品，从一个城市出发，经过每个城市一次，最后回到起点城市。问：如果按照总路程的长短为评判标准，如何设计旅行路径，使得他能够旅行所有城市一次，且仅一次，同时，又能旅行路径最短？ 例3 猴子和香蕉问题 问题的状态描述方法 用一个四元组向量表示整个问题的各种状态，其中： 表示猴子的水平位置；表示猴子是否在箱子顶上取香蕉，是时，否则；表示箱子所在的水平位置；表示猴子是否摘到香蕉，摘到，否则，。 问题的初始状态描述 问题描述状态转换的操作算子及其对状态描述的作用 本问题有四个算子： (1)表示猴子走到水平位置。用产生式规则表示成： 。即猴子在水平位置处，箱子在处，没有站在箱子上，是否摘到香蕉处于值状态，在算子作用下，会进入下一个状态。 （2）表示猴子把箱子推到水平位置。用产生式规则表示成：。即猴子与箱子在同一位置，且猴子不在箱子顶上时，它通过算子将箱子推到水平位置，进入状态。 （3）算子表示猴子爬上箱子顶去。即：。 （4）算子表示猴子在箱子顶上摘香蕉。即：。 问题的目标状态描述 2-2问题归约法（Problem Reduction） 2-2-1 问题归约描述 Hanoi Puzzle（图示略） ① 问题的原始描述 ② 原始问题的归约（将其变成三个难度较小的子问题） ③