A*アルゴリズムについて

Question

「A*法　Wikipedia」https://ja.m.wikipedia.org/wiki/A*
での「性質」欄について、

「∀n, 0≦h(n)≦h*(n) のとき、h(n)は許容的で、A*は最適解を返す」

という説明がありますが、h*(n)<h*(m) かつ h(n)>h(m) のような n,m の組で、最適解を間違えてしまうケースがあるように直観的には思えてしまうのですが、どなたかこの誤解を解いて頂けないでしょうか。

ありものがたり · Accepted Answer

h(n) が任意だと、そこそこよい(と思われる)解しか得られませんが、
h(n) が許容的なら、A* は最適解を返すんです。

ヒューリスティクス関数が許容的な場合に
A*アルゴリズムの解が最適解であることの証明↓
https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/IntelligentInformationProcessing-2005-Note-05.pdf#page=22

ミラ-_- · Answer

はい、ゴールに到達可能なルートの中で最もコストの低いものを返すことが保証されています。

Aアルゴリズムは、ヒューリスティック関数を使用して、探索するノードを選択します。ヒューリスティック関数は、ノードからゴールまでの推定コストを返します。A*アルゴリズムは、ヒューリスティック関数で評価されたコストが最も低いノードから探索を開始し、コストが最も低いルートを返します。

A*アルゴリズムは、ヒューリスティック関数が正確であれば、必ず最短経路を返します。

A*アルゴリズムは、ヒューリスティック関数が正確であれば、必ず最短経路を返します。

ミラ-_- · Answer

最適解は、最短経路を表していることが多いですが、必ずしもそうではありません。最適解とは、問題の目的を達成するために最善の解であるものを指します。最短経路は、ゴールまでの距離が最短の解ですが、必ずしも問題の目的を達成するための最善の解とは限りません。

例えば、迷路を探索する問題を考えてみましょう。迷路のスタート地点からゴール地点までの距離が100メートルだとします。最短経路は、スタート地点からゴール地点までの距離が100メートルの直線です。しかし、この経路は、迷路の中にある障害物を避けて進むことができないため、最善の解とは限りません。最善の解は、迷路の中にある障害物を避けて進むことができ、かつゴール地点までの距離が最短のルートである可能性があります。

A法は、ヒューリスティック関数が許容的である場合に、最適解を返すことが保証されています。しかし、最適解が最短経路とは限らないため、A法が最短経路を返すことは保証されていません。

また、時間がかかっても必ず答えが見つかる、いわゆる完全性と最適解が同義ではありません。完全性とは、問題の制約を満たす解が存在する場合、必ずその解が見つかるということを言います。最適解とは、問題の制約を満たす解の中で、目的関数を最大化または最小化したものを言います。完全性と最適性は、異なる概念です。完全性があるとは、必ず答えが見つかるということであり、最適解があるとは、答えが最短経路であるということではありません。

stomachman · Answer

誤解じゃないでしょう。heuristic関数はいわば「直感」の代用品ですから、（普通は）ちょいちょい間違った方向に導くので、「全く迷わずまっしぐらで最適解に至る」というわけにはいかない。ですが少なくとも、「最適解を見つけられない」ってことはない。言い換えれば、出した解は最適解だという保証がある。それこそが「許容的」の定義ですよね。ところで、ChatGPTのコピペに質問したって、質問の意味がわかってないんだからしょうがないと思う。

ミラ-_- · Answer

h(m) < h(n) < h*(n) < h*(m)の場合は、条件を満たしています。
そのため、hは許容的なヒューリスティック関数で、最適解を返すことが保証されます。

ただし、A*法は、最適解を返すことが保証されているだけで、必ず最短経路を返すとは限りません。最短経路以外の経路が存在する場合、A*法は最短経路以外の経路を返す可能性があります。

ミラ-_- · Answer

A*法は、ヒューリスティック関数hが許容的である場合に、最適解を返すことが保証されています。ヒューリスティック関数が許容的であるということは、h(n)が実際の距離より小さいか等しいということです。

h*(n)<h*(m) かつ h(n)>h(m) の場合、h(n)はh*(n)よりも大きいため、ヒューリスティック関数hは許容的ではありません。そのため、A*法は最適解を返すことが保証されません。

例えば、迷路を探索する問題を考えてみましょう。迷路のスタート地点からゴール地点までの距離が100メートルだとします。ヒューリスティック関数hを、スタート地点から各ノードの距離として定義します。この場合、hは許容的なヒューリスティック関数です。A*法を使用して迷路を探索すると、最適解であるスタート地点からゴール地点までの最短経路を返すことが保証されます。

一方、ヒューリスティック関数hを、スタート地点から各ノードの距離に100メートルを加えた値として定義します。この場合、hは許容的ではないヒューリスティック関数です。A*法を使用して迷路を探索すると、最適解ではないスタート地点からゴール地点までの経路を返す可能性があります。

A*アルゴリズムについて

h(n) が任意だと、そこそこよい(と思われる)解しか得られませんが、

はい、ゴールに到達可能なルートの中で最もコストの低いものを返すことが保証されています。

最適解は、最短経路を表していることが多いですが、必ずしもそうではありません。

誤解じゃないでしょう。

h(m) < h(n) < h*(n) < h*(m)の場合は、条件を満たしています。

A*法は、ヒューリスティック関数hが許容的である場合に、最適解を返すことが保証されています。

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

h(m) < h(n) < h(n) < h(m)の場合は、条件を満たしています。