启发式搜索 启发式信息加速搜索 盲目搜索的缺陷 改进： 改进：根据与问题相关的 知识问题，引入启发式信 息。 策略： 策略：从初始结点S 出发 ，选择离目标最近的子节 点扩展。 定义： 定义：f f( (n n) ) 为 为经过结点n的 且从起点到目标的最短路 径长度的估计函数。 f(n) 的值越小，表示路径越短引入 f f ( ( n n ) ) 的搜索过程 f(n)f 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= ? ?引入 g g ( ( n n ) ) 、 、 h h ( ( n n ) ) 的搜索过程f f ( ( n n ) ) f f *( *( n n ) )八数码问题启发式搜索算法A 算法 定义g(n) 为已发现的初始结点到结点n所有 路径中的最短路径的代价。 定义h(n) 为结点n到目标结点的最短路径长 度的估计，也称启发
