A *と貪欲な最良優先探索の違いは何ですか？

どちらのアルゴリズムも「最良優先探索」のカテゴリに分類されます。アルゴリズム。 $ g（n）$ で示される、検索空間の探索中にこれまでに取得した両方の知識を 使用できるアルゴリズムです。 $ h（n）$ で表されるヒューリスティック関数は、各ノードについて、ゴールノードまでの距離を推定します。検索スペースの$ n $ （多くの場合グラフとして表されます）。

これらの各検索アルゴリズムは、グラフ（または検索空間）内のノード $ n $ ごとに、「評価関数」を定義します。 $ f（n）$ 。この評価関数は、検索中にどのノードが最初に「展開」されるか、つまり、どのノードが最初に「フリンジ」（または「フロンティア」、または「境界」）、その子を「訪問」するため。一般に、「ベストファースト」カテゴリのアルゴリズムの違いは、評価関数 $ f（n）$ の定義にあります。

貪欲なBFSアルゴリズム の場合、評価関数は $ fです。 （n）= h（n）$ 、つまり、貪欲なBFSアルゴリズムは、最初に、ゴールまでの推定距離が最小であるノードを展開します。したがって、貪欲なBFSは「過去の知識」、つまり $ g（n）$ を使用しません。したがって、その意味合いは「貪欲」です。一般に、貪欲なBSTアルゴリズムは完全ではありません、つまり、そうでないパスをとるリスクが常にあります目標を達成します。欲張りBFSアルゴリズムでは、 border （またはフリンジまたはフロンティア）上のすべてのノードがメモリに保持されるため、すでに拡張されているノードはメモリに保存する必要がないため、破棄できます。一般に、貪欲なBFSも最適ではありません。つまり、見つかったパスが最適ではない可能性があります。一般に、時間計算量は $ \ mathcal {O}（b ^ m）$ です。ここで、 $ b $ は（最大）分岐係数であり、 $ m $ は検索ツリーの最大深度です。スペースの複雑さは、フリンジ内のノードの数と見つかったパスの長さに比例します。

Aの場合*アルゴリズム 、評価関数は $ f（n）= g（n）+ h（n）$ です。ここで、 $ h $ は、許容されるヒューリスティック関数です。多くの場合アスタリスク*で示される「星」は、A *が許容可能なヒューリスティック関数を使用するという事実を指します。これは、基本的にA *が optimal 、つまり、開始ノードとゴールノードの間の最適なパスを常に見つけます。 A *も完全です（検索スペースで探索するノードが無限に多い場合を除く）。時間計算量は $ \ mathcal {O}（b ^ m）$ です。ただし、A *は基本的に「全数検索」（ヒューリスティック関数を使用するという意味で「情報」）を実行するため、検索中はフリンジ内のノードだけでなく、すべてのノードをメモリに保持する必要があります。 。

要約すると、貪欲なBFSは完全ではなく、最適ではなく、時間計算量は $ \ mathcal {O}（b ^ m）$ および多項式である可能性のある空間計算量。 A *は完全で最適であり、時間と空間の複雑さは $ \ mathcal {O}（b ^ m）$ です。したがって、一般に、A *は貪欲なBFSよりも多くのメモリを使用します。探索空間が大きい場合、A *は実用的ではなくなります。ただし、A *は、開始ノードとゴールノードの間で見つかったパスが最適なパスであり、アルゴリズムが最終的に終了することも保証します。一方、貪欲なBFSはメモリの使用量が少なくなりますが、A *の最適性と完全性を保証するものではありません。したがって、どちらのアルゴリズムが「最良」であるかはコンテキストによって異なりますが、どちらも「最良」の最初の検索です。

注：実際には、これらのアルゴリズムを使用することはできません。代わりに、 IDA * を使用してください。

コメント

• コメントは対象外です広範な議論;この会話はチャットに移動されました。

本によると人工知能：スチュアート・ラッセルとピーター・ノーヴィグによる現代的アプローチ（第3版）、具体的には、セクション 3.5.1貪欲な最良優先探索（p。92）

貪欲な最良優先探索は、これを理由に、目標に最も近いノードを拡張しようとします。すぐに解決策につながる可能性があります。したがって、ヒューリスティック関数のみを使用してノードを評価します。つまり、 $ f（n）= h（n）$ です。

これでは同じセクションで、著者は貪欲な最良優先探索が最適でも完全でもないことを示す例を示しています。

セクション 3.5.2 A *検索：同じ本の推定総ソリューションコスト（p。93）を最小化すると、

A *検索では、ノードに到達するためのコストである $ g（n）$ と、 $ h（n）を組み合わせてノードを評価します。 $ 、ノードからゴールに到達するためのコスト $$ f（n）= g（n）+ h（n）。$$

$ g（n）$ は、開始ノードからノード $ n $へのパスコストを示すため、および $ h（n）$ は、 $ n $ には、 $ f（n）$ = $ n $ による最も安価なソリューションの推定コスト。

したがって、最も安価なソリューションを見つけようとしている場合、最初に試すのが妥当なのは、 $ g（n）+ h（n）$ の値が最も低いノードです。この戦略は合理的であるだけではありません。ヒューリスティック関数 $ h（n）$ が特定の条件を満たす場合、A *検索は完全かつ最適です。アルゴリズムは、A *が $ g $ の代わりに $ g + h $ を使用することを除いて、均一コスト検索と同じです。 span>

あなたの言ったことは完全に間違っているわけではありません、ただし、ヒューリスティック関数hが許容される場合、A *アルゴリズムは最適で完全になります。つまり、この関数は目標に到達するためのコストを過大評価することはありません。その場合、A *アルゴリズムは貪欲な検索アルゴリズムよりもはるかに優れています。

コメント

• 親愛なる回答を詳しく教えていただけますか。申し訳ありませんが、お答えできませんでした。
• @ IramShah-TemmanRafk A *が最適かつ完全であるという証明について話している。そうするためには、三角形の不等式のために、ゴールまでの残りの距離を推定するヒューリスティックが過大評価されていないことが示されている。より完全な説明を見るには、