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 ...