A*アルゴリズムとは何か

かの有名な A* アルゴリズムについてのメモ。
ダイクストラ法と A*, weighted A*, anytime A* について。

ダイクストラ法と A* アルゴリズム

A* アルゴリズムはグラフ上の最短経路を求めるアルゴリズムである。最短経路の素朴なアルゴリズムといえば ダイクストラ法 であるが、A* アルゴリズムダイクストラ法を一般化したものになっている。

最短経路の探索問題では経路の始点 s と終点 t が与えられるものとする。ダイクストラ法と A* アルゴリズムは、どちらも始点 s から探索を開始し "次にどのノード n を調べるか" を決定し、ノード n に到達するのにかかるコストを計算してゆく。ダイクストラ法と A* アルゴリズムの違いは "次にどのノード n を調べるか" の部分にある。ダイクストラ法では、始点 s からノード n までの距離 g(n) が最小となるようなノードを n として採用する。一方で A* アルゴリズムでは、g(n) に加えてノード n から終点 t までの距離の推定値 h(n) を考慮する。

具体的には A* アルゴリズムではノード n の評価値 f(n) を以下のように定義し、それが最小となるノード n を次に調べる。

f(n) = g(n) + h(n)

ここで g(n) は始点 s からノード n までかかるコストという実績値であり、h(n) はノード n から終点 t までかかるコストの推定値である。つまり、ノード n の "よさ" を評価するために「n に到達するのにこれだけかかる」という実績値 g(n) と「n から終点までこれくらいかかりそう」という推定値 h(n) を考慮している。こういう経験的に上手くいきそうなアルゴリズムは一般に「ヒューリスティック」と呼ばれ、A* アルゴリズムの文脈では h(n)ヒューリスティック関数と呼ばれる。なお h(n)=0 とした A* アルゴリズムダイクストラ法に一致する。

推定値 h(n) は、理想的にはノード n から終点 t までの最短距離にしたいのだが、それは最短経路を求めたい今の状況において知ることはできない。よって、ノード n から終点 t までの最短経路の近似になっているようなヒューリスティック関数 h(n) を設計してやる必要がある。本記事では、 h(n) としてノード n から終点 t までの マンハッタン距離 を採用することにする。終点 t までのマンハッタン距離が小さいのであれば終点 t までの最短経路も小さいだろう、というアイデアである。他の h(n) も考えられるが、ちゃんと最短経路を見つけるためには consistent と admissible という性質を満たすものが望ましいらしい。マンハッタン距離はこれを満たしているので求まる経路は常に最適解である。このあたりに関して軽く調べたので別の記事でまとめたい。

Weighted A*

A* アルゴリズムの派生系として重み付き A* アルゴリズム(weighted A*)が存在する。基本的なアルゴリズムの構造は A* と同様だが評価値 f(n) だけが異なる。具体的には以下のように f(n) が定義される。

f(n) = g(n) + \epsilon \times h(n)

A* アルゴリズムとの違いは \epsilon の有無だけである。ここで \epsilonヒューリスティック関数 h(n) に対する重みであり、\epsilon = 1 のとき A* に一致するし、\epsilon = 0 のときダイクストラ法に一致する。\epsilon \leq 1 のときは厳密な最短経路(つまり最適解)が求まるが、\epsilon > 1 のときは最適解が求まるとは限らない。ただし、最短経路の \epsilon 倍以内の近似解が求まることが知られているうえ、アルゴリズムの実行に要する時間は短いので有効な場合がある。このあたりについても別の記事で書きたい。

Weighted A* を実装してみた

Wikipediaの A* アルゴリズム のページを参考に Kotlin を用いて Weighted A* を実装してみた。

f(n) を考慮しながら探索を繰り返す部分を以下に示す。

fun weightedAsterCost(weight: Double): Map<P, Int>? {
    // h: heuristic function with weight
    val h = { n: P -> weight * n.distance(grid.goal) }

    val costs = mutableMapOf<P, Int>()
         .apply { this[grid.start] = 0 }
    val queue = PriorityQueue<PC>()
         .apply { add(PC(grid.start, h(grid.start))) }
    while (queue.isNotEmpty()) {
        val p = queue.poll().point
        if (p == grid.goal) return costs
        grid.neighbors(p).forEach { n ->
            val cost = costs[p]!! + p.distance(n) 
            if (costs[n] == null || cost < costs[n]!!) {
                costs[n] = cost
                queue.add(PC(n, cost + h(n)))  // f(n) = g(n) + h(n)
            }
        }
    }
    return null // the goal is unreachable
}

ここだけ切り取っても分かりづらいが、コード全体は Github 上にある

Weighted A* を実行してみた

引数の重み \epsilon を変えながら実行してみた。

実行結果を示す前に、今回の探索対象のグラフを以下に示す。濃いマスが壁であり通ることができない。

f:id:t-keita:20210308012431p:plain

左上 (0,0) が始点 s で、右下 (13, 19) が終点 t である。この間を結ぶ最短経路を求めてみる。

\epsilon = 0 の場合

まずは \epsilon = 0 としたとき、つまりダイクストラ法の実行結果を以下に示す。

f:id:t-keita:20210308023109p:plain

左の図が実際に求まった経路。もちろん始点 s から終点 t までの最短経路になっている。右の図はその過程で始点 s からの距離を求める必要があったノードを図示したものである。色の濃いノードほど始点 s からの距離が大きいことを示す。ほとんどすべてのノードを調べる必要があることが分かる。

\epsilon = 1 の場合

つぎは \epsilon = 1、つまり A* アルゴリズムの実行結果を以下に示す。

f:id:t-keita:20210308023538p:plain

左の図により最短経路が求まっていることが分かる。マンハッタン距離がよい性質をもつヒューリスティック関数 h(n) であるため、任意のグラフにおいて最短経路を求めることができる。一方で右の図より、\epsilon = 0 のときより少ないノードのみを調べていることが分かる。つまり、A* アルゴリズムではヒューリスティック関数によって「最短経路がこのノードを含むことはない」という事実が検出され、結果として調べるノードの範囲が小さくなっている。精度を落とすことなく無駄な探索は減らせるという実に上手いアルゴリズムである。

\epsilon = 2 の場合

重みが1より大きい \epsilon = 2 の場合の実行結果を以下に示す。

f:id:t-keita:20210308024316p:plain

左の図より、最短でない経路が求まってしまったことが分かる。これは重み \epsilon が大きすぎるため、終点 t に向けてまっすぐ進む力が強すぎて、最短経路を見落としてしまった状況である。ただし、求まった経路の長さが最短経路の2倍以内に収まっていることは保証されている。右の図からは \epsilon = 1 の場合よりさらに少ないノードを探索していることが(ちゃんと色のついたノードを数えれば)分かる。よって高速に動作することが期待できる。

Anytime A*

ここまでの話を聞くと「 A* では \epsilon = 1 にするのが無難で 、\epsilon > 1 は使いどころがないのでは?」と思ったに違いない。しかし、現実の問題ではグラフが巨大で最適解を出すことが難しい場合も多い。そんなときは、最適でないにせよそこそこの精度をもつ解を求めることが望ましい。

もっというと、なるべく最適解に近い解が欲しいが、途中で打ち切られたときであってもそれまでのベストの解を返すようなアルゴリズムが有用である場合がある。このようなアルゴリズムは anytime algorithm と呼ばれる。anytime な A* はそのまま anytime A* と呼ばれる。

Anytime A* - Wikipedia

anytime A* の実現方法として、weighted A* の \epsilon の値を大きなものからスタートし、徐々に \epsilon を小さくしながら1に近づけてゆく方法がある。\epsilon の大きな方が探索にかかる時間は小さいので、最適でないにせよとりあえず経路は求まる。その後、異なる \epsilon の値によってより短い経路が見つかれば、その時点での最短経路が更新される。この繰り返しの過程において、一度計算したコストを再利用するなどの手法が存在するらしい。

所感

参考文献

https://papers.nips.cc/paper/2003/file/ee8fe9093fbbb687bef15a38facc44d2-Paper.pdf