3-2020 第三章-21
需积分: 0 26 浏览量
2022-08-03
17:37:53
上传
评论
收藏 1.31MB PDF 举报
1
主要内容
• 3.1 问题规约和与或图
• 3.2 与或树的盲目式搜索
• 3.3 博弈树搜索
与或图搜索：在与或图上执行搜索的过
程，其目的在于标明起始节点是可解的
，即搜索不是去寻找到目标节点的一条
路径，而是寻找一个解树。
执行可解节点标志和不可解点标志过程。
解树：那些可解节点所构成的子树，这些节
点能够证明问题的初始节点是可解的。
应把该节点从图中删去
A
B
C
D
t
2
t
3
t
4
t
1
E
与或图/与或树
与或树：除初始节点，其余节点只有一
个父节点
与或图：除初始节点，其余节点允许有
多个父节点
A
B
C
D
t
2
t
3
t
4
t
1
E
与或树
与或图
与或树搜索
与或树的一般搜索过程：
⑴ 把原始问题作为初始节点S
0
，并把它作为当前节点；
⑵ 应用分解或等价变换对当前节点进行扩展；
⑶ 为每个节点设置指向父节点的指针；
⑷ 选择适合的节点作为当前节点，反复执行第⑵步和第⑶
步，在此其间要多次调用可解标志过程和不可解标志过程
，直到初始节点被标为可解节点或不可解节点为止。
与或树的搜索的目的是寻找解树，从而求得原始
问题的解.
与或树搜索：
搜索目的：是证明起始节点是否可解，而可解节点
是递归定义的，取决于后继节点是否可解，即搜索
过程是能否找到可解的叶节点。
若初始节点被标志为可解，则搜索成功结束；若初
始节点被标志为不可解，则搜索失败。
与或树搜索
与或树搜索
盲目式搜索
宽度优先搜索
深度优先搜索
博弈树搜索
与/或树的搜索策略
Max-Min搜索
剪枝
与或树的宽度优先搜索
与或树的宽度优先搜索的基本思想：
按照“先产生的节点先扩展”的原则进行搜索
搜索过程中要多次调用可解标志过程和不可解标志
过程
OPEN表、CLOSED表类似状态空间搜索
OPEN表：存放待扩展的节点
CLOSED表：存放已扩展的节点
Copyright by Lrc&Mch
评论0