f(x)=g(x)+h(x)
其中:g(x)——从初始节点S0到节点x的实际代价; h(x)——从x到目标节点Sg的最优路径的评估代价,它体现了问
题的启发式信息,其形式要根据问题的特性确定,h(x)称为启发式 函数。
2022/10/14
6
评估函数
启发式方法把问题状态的描述转换 成了对问题解决程度的描述。
这一程度用评估函数的值来表示。
2022/10/14
7
评估函数
S
搜索图G
2022/10/14
n ng
初始状态节点S
f(n):s-n-ng的估计最小路径代价
g(n):s-n的实际路径代价 h(n): n-ng的估计最小路径代价
节点n
目标状态节点ng
8
启发式搜索A算法
A算法的设计与一般图搜索相同,划分为二个阶段:
IF f(ni)>f(n,ni) THEN 令f(ni)=f(n,ni)
修改指针指向新父结点n
排序OPEN表(f(n)值从小到大排序)
2022/10/14
10
2022/10/14
4功指1搜 未做.若.退针建扩C索nL出从立为展图O,n一S一节到GE个此,目的把点S只这解标已S表放条包是扩节中路到含追展点;径一节起踪,建而个点始图则立得叫表节G有一到中O,点解P个的沿其ES成N叫;的初着的
始为空表;
5.扩展节点n,同时生成不是n的 祖 M2出的.先若;这的OP些那EN成些表员子是作节空为点表n,的的则集后失合继败节M,退点把 添入搜索图G中;对于M中每个 子3把 表.节选中它点f择(,从nnO,称nOi,P计iP)E此EN=算N表节g表:(n上点移,n为的出i) +节并第h放点一(n进in)个;C节LO点SE,