Informed Search

Posted on

Search Heuristics

启发式函数$h(n)$度量当前状态到目标状态的代价估计值，以利用问题的额外信息；

对于不同的问题，采取的启发式函数也不一样，常见的启发式函数有：Manhattan距离，Euclidean距离；

称一个启发式函数是Admissible的（可采纳性），如果这个Heuristics不会过高估计当前状态到目标状态的实际代价；

称一个启发式函数是consistent的（一致性），如果对于当前结点$n$,下一步结点$n’$,和目标结点$x$,有如下三角不等式成立：
$$
h(n)\le c(n,n’,x)+h(n’)
$$
结点$n$的预估代价不会超过每个结点$n$通过某一行动到达$n’$的单步代价与结点$n’$的预估代价和；

一致的启发函数一定是可采纳的；

对于GBS来说试图拓展距离目标看起来最近的结点，也就是只利用启发信息,$f(n)=h(n)$

我们从四个方面考察GBS的性能：

  • 完备性：即使在有限状态空间中，GBS也是不完备的；
  • 最优性：往往也不能达到全局最优解；
  • 时间复杂度：$O(b^m)$;
  • 空间复杂度：$O(b^m)$;

对于A*S来说，采用的代价函数具有如下形式：
$$
f(n)=g(n)+h(n)
$$
其中，$g(n)$表示开始结点到当前结点的实际代价，$h(n)$表示当前结点到目标结点的预估最小代价；

A*S试图拓展使得$f(n)$最小的结点$n$​,下从四个方面考察Astar算法的性能：

  • 完备性：A*算法是完备的；

  • 最优性：若$h(n)$可采纳，那么树搜索版本具有最优性，若$h(n)$一致，则图搜索版本具有最优性;只需注意到当A*选择结点$n$时，就已经找到了$n$的最优路径；

  • 时间复杂度：在所有启发式算法中最优的也是效率最优的；

  • 空间复杂度：内存保留已生成的结点，因此对于大规模问题在计算完成前往往就耗尽内存

类似IDS，采用的截断值不是搜索深度而是$f$代价，但是$f$代价是一个实数，将面临和UCS一样的问题；

相对于A*，确实减少了内存需求；

RBFS

MA*

SMA*