搜寻者:A* 搜寻法

首先要先说下是 A*搜寻法是是种最佳化搜寻思路方法既此搜寻法所找到路径成本总是最小也就是说从起点到终点路径是最短.

首先我先介绍两个概念:

1.最佳优先搜寻法 ( Best-First-Search )
命名为 \" 最佳优先搜寻法 \" 是个令人可敬称呼,但其实有点名过其实 , 毕竟,假如我们每次都可得知哪个点是最好下点 ,那就不用搜寻了.
在这个主题中,我们所要做是从所有可以选择点中,经由估计计算 而选出其中最好点,当成我们下点.如果估计是无所不知,当然我 们真可以每次都走最佳点 ,也就是我们所找到路径是成本最低.但实 际上估计通常无法做到这样程度. 因此,我们所选出点可能不是最佳 点,但至少是眼前最好.
因此简单说,最佳优先搜寻法就是由搜寻起点开始搜寻,然後对其作展开,并计 算其展开点经由估计所得出值 ,且选出其中最好点作为我们下个 搜寻点,再对其作展开并计算其展开点经由估计所得出值,并选出其中最 好点作为我们下个搜寻点,依此类推..........直到到达我们目标点.

2.启发式搜寻法 ( Heuristic Search Methods ) 我们可以将解决问题过程描述为状态空间的搜寻状态空间中每个状 态即代表相对应解题状况搜寻是由状态开始经系列的运算到达 目标状态为止搜寻方式可以分为基础搜寻法和启发式搜寻法两大类盲目 搜寻方式是指在搜寻过程中除了能够分别目标状态和非目标状态的外 没有其他叁考资讯；而启发式搜寻法则是在搜寻过程中可以知道目前状态 距离状态多远同时可以藉由启发估计目前状态和目标状态还有多少 距离进而增进搜寻效率

启发法则最大缺点是不能保证成功但可大量节省时间是其优点 同时对问题愈了解便能够设计出愈好启发再者启发法则执 行效率是无法分析例如在对奕程式中使用启发法则我们只能藉由 实验观察评估其效率也许在蠃了百回合的後才发现其缺点且对手 但发现了此缺点程式威力便会大减

此外并非每种问题都适合启发式搜寻法；例如:某些复杂问题 可以分解成几个小问题再分别解决问题状态改变只占原状态小 部份或问题本身在执行上无法回溯等这些不适用启发式搜寻法问 题则可以改用规划规则库专家系统学习等其他思路方法



而 A* 搜寻法主要是由下列 3种观念所合成:

1. 最佳优先搜寻法应用

既我们用最佳优先搜寻法观念来选取下个搜寻点.

2. 分枝跟界限 (Branch - and - Bound )

\" 分枝 跟 界限 \" 主要观念是说 ,如果我们已经知道有到达目标点 路径成本是 X , 若我们现在尝试对另路径搜寻, 但还没到达目标 点时其成本已经超过或等於 X , 则我们便放弃这条路径继续搜寻因 为这条路径已经不可能是最佳解了.
以下面这个图为例 :



我们要从 S 点到 G 点

我们以最佳搜寻法观念 把从起点到目前走道点成本当成我们搜寻下点 依据利用分支跟界限搜寻步骤将如,范例图所示 :












3. 动态程式规划 (Dynamic-Programming)

\" 动态程式规划 \"主要观念便是在我们搜寻过程中, 若我们发现有 两条路径可到达同点, 我们便可放弃到达那点成本较高路径 而对这条路径停止搜寻.

以下图为例, 当我们发现 S-D 成本要 4 , S-A-D 成本要 8 我们便可放弃 S-A-D 路径 继续搜寻.


这里是 A* 演算法

A* 演算法 Step1 : Put the start node S _disibledevent=>

延伸阅读