搜索与或图搜索.ppt

该【搜索与或图搜索 】是由【165456465】上传分享，文档一共【59】页，该文档可以免费在线阅读，需要了解更多关于【搜索与或图搜索 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。简约风年终工作总结
CLICK HERE TO ADD A TITLE
与或图搜索
演讲人姓名
01
与或树表示
02
与/或树的一般搜索
03
与/或树的广度优先搜索
04
与/或树的深度优先搜索
05
与／或树的启发式搜索
06
博弈树的启发式搜索
内容
基本思想：
当一个问题比较复杂时，直接进行求解往往比较困难。
可通过归约（分解或变换），将它转化为一系列较简单的问题。
通过对这些较简单问题的求解来实现对原问题的求解。
不同于状态空间方法的另外一种形式化方法。
02
01
03
04
05
与或树表示
与或树表示
【】
设有四边形ABCD和A′B′C′D′，证明它们全等。
与或树表示
分析：原问题分解为两个子问题：
与或树表示
与或树表示
分解
问题P可以归约为一组子问题{P1,P2,……,Pn}。
只有当所有子问题Pi(i＝1，2，……，n)都有解时,原问题P才有解。
即分解所得到的子问题的“与”和原问题P等价。
与树
K-连接符
P1
P2
P3
P
…...
K个
与或树表示
等价变换
问题P可以归约为一组子问题{P1,P2,……,Pn}。
这些子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解。
即变换所得到的子问题的“或”与原问题P等价。
或树
把一个原问题变换为若干个子问题可用一个“或树”来表示。
P1
P2
P3
P
与或树表示
与或树
如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。
P
P1
P2
P3
P31
P32
P33
P11
P12
原始问题
本原问题
（终止节点）
端节点———没有子节点的节点，即叶子节点；
终止节点——可解节点，即本原问题。
t
P
t
t
1
2
3
4
5
解树
由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树。
在解树中一定包含初始节点。
t
与或树表示