21第二章知识表示与推理

2006-2007 年度第 1 学期研究生《人工智能》教案----详案 第二部分 知识表示方法 问题求解(Problem solving)涉及许多研究领域，但知识表示是其三大基本功能之一。本章主要讨论几中基本的知识表示方法技术，如状态空间表示法、问题归约法、谓词逻辑法、语义网络法等方法。 2-1 状态(state)空间表示法 2-1-1 问题 Q 的状态描述 State:为描述某类不同事物间差异而引入的一组变量nqqq,...,,10之有序集合。即TnqqqQ],...,[10,其中，iq 表示状态分量或状态变量。TnkkkkqqqQ],...,[10表示 Q 的每一元素都赋予一个值之后的某种状态。 (1) 操作符/算符：是问题从一种状态变迁到另外一种状态的过程或手段。如走步、过程、规则、算子、逻辑运算符号等。 (2) 问题状态空间：表示问题全部可能状态及其关系的图。其构成由三部分构成（如图所示） (3) 15数码难题（15 puzzle problem） Sou rce etT arg 需要解决的问题如下： ① 问题的状态描述方法 ② 问题的初始状态描述 ③ 问题的目标状态描述 ④ 问题描述状态转换的操作算子及其对状态描述的作用 ⑤ 两种状态的比较 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 Shift 原始问题描述：每次移动一步，只能移动跟空格相邻的数字单元。是否能从状态1 变成状态2？ (S, F, G) 初始状态集合 操作算子集合 目标状态集合 2006-2007 年度第1 学期研究生《人工智能》教案----详案 2-1-2 问题的状态图示法 （ 1）基本概念 （ 2）能够表示的问题 ① 求解问题状态图中指定节点s（初始状态）与另一节点t（目标状态）之间的一条路径（或所有路径）。 ② 求节点s与节点集合 }{it 中任一个节点之间的距离（最小距离，最大距离等）。 ③ 求节点集合 }{is 中任一个节点与节点集合 }{it 中任一个节点之间的路径。 2-1-3 状态空间表示举例（从要解决的五个基本问题分析） 例 1 十五数码问题（表示如图2-1，可用矩阵形式表示） 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 ...