「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ベストアンサー
- 回答日時:
h(n) が任意だと、そこそこよい(と思われる)解しか得られませんが、
h(n) が許容的なら、A* は最適解を返すんです。
ヒューリスティクス関数が許容的な場合に
A*アルゴリズムの解が最適解であることの証明↓
https://ocw.hokudai.ac.jp/wp-content/uploads/201 …
ありがとうございます!
リンクの説明がとてもわかり易いですね。
・h(n)の楽観性はゴールに近づくに連れて小さくなっていく
→ 実際の将来コストに近づく
・見当違いなノードを探索し続ければ、いずれより正しいノードのf(n)の方が小さくなり、軌道修正される
ということですね!解決しました!
No.5
- 回答日時:
はい、ゴールに到達可能なルートの中で最もコストの低いものを返すことが保証されています。
Aアルゴリズムは、ヒューリスティック関数を使用して、探索するノードを選択します。ヒューリスティック関数は、ノードからゴールまでの推定コストを返します。A*アルゴリズムは、ヒューリスティック関数で評価されたコストが最も低いノードから探索を開始し、コストが最も低いルートを返します。A*アルゴリズムは、ヒューリスティック関数が正確であれば、必ず最短経路を返します。
>はい、ゴールに到達可能なルートの中で最もコストの低いものを返すことが保証されています。
そうですよね。最短経路を確実に返しますよね。
ありがとうございます!
No.4
- 回答日時:
最適解は、最短経路を表していることが多いですが、必ずしもそうではありません。
最適解とは、問題の目的を達成するために最善の解であるものを指します。最短経路は、ゴールまでの距離が最短の解ですが、必ずしも問題の目的を達成するための最善の解とは限りません。例えば、迷路を探索する問題を考えてみましょう。迷路のスタート地点からゴール地点までの距離が100メートルだとします。最短経路は、スタート地点からゴール地点までの距離が100メートルの直線です。しかし、この経路は、迷路の中にある障害物を避けて進むことができないため、最善の解とは限りません。最善の解は、迷路の中にある障害物を避けて進むことができ、かつゴール地点までの距離が最短のルートである可能性があります。
A法は、ヒューリスティック関数が許容的である場合に、最適解を返すことが保証されています。しかし、最適解が最短経路とは限らないため、A法が最短経路を返すことは保証されていません。
また、時間がかかっても必ず答えが見つかる、いわゆる完全性と最適解が同義ではありません。完全性とは、問題の制約を満たす解が存在する場合、必ずその解が見つかるということを言います。最適解とは、問題の制約を満たす解の中で、目的関数を最大化または最小化したものを言います。完全性と最適性は、異なる概念です。完全性があるとは、必ず答えが見つかるということであり、最適解があるとは、答えが最短経路であるということではありません。
あ、そういうことでしたか。
ミラ-_-さんが最短経路とおっしゃっているのは、最短距離のことですね。
そういうことなら、それはわかります。迷路の例えどおり壁を貫通して突き進むことはできませんものね。
必ずゴールに辿り着くルートを少なくとも1つ見つけられるのも分かります。
私が言いたかった最短経路というのは、ゴールに到達可能なルートの中で最もコストの低いもの、という意味です。
この場合の最短経路を、A*が返すと保証されているのか、もしそうだとすればどうしてか、というのが私の質問の意図です。
No.3
- 回答日時:
誤解じゃないでしょう。
heuristic関数はいわば「直感」の代用品ですから、(普通は)ちょいちょい間違った方向に導くので、「全く迷わずまっしぐらで最適解に至る」というわけにはいかない。ですが少なくとも、「最適解を見つけられない」ってことはない。言い換えれば、出した解は最適解だという保証がある。それこそが「許容的」の定義ですよね。ところで、ChatGPTのコピペに質問したって、質問の意味がわかってないんだからしょうがないと思う。No.2
- 回答日時:
h(m) < h(n) < h*(n) < h*(m)の場合は、条件を満たしています。
そのため、hは許容的なヒューリスティック関数で、最適解を返すことが保証されます。
ただし、A*法は、最適解を返すことが保証されているだけで、必ず最短経路を返すとは限りません。最短経路以外の経路が存在する場合、A*法は最短経路以外の経路を返す可能性があります。
ありがとうございます。
ということは、ゴールに辿り着ける経路は全て最適解で、最適解 ≠ 最短経路ということでしょうか。
時間がかかっても必ず答えが見つかる、いわゆる完全性と最適解が同義という認識でよろしいしょうか。
最適、というからには、最短経路を表しているものだと考えていたのですが。
No.1
- 回答日時:
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)
のような場合は条件を満たしていると思うのですが、いかがでしょうか。実のところ、ここが分からなくて混乱しています。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(スポーツ) ホッケーマスクにはフルフェイス型(ジェイソンタイプ)と骨組み型(よく試合で見るやつ?)がある事を知り 2 2022/08/23 14:48
- 日本語 生娘をシャブ漬け 5 2022/04/19 19:23
- その他(悩み相談・人生相談) Yahoo!知恵袋の「不適切な情報」の基準について 9 2022/04/13 01:25
- 憲法・法令通則 次の3つの文のうち、まちがっている文はどれですか?? ①憲法上裁判所に与えられた司法権が発動するため 2 2022/06/21 00:54
- 電気工事士 平成27年度下期の問題なのですが 2 2022/08/11 20:52
- 大学受験 現代文について教えください。 問題 傍線部1「科学的方法」とあるが、それは具体的にいうとどのような方 3 2022/10/16 20:31
- その他(教育・科学・学問) 計測器について、適用可能な製品公差が標準ノギスでは0.3mm以上とありますが、詳しい方分かりやすく説 4 2022/11/21 12:05
- 計算機科学 これは迷路を解くというよりも、いかに速く最速で走り切れる経路を見出せるかや、マシン性能、プログラミン 3 2023/07/17 16:27
- 数学 確率の最大値の解説で 〜のときP[n+1]=P[n]になる のように書かれていたのですが、 P[n+ 4 2022/05/22 17:49
- 数学 最大エントロピー原理をpythonで実装したい 2 2022/06/21 13:10
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
求伏見稻荷大社和難波八阪神社...
-
判別式はyにおいても使えますか...
-
解けない問題があります
-
高1の数学でこんな感じに解の公...
-
2次・3次方程式の共通解に関...
-
二次不等式2x²−3x+m+1<0を満た...
-
たすきがけと解の公式の答えが...
-
2次不等式X^2+MX+M<0が実数...
-
解なしと実数解なしのちがいは...
-
【数Ⅰ】次の2次方程式が重解を...
-
2次方程式が実数解を持つ範囲
-
題意より の使い方あってますか?
-
三次方程式の問題
-
数学 2次方程式4x二乗−12x+9=...
-
二次関数~二つの負の解
-
共通解の問題についてです。こ...
-
「解せません」という表現
-
二次方程式の解の書き方
-
数が大きい式の因数分解をする...
-
二次方程式x^2+2(m-1)x+1=0が異...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
求伏見稻荷大社和難波八阪神社...
-
高1の数学でこんな感じに解の公...
-
2次方程式でX^2-3x+2k=0 が...
-
3次と2次の方程式の共通解
-
なぜ「異なる2つの実数解」と書...
-
共通解の問題についてです。こ...
-
なんでx軸と接しているところが...
-
二次方程式の虚数解と複素数の...
-
数学の問題集から問題をとって...
-
数学2 虚数解です。答えお願い...
-
数II、解と係数の問題
-
数2の問題について
-
因数分解 数字を早く見つける方法
-
2次方程式x^2-x-1=0の2つの解を...
-
対称行列同士の積は対称行列?
-
aを定数とする。 2次方程式 x²+...
-
√3 を連分数展開するとどうなり...
-
高校数学についてです。 以下の...
-
判別式はyにおいても使えますか...
-
Z^3(Zの3乗)=-8 の複素数解...
おすすめ情報