1/89
文档分类:IT计算机

启发式搜索搜索技术的应用-智能搜索引擎.ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
启发式搜索搜索技术的应用-智能搜索引擎.ppt
文档介绍:
2.4启发式搜索
搜索技术的应用-智能搜索引擎
启发式搜索涉及的基本概念
基本的启发式搜索方法
代价树的广度优先搜索
动态规划法(改进的代价树广度优先搜索)
代价树有界深度优先搜索
启发式搜索搜索技术的应用-智能搜索引擎
启发式搜索概念
启发式搜索与无信息搜索
无信息(盲目)搜索:按预定的控制策略进行搜索,在搜索过程中 获得的中间信息并不改变控制策略。 81
启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导 搜索朝着最有希望的方向前进,加速问题的求解过程并 找到最优解。
启发性信息
评估函数
启发式搜索搜索技术的应用-智能搜索引擎
评估函数的表示
含义:用于估价节点重要性的函数称为估价函数
表示: f(x)=g(x)+h(x)
g(x)是从初始结点S0到x实际代价
h(x)是从x到目标结点Sg的最佳路径的估计代价, 启发性信息的函数描述。
例 重排九宫问题 f(x)=d(x)+h(x)
启发式搜索搜索技术的应用-智能搜索引擎
代价的计算
边代价:从父节点到子节点的代价
表示:c(x1,x2)表示从父节点x1到子节点x2的代价
例:c(s0,A)=2 c(A,C)=4
代价:从一个节点经过一条支路到另一个节点所支付的代价。
表示:g(x)表示从初始节点s0到节点x的代价
例: g(A)=g(s0)+c(s0,A)=0+2=2 g(C)=g(A)+c(A,C)=2+4=6
代价树:边上标有代价的搜索树
s0
A
C
B
3
2
4
s0
A
B
C
2
3
4
启发式搜索搜索技术的应用-智能搜索引擎
2.4.1 代价驱动的搜索策略
代价树的广度优先搜索
动态规划法(改进的代价树广度优先搜索)
代价树的深度优先搜索
启发式搜索搜索技术的应用-智能搜索引擎
代价树的广度优先搜索
基本思想
搜索过程
实例
存在问题
解决方法(动态规划法)
启发式搜索搜索技术的应用-智能搜索引擎
基本思想
open表的节点顺序按的节点代价排列(从小到大)
启发式搜索搜索技术的应用-智能搜索引擎
搜索过程
1.将初始节点s0放入OPEN表,令g(s0)=0
2.如果OPEN表为空,则问题无解,退出
3.把OPEN表的第一个节点(记为n节点)取出放入CLOSED表
4.考察节点n是否为目标节点。若是,则求得了问题的解,退出。
5.若节点n不可扩展转(2)步。
6.扩展节点n,将其子节点放入OPEN表中,并为每一个子节点都配置指向父节点的指针;计算各个子节点的代价,并按各个节点的代价对表的全部节点进行排序(按从小到大的顺序),然后转(2)步。
启发式搜索搜索技术的应用-智能搜索引擎
例 如图是八城市间的交通图,两城市间的交通费用(代价)如图中数字所示。求从S到T的最小交通费用代宽演示.ppt
S
A
D
E
B
F
T
C
3
4
4
5
2
5
4
4
3
启发式搜索搜索技术的应用-智能搜索引擎
代价树的广度优先搜索(例)
1
2
3
4
5
6
7
10
11
12
13
8
9
19
20
21
15
17
18
14
S(0)
D1(4)
A1(3)
B1( 7 )
D2(8)
A2(9)
E1(6)
F1(10)
T1(13)
C1(11)
B2(11)
B3(13)
E3(10)
E2(12)
16
D3(14)
F3(16)
B4(15)
F2(14)
C3(17)
A3(15)
C2(15)
3
4
4
4
5
5
5
2
4
5
4
2
2
4
5
4
4
4
4
3
启发式搜索搜索技术的应用-智能搜索引擎
内容来自淘豆网www.taodocs.com转载请标明出处.
非法内容举报中心
文档信息
  • 页数89
  • 收藏数0 收藏
  • 顶次数0
  • 上传人sanshenglu2
  • 文件大小767 KB
  • 时间2021-06-29