A* 搜寻法

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

首先我先介绍两个概念：

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

2.启发式搜寻法 ( Heuristic Search Methods )

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

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

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

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

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 on a list called OPEN . Set g(S)<---0 and f(S)<--h(S) Step2 : If OPEN is empty, exit with failure; otherwise continue. Step3 : Remove from OPEN that node n whose f-value is smallest and put it on a list called CLOSED. Step4 : If n is a goal node, exit with the solution path obtained by tracing back through the pointers; otherwise continue. Step5 : Expand node n, generating all of its successors. ( If there are no successors, go to Step2. For each successor ni, compute gi<---g(n)+c(n,ni). c(n,ni) 是由 n 点到 n的第 i 个 successor 的成本 Step6 : If a successor ni is not already on either OPEN or CLOSED, set g(ni)<---gi and f(ni)<---gi+h(ni). Put ni on OPEN and direct a pointer from it back to n. Step7 : If a successor ni is already on OPEN or CLOSED ,and if g(ni)>gi, then update it by setting g(ni)<---gi and f(ni)<---gi+h(ni) Put ni on OPEN if it was on CLOSED and redirect to n the pointer from ni. Step8 : Go to Step2 .

文章出处：http://dev.gameres.com/Program/Abstract/a8.htm