人工智能第二章.ppt

1、第二章 知识表示方法 Chapter 2 Methodologies of Knowledge Representation 主讲教授 蔡自兴,人工智能Artificial Intelligence,General Methodologies of KR State Space Representation Problem Reduction Representation Predicate Logic Representation Semantic Network Representation Frame Script Procedure,Ch.2 Methodologies of Know

2、ledge Representation (KR),2.1 State Space Representation (状态空间表示) Principle Tool Examples Solution,Ch.2 Methodologies of Knowledge Representation (KR),1. Basic Thinking 2. Working Mechanism Reduction 3. Means of Representation -AND/OR Graph 4. Summary,2.2 Problem Reduction Representation第二节 问题归约表示,C

3、ontents:,2.2.1. Basic Thinking（基本思路）,Give a problem description,1. Problem Transformation （问题变换）Q1,Q2 An initial problem description. A set of operators transforming the initial problem into subproblems and sub-subproblems. A set of description of primitive problems,2. Main Components（主要组成）,2.2.2 Wo

4、rking Mechanism-Reduction（变换机理归约) 1. Example：Tower of Hanoi Puzzle（THP）,Three pegs and sixty-four disks,3-disk Description for THP （3圆盘梵塔难题描述）,Constrain Conditions（约束条件）,Three Rules:,2. Reduce the original problem into a set of simpler problems （把原问题归约为较简单问题的集合）,Fig 2.5 Reduction for the Tower Hanoi

5、 Puzzle (See the next page),（122）,（322）,(b) The one-disk puzzle of moving disks C to peg 3,(a) The 2-disk puzzle of moving disks A and B to peg 2,The solving process of THP（梵塔难题求解步骤）,3. Demonstration of THP （多圆盘梵塔难题演示） Q3,2.2.3 Means of Representation-AND/OR Graph （表示工具与或图）,Fig 2.6 Structure of an A

6、ND/OR graph,1. Idea of AND/OR Graph（与或图概念）,2. Some Terms of AND/OR Graph（与或图的某些术语）,3. AND/OR Graph for 3-disk THP （梵塔难题与或图）,Fig 2.7 Reduction graph for the 3-disk THP,3. AND/OR Graph for 3-disk THP （续）,4. AND/OR Graph for 4-disk THP （4圆盘梵塔难题归约图）,Constructing Rules for AND/OR Graph（与或图构造规则）,Every node represents a single problem or a set of problems.,(2) Terminal nodes correspond to primitive problems.,(3) Operators transform a problem into a set of subproblems.,(4) Directed links are towards every AND node of the