人工智能(知识表示方法问题归约法)课件.ppt

1、人人 工工 智智 能能Artificial Intelligence (AI)许建华许建华南京师范大学计算机科学与技术学院南京师范大学计算机科学与技术学院2011年秋季年秋季第第2章章 知识表示方法知识表示方法2.1 状态空间法状态空间法2.2 问题归约法问题归约法2.3 谓词逻辑法谓词逻辑法2.2 问题归约法问题归约法 例：求积分例：求积分 解法解法1：解法解法2：解法解法3：2(cos)xexxdx223(cos)cossin3xxxexxdxe dxxdxx dxxex问问 题题解法解法1解法解法2解法解法3解法解法4子问题子问题1子问题子问题2子问题子问题3变换变换分解分解问题归约法问

2、题归约法：从已知问题的描述出发，通过一系列从已知问题的描述出发，通过一系列变换变换或或分解分解将问题最终变为一个将问题最终变为一个子问题集合子问题集合，这些子问题的，这些子问题的解可以直接得到，从而解决初始问题解可以直接得到，从而解决初始问题 问题归约法由三个部分组成问题归约法由三个部分组成： 一个初始问题描述一个初始问题描述 一套将问题变换或分解为子问题的操作符一套将问题变换或分解为子问题的操作符 一套本原问题（一套本原问题（解可以直接得到的简单问题解可以直接得到的简单问题）描述描述2.2.1 问题归约描述问题归约描述 1 1、例子：、例子：梵塔问题梵塔问题（三个盘）（三个盘） (a) 初始

3、配置初始配置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题解决问题的思路解决问题的思路：第一第一、要将所有盘从第一个柱子搬到第三个、要将所有盘从第一个柱子搬到第三个柱子，根据游戏规则，首先要搬最大的柱子，根据游戏规则，首先要搬最大的 C 盘盘到第三个柱子上到第三个柱子上(a) 初始配初始配置置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题解决问题的思路解决问题的思路：第二第二、要能够搬、要能够搬 C 盘，条件是：第三个柱盘，条件是：第三个柱子是空的，子是空的，A、B必须在第二个柱子上（这必须在第二个柱子上（这里没有考虑如何搬里没有考虑如何搬A、B盘）盘）(a) 初始配置初始配置(b

4、) 目标配置目标配置图图2.6 梵塔难题梵塔难题解决问题的思路解决问题的思路：第三第三、搬、搬C盘到第三个柱子，然后想办法将盘到第三个柱子，然后想办法将A、B盘搬到第三个柱子上盘搬到第三个柱子上 (a) 初始配初始配置置(b) 目标配置目标配置图图2.6 梵塔难题梵塔难题将问题简化为下列三个子问题将问题简化为下列三个子问题：1. 移动园盘移动园盘 A 和和 B 到柱子到柱子 2 的双园盘难题的双园盘难题2. 移动移动 C 盘到柱子盘到柱子 3 的单园盘难题的单园盘难题3. 移动移动 A 和和 B 到柱子到柱子 3 的双园盘难题的双园盘难题图图2.8 梵塔问题的归约梵塔问题的归约左到右左到右 表

5、示表示 盘从大到小，盘从大到小，数字数字 表示表示 盘所在柱子号盘所在柱子号小盘：小盘：13中盘：中盘：12小盘：小盘：32小盘：小盘：21中盘：中盘：23小盘：小盘：13与与中小盘中小盘1到到2中小盘中小盘2到到3大盘大盘1到到32、问题归约的描述问题归约的描述 问题归约法的问题归约法的基本思路基本思路是：应用一系列算符将原是：应用一系列算符将原始问题的描述始问题的描述变换或分解变换或分解成为子问题的描述成为子问题的描述问题的描述问题的描述可以采用各种数据结构，如表、树、可以采用各种数据结构，如表、树、矢量、数组等矢量、数组等对于梵塔问题，问题及子问题描述：对于梵塔问题，问题及子问题描述：

6、(113)(333)问题归约法可以用一个三元组（问题归约法可以用一个三元组（S, O, P）来表示，来表示，其中：其中： S：原始问题，即要解决的问题原始问题，即要解决的问题 P：本原问题集，其中的每一个问题是不用证本原问题集，其中的每一个问题是不用证明的或自然成立的，例如公理、已知事实等明的或自然成立的，例如公理、已知事实等 O：操作算子集，用于将问题化为子问题操作算子集，用于将问题化为子问题2.2.2 与或图表示与或图表示 例例：有一个问题：有一个问题A，它可以通过三种途径来求解：它可以通过三种途径来求解：1、求解问题、求解问题 B 和和 C2、求解问题求解问题 D 、E 和和 F3、求解

7、求解 H与与或或引入中间节点引入中间节点好处好处：任何一个节点的后继节点要么全是任何一个节点的后继节点要么全是“与节与节点点”，要么全是，要么全是“或节点或节点”。与与或或与或图的特例与或图的特例： 所有节点都是或节点，这时就是一般的所有节点都是或节点，这时就是一般的图图，即，即状态空间法用到的图状态空间法用到的图 除了起始节点外，所有节点只有一个父节点，除了起始节点外，所有节点只有一个父节点，此时称为此时称为与或树与或树，前面的图，前面的图2.11就是与或树就是与或树 问题归约法、与或图表示之间的对应关系问题归约法、与或图表示之间的对应关系：问题归约法问题归约法原始问题原始问题本原问题本原问

8、题操作符操作符中间问题中间问题与或图表示与或图表示起始节点起始节点终叶节点终叶节点与、或关系的弧线与、或关系的弧线非终叶节点非终叶节点在与或图中，问题在与或图中，问题有解的条件有解的条件是：起始节点是是：起始节点是可解可解的的 一般情况下：一般情况下：分解分解 操作符得到操作符得到 与节点与节点变换变换 操作符得到操作符得到 或节点或节点在与或图中，一个在与或图中，一个可解节点的定义可解节点的定义是（递归地）：是（递归地）：1、终叶节点是可解的（因为它们与本原问题相关联、终叶节点是可解的（因为它们与本原问题相关联的）。一般情况，终叶节点用的）。一般情况，终叶节点用 t 来表示来表示2、如果某一

9、个非终叶节点含有、如果某一个非终叶节点含有“或或”后继节点，那后继节点，那么，只要有一个后继节点是可解的，这一个非终么，只要有一个后继节点是可解的，这一个非终叶节点就是可解的。叶节点就是可解的。一个节点可解一个节点可解可解可解3、如果某一个非终叶节点含有、如果某一个非终叶节点含有“与与”后继节点，后继节点，那么，只要所有后继节点是可解的，这一个那么，只要所有后继节点是可解的，这一个非终叶节点才是可解的非终叶节点才是可解的。所有节点可解所有节点可解可解可解与或图中，一个与或图中，一个不可解节点的定义不可解节点的定义（递归地）是：（递归地）是：1、没有后裔的非终叶节点是不可解节点。、没有后裔的非终

10、叶节点是不可解节点。2、如果某一个非终叶节点含有、如果某一个非终叶节点含有“或或”后继节点，后继节点，那么，只要当所有的后继节点都不可解时，这那么，只要当所有的后继节点都不可解时，这一个非终叶节点才是不可解的。一个非终叶节点才是不可解的。所有节点不可解所有节点不可解不可解不可解3、如果某一个非终叶节点含有、如果某一个非终叶节点含有“与与”后继节点，后继节点，那么，只要有一个后继节点是不可解的，这一那么，只要有一个后继节点是不可解的，这一个非终叶节点就是不可解的。个非终叶节点就是不可解的。 有一个节点不可解有一个节点不可解不可解不可解与或图的解图与或图的解图：由由最少最少的可解节点所构成的子图，这些的可解节点所构成的子图，这些节点能够使问题的起始节点是可解的节点能够使问题的起始节点是可解的与或图的一些例子与或图的一些例子t ：终叶节点终叶节点小实心园点小实心园点 ：可解节点：可解节点园圈园圈 ：不可解节点：不可解节点多多解解解图解图解图解图解图解图