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

「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 の組で、最適解を間違えてしまうケースがあるように直観的には思えてしまうのですが、どなたかこの誤解を解いて頂けないでしょうか。

No.6 ベストアンサー 回答者： ありものがたり 回答日時： 2023/06/09 14:35

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

h(n) が許容的なら、A* は最適解を返すんです。

ヒューリスティクス関数が許容的な場合に
A*アルゴリズムの解が最適解であることの証明↓
https://ocw.hokudai.ac.jp/wp-content/uploads/201 …

この回答へのお礼

ありがとうございます！

リンクの説明がとてもわかり易いですね。

・h(n)の楽観性はゴールに近づくに連れて小さくなっていく
　→　実際の将来コストに近づく

・見当違いなノードを探索し続ければ、いずれより正しいノードのf(n)の方が小さくなり、軌道修正される

ということですね！解決しました！

お礼日時：2023/06/09 15:05

No.5 回答者： ミラ-_- 回答日時： 2023/06/09 14:15

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

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

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

この回答へのお礼

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

そうですよね。最短経路を確実に返しますよね。
ありがとうございます！

お礼日時：2023/06/09 16:05

No.4 回答者： ミラ-_- 回答日時： 2023/06/09 13:08

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

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

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

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


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

この回答へのお礼

あ、そういうことでしたか。
ミラ-_-さんが最短経路とおっしゃっているのは、最短距離のことですね。
そういうことなら、それはわかります。迷路の例えどおり壁を貫通して突き進むことはできませんものね。

必ずゴールに辿り着くルートを少なくとも1つ見つけられるのも分かります。

私が言いたかった最短経路というのは、ゴールに到達可能なルートの中で最もコストの低いもの、という意味です。
この場合の最短経路を、A*が返すと保証されているのか、もしそうだとすればどうしてか、というのが私の質問の意図です。

お礼日時：2023/06/09 13:50

No.3 回答者： stomachman 回答日時： 2023/06/09 12:27

誤解じゃないでしょう。

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

この回答へのお礼

A*では最適解を確実に見つけられる、という認識で間違っていないということですね。
ありがとうございます！

お礼日時：2023/06/09 16:57

No.2 回答者： ミラ-_- 回答日時： 2023/06/09 12:00

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

そのため、hは許容的なヒューリスティック関数で、最適解を返すことが保証されます。

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

この回答へのお礼

ありがとうございます。

ということは、ゴールに辿り着ける経路は全て最適解で、最適解 ≠ 最短経路ということでしょうか。

時間がかかっても必ず答えが見つかる、いわゆる完全性と最適解が同義という認識でよろしいしょうか。

最適、というからには、最短経路を表しているものだと考えていたのですが。

お礼日時：2023/06/09 12:26

No.1 回答者： ミラ-_- 回答日時： 2023/06/09 09:11

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*法を使用して迷路を探索すると、最適解ではないスタート地点からゴール地点までの経路を返す可能性があります。

この回答へのお礼

早速回答ありがとうございます！

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

h(m) < h(n) < h*(n) < h*(m)
のような場合は条件を満たしていると思うのですが、いかがでしょうか。実のところ、ここが分からなくて混乱しています。

お礼日時：2023/06/09 10:40