Artificial Intelligence 第二章知识表示方法 21状态变间法 2.2问题归约法 2.3谓词逻辑法 2.4语义网络法 2.5其他方法 2.6小结
第二章 知识表示方法 2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 2.5 其他方法 2.6 小结
2.1状态空间法 State Space Representation 令问题求解技术主要是两个方面: 问题的表示 令求解的方法 (分状态空间法 心状态( state ☆算符( operator) C状态空间六法C5U
2 2.1状态空间法 （State Space Representation） ❖问题求解技术主要是两个方面： ❖问题的表示 ❖求解的方法 ❖状态空间法 ❖状态（state） ❖算符（operator） ❖状态空间方法
21状态空间法 2.1.1河题状态描述 ◇定义 (状态:描述某类不同事物间的差别而引入的 组最少变量q,q1,…,qn的有序集合 算符:使问題从一种状态变化为另一种状态 的手段称为拼作符或算符 心问题的状态空间:是一个表示该问題全部可 能状态及其关糸的图,它包含三种说明的集 合,即三元状态(S,F,G)。 3
3 2.1.1 问题状态描述 ❖定义 ❖状态：描述某类不同事物间的差别而引入的 一组最少变量q0，q1，…，qn的有序集合。 ❖算符：使问题从一种状态变化为另一种状态 的手段称为操作符或算符。 ❖问题的状态空间：是一个表示该问题全部可 能状态及其关系的图，它包含三种说明的集 合，即三元状态（S，F，G）。 2.1 状态空间法
21状态空间法 2.状态空间表示概念详释 Original Middle Goal State State State 心例如下棋、迷宫及各种游戏
4 2. 状态空间表示概念详释 ❖例如下棋、迷宫及各种游戏。 Original State Middle State Goal State 2.1 状态空间法
21状态空间法 例:三数码难题 (3 puzzle problem 23 23 2 2 31 初始棋局 目标棋局
5 例:三数码难题 （3 puzzle problem） 2 1 3 1 2 3 1 2 3 1 3 2 1 3 2 3 1 2 初始棋局 目标棋局 2.1 状态空间法
21状态空间法 2.1.2状态图示法 ☆有向图 (心路径 代价 ☆图的显示说明 图的隐示说明 A B
6 ❖有向图 ❖路径 ❖代价 ❖图的显示说明 ❖图的隐示说明 2.1.2 状态图示法 A B 2.1 状态空间法
21状态空间法 213状态空间表示举例 冷产生式杀统( production system) 一个总数据厍:它含有与具体任务有关的信息随着应 用情况的不同,这些数据庠可能简单,或许复杂。 冷一套规则:它对数据年进行作运算。每条规则由左部 鉴别规则的适用性或先决条件以及右部描述规则应用肘 所完成的动作。 令一个控制策略:它确定应该采用哪一条适用规则,而 且当数据庠的终止条件满足肘,就停止计算。⌒C
7 2.1.3 状态空间表示举例 ❖产生式系统（production system） ❖一个总数据库：它含有与具体任务有关的信息随着应 用情况的不同，这些数据库可能简单，或许复杂。 ❖一套规则：它对数据库进行操作运算。每条规则由左部 鉴别规则的适用性或先决条件以及右部描述规则应用时 所完成的动作。 ❖一个控制策略：它确定应该采用哪一条适用规则，而 且当数据库的终止条件满足时，就停止计算。 2.1 状态空间法
21状态空间法 状态空间表示举例 今例:猴子和香蕉问题 香蕉p 狼子 箱子 8
8 状态空间表示举例 ❖例：猴子和香蕉问题 2.1 状态空间法
21状态空间法 解题过程 ◇用一个四元表列(W,x,Y,z)来表示 这个问题状态 令这个问题的操作(算符)如下: (冷2B0to(U)表示猴子走到水平位置U 或者用产生式规则表示为 W,0, Y, z)goto (U)(U,0,Y, Z) 9
9 解题过程 ❖ 用一个四元表列（W，x，Y，z）来表示 这个问题状态. ❖这个问题的操作（算符）如下： ❖2 goto（U）表示猴子走到水平位置U ❖或者用产生式规则表示为 （W，0，Y，z） goto（U） （U，0，Y，z） 2.1 状态空间法
21状态空间法 pushbox(V)猴子把箱子推到水平位置V, 即有 (W,0, W, Z)pushbox (V),(V,0, V, z) ☆ climbbox猴子爬上箱顶,即有 (W,0,W,z) climbbox (W,1,W,z) 10
10 ❖pushbox（V）猴子把箱子推到水平位置V， 即有 （W，0，W，z） pushbox（V） （V，0，V，z） ❖ climbbox猴子爬上箱顶，即有 （W，0，W，z） climbbox （W，1，W，z） 2.1 状态空间法