《搜索与或图搜索》PPT课件

《搜索与或图搜索》PPT课件

ID:36875864

大小:1.15 MB

页数:59页

时间:2019-05-10

《搜索与或图搜索》PPT课件_第1页
《搜索与或图搜索》PPT课件_第2页
《搜索与或图搜索》PPT课件_第3页
《搜索与或图搜索》PPT课件_第4页
《搜索与或图搜索》PPT课件_第5页
资源描述:

《《搜索与或图搜索》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四章与或图搜索内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与/或树的启发式搜索4.5博弈树的启发式搜索与或图搜索24.0与或树表示不同于状态空间方法的另外一种形式化方法。基本思想:当一个问题比较复杂时,直接进行求解往往比较困难。可通过归约(分解或变换),将它转化为一系列较简单的问题。通过对这些较简单问题的求解来实现对原问题的求解。与或图搜索34.0与或树表示【例4.0】设有四边形ABCD和A′B′C′D′,证明它们全等。与或图搜索44.0与或树表示分析:原问题分解为两个子问题:与或图搜索54.0与或树表示与或图搜索64

2、.0与或树表示4.0.1分解问题P可以归约为一组子问题{P1,P2,……,Pn}。只有当所有子问题Pi(i=1,2,……,n)都有解时,原问题P才有解。即分解所得到的子问题的“与”和原问题P等价。与树K-连接符P1P2P3P…...K个与或图搜索74.0与或树表示4.0.2等价变换问题P可以归约为一组子问题{P1,P2,……,Pn}。这些子问题Pi中只要有一个有解则原问题P就有解,只有当所有子问题Pi都无解时原问题P才无解。即变换所得到的子问题的“或”与原问题P等价。或树把一个原问题变换为若干个子问题可用一个“或树”来表示。P1P2P3P与或图搜索84.0与或树表示4.0.3与或树

3、如果一个问题既需要通过分解,又需要通过变换才能得到其本原问题,则其归约过程可用一个“与/或树”来表示。PP1P2P3P31P32P33P11P12原始问题本原问题(终止节点)端节点———没有子节点的节点,即叶子节点;终止节点——可解节点,即本原问题。t与或图搜索94.0与或树表示Pttt4.0.4解树由可解节点构成,并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树。在解树中一定包含初始节点。与或图搜索104.0与或树表示【例4.1】三阶梵塔问题。解:用三元组表示问题在任一时刻的状态:(i,j,k)i:代表金片C所在的钢针号;j:代表金片B所在的钢针号;k;代表

4、金片A所在的钢针号;123123ABC与或图搜索11123(1,1,1)123(1,2,2)123(3,2,2)123(3,3,3)ABC与或图搜索12(1,1,1)->(3,3,3)(1,1,1)->(1,2,2)(1,2,2)->(3,2,2)(3,2,2)->(3,3,3)(1,1,1)->(1,1,3)(1,1,3)->(1,2,3)(1,2,3)→(1,2,2)(3,2,2)->(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)三阶梵塔问题的与或树在该与/或树中,有7个终止节点,它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来,即得到

5、了原始问题的解:与或图搜索134.0与或树表示目标目标初始节点sabc与或图搜索14内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与/或树的启发式搜索4.5博弈树的启发式搜索与或图搜索154.1与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下:(1)把原始问题作为初始节点S0,并把它作为当前节点;(2)应用分解或等价变换操作对当前节点进行扩展;(3)为每个子节点设置指向父节点的指针;(4)选择合适的子节点作为当前节点,反复执行第(2)步和第(3)步,在此期间需要多次调用可解标记过程或不

6、可解标记过程,直到初始节点被标记为可解节点或不可解节点为止。与或图搜索164.1与/或树的一般搜索在与/或树中,除端节点和终止节点外,一个节点的可解性完全是由其子节点来决定的。对与节点,只有其所有子节点都为可解时它才为可解,只要有一个子节点不可解它就是不可解的;对或节点,只要有一个子节点可解它就是可解的,仅当所有子节点都是不可解时它才为不可解。可解标记过程由可解子节点来确定其父节点、祖父节点为可解节点的过程。不可解标记过程由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。与或图搜索174.1与/或树的一般搜索搜索解树的过程中,节点删除策略:①如果搜索过程确定某个节点为可解节

7、点,则其不可解的后裔节点就可从搜索树中删去;②如果搜索过程能确定某个节点为不可解节点,则其后裔节点也可从搜索树中删去。与或图搜索18内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与/或树的启发式搜索4.5博弈树的启发式搜索与或图搜索194.2与/或树的广度优先搜索与/或树的广度优先搜索算法:(1)把初始节点S0放人Open表中;(2)把Open表的第一个节点取出放入Closed表,并记该节点为n;(3)如果节

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

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

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