(知识表示方法2问题归约法)课件.ppt

(知识表示方法2问题归约法)课件.ppt

ID:57029886

大小:197.00 KB

页数:30页

时间:2020-07-26

(知识表示方法2问题归约法)课件.ppt_第1页
(知识表示方法2问题归约法)课件.ppt_第2页
(知识表示方法2问题归约法)课件.ppt_第3页
(知识表示方法2问题归约法)课件.ppt_第4页
(知识表示方法2问题归约法)课件.ppt_第5页
(知识表示方法2问题归约法)课件.ppt_第6页
(知识表示方法2问题归约法)课件.ppt_第7页
(知识表示方法2问题归约法)课件.ppt_第8页
(知识表示方法2问题归约法)课件.ppt_第9页
(知识表示方法2问题归约法)课件.ppt_第10页
资源描述:

《(知识表示方法2问题归约法)课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第2章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法2.2问题归约法例:求积分解法1:解法2:解法3:问题解法1解法2解法3解法4子问题1子问题2子问题3变换分解问题归约法:从已知问题的描述出发,通过一系列变换或分解将问题最终变为一个子问题集合,这些子问题的解可以直接得到,从而解决初始问题问题归约法由三个部分组成:一个初始问题描述一套将问题变换或分解为子问题的操作符一套本原问题(解可以直接得到的简单问题)描述2.2.1问题归约描述1、例子:梵塔问题(三个盘)(a)初始配置(b)目标配置图2.6梵塔难题解决问题的思路:第一、要将所有盘从第一个柱子搬到第三个柱子,根据

2、游戏规则,首先要搬最大的C盘到第三个柱子上(a)初始配置(b)目标配置图2.6梵塔难题解决问题的思路:第二、要能够搬C盘,条件是:第三个柱子是空的,A、B必须在第二个柱子上(这里没有考虑如何搬A、B盘)(a)初始配置(b)目标配置图2.6梵塔难题解决问题的思路:第三、搬C盘到第三个柱子,然后想办法将A、B盘搬到第三个柱子上(a)初始配置(b)目标配置图2.6梵塔难题将问题简化为下列三个子问题:移动园盘A和B到柱子2的双园盘难题移动C盘到柱子3的单园盘难题移动A和B到柱子3的双园盘难题图2.8梵塔问题的归约左到右表示盘从大到小,数字表示盘所在柱子号小盘:13中盘:12小盘:3

3、2小盘:21中盘:23小盘:13与中小盘1到2中小盘2到3大盘1到32、问题归约的描述问题归约法的基本思路是:应用一系列算符将原始问题的描述变换或分解成为子问题的描述问题的描述可以采用各种数据结构,如表、树、矢量、数组等对于梵塔问题,问题及子问题描述:(113)(333)问题归约法可以用一个三元组(S,O,P)来表示,其中:S:原始问题,即要解决的问题P:本原问题集,其中的每一个问题是不用证明的或自然成立的,例如公理、已知事实等O:操作算子集,用于将问题化为子问题2.2.2与或图表示例:有一个问题A,它可以通过三种途径来求解:1、求解问题B和C2、求解问题D、E和F3

4、、求解H与或引入中间节点好处:任何一个节点的后继节点要么全是“与节点”,要么全是“或节点”。与或与或图的特例:所有节点都是或节点,这时就是一般的图,即状态空间法用到的图除了起始节点外,所有节点只有一个父节点,此时称为与或树,前面的图2.11就是与或树问题归约法、与或图表示之间的对应关系:问题归约法原始问题本原问题操作符中间问题与或图表示起始节点终叶节点与、或关系的弧线非终叶节点在与或图中,问题有解的条件是:起始节点是可解的一般情况下:分解操作符得到与节点变换操作符得到或节点在与或图中,一个可解节点的定义是(递归地):1、终叶节点是可解的(因为它们与本原问题相关联的)。一般情况,

5、终叶节点用t来表示2、如果某一个非终叶节点含有“或”后继节点,那么,只要有一个后继节点是可解的,这一个非终叶节点就是可解的。一个节点可解可解3、如果某一个非终叶节点含有“与”后继节点,那么,只要所有后继节点是可解的,这一个非终叶节点才是可解的。所有节点可解可解与或图中,一个不可解节点的定义(递归地)是:1、没有后裔的非终叶节点是不可解节点。2、如果某一个非终叶节点含有“或”后继节点,那么,只要当所有的后继节点都不可解时,这一个非终叶节点才是不可解的。所有节点不可解不可解3、如果某一个非终叶节点含有“与”后继节点,那么,只要有一个后继节点是不可解的,这一个非终叶节点就是不可解的。

6、有一个节点不可解不可解与或图的解图:由最少的可解节点所构成的子图,这些节点能够使问题的起始节点是可解的与或图的一些例子t:终叶节点小实心园点:可解节点园圈:不可解节点多解解图解图解图

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。