2.4启发式图搜索.ppt

启发式图搜索
利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。
启发信息的强度
强:降低搜索工作量,但可能导致找不到最优解
弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解
希望:
引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率。
基本思想
定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。
1,启发式搜索算法A(A算法)
评价函数的格式:
f(n) = g(n) + h(n)
f(n):评价函数
h(n):启发函数
符号的意义
g*(n):从s到n的最短路径的耗散值
h*(n):从n到g的最短路径的耗散值
f*(n)=g*(n)+h*(n):从s经过n到g的最短路径的耗散值
g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值
A算法
1, OPEN:=(s), f(s):=g(s)+h(s);
2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);
3, n:=FIRST(OPEN);
4, IF GOAL(n) THEN EXIT(ESS);
5, REMOVE(n, OPEN), ADD(n, CLOSED);
6, EXPAND(n) →{Mi},
计算f(n, mi):=g(n, mi)+h(mi);
A算法(续)
ADD(mj, OPEN), 标记mj到n的指针;
IF f(n, mk)<f(mk) THEN f(mk):=f(n, mk),
标记mk到n的指针;
IF f(n, ml)<f(ml,) THEN f(ml):=f(n, ml),
标记ml到n的指针,
ADD(ml, OPEN);
7, OPEN中的节点按f值从小到大排序;
8, GO LOOP;
…...
…...
…...
…...
…...
mj
mk
ml
一个A算法的例子
定义评价函数:
f(n) = g(n) + h(n)
g(n)为从初始节点到当前节点的耗散值
h(n)为当前节点“不在位”的将牌数
2 8 3
1 6 4
7 5
1 2 3
8 4
7 6 5