启发式搜索.ppt

启发式搜索 yinbaoyong@ 1启发式信息加速搜索?盲目搜索的缺陷??改进: 改进: 根据与问题相关的知识问题,引入启发式信息。??策略: 策略: 从初始结点 S出发, 选择离目标最近的子节点扩展。??定义: 定义: f f( (n n) )为为经过结点 n的且从起点到目标的最短路径长度的估计函数。 f(n)的值越小,表示路径越短 2引入 f f( (n n) )的搜索过程 f(n)3f f( (n n) )=? =? ??f f( (n n ) ) =g ( (n n) ) + h h( (n n ) ) –g( (n n) )表示起始结点到 n的最短路径长度的估计––h h( (n n) )表示 n到目标结点的最短路径长度的估计??g= g= ? ? h= h= ? ? )(ng)(nh4引入 g g( (n n ) ) 、、h h( (n n) )的搜索过程)()()(nhngnf?? 5f f( (n n) )≈≈f f* *( (n n) ) )(*ng)(*nh )(*)( )(*)(*)(* )(* )(* )(*nfnf nhngnf nnf nnh nng???的最短路径的代价是经过结点到目标最短路径的代价是结点的最短路径的代价是初始结点到结点 6八数码问题数为位置不正确的数字个令的深度为初始结点到结点令)( )(nh n ng 1)(?nh78启发式搜索算法—— A算法?定义 g(n)为已发现的初始结点到结点 n所有路径中的最短路径的代价。?定义 h(n)为结点 n到目标结点的最短路径长度的估计,也称启发式函数。?f(n ) = g(n )+ h(n)?利用 f 加速搜索的算法?使用 Open 表、 Closed 表 9A算法——伪代码 open 表、 closed 表为空,定义 s为初始状态结点。 f(s) := g(s) + h(s) 。将s加入到 open 表中。 open 表为空,则搜索失败退出, open 表中取出第一个结点 n,将 n插入到 closed 表中 n是目标结点,搜索成功,返回问题的解 Op i,扩展 n生成子结点 m i, a)计算 g(m i )=g(n)+ C(n, m i ); f=g(m i )+h(m i ); b)如果 m i已经存在于 open 表中或者在 closed 表中,且先前计算的 g(m i)小于等于当前的 g(m i),那么 goto 6 。否则从 open 表或 closed 表中取出与 m i相同的子结点 m i’ c)令m i: = m i’,将 m i的父指针指向 n d)将结点 m i插入到 open 表,然后将 open 表按 f值排序。 7. goto 3 10