algorithm - 「A*」(A STAR) アルゴリズムを見つける方法は?

Question

私の直感と仮定では、貪欲を使用できない場合は常に A* を使用することになりますが、100% 確実ではありません。A* アルゴリズムを認識して特定する方法について、さらにいくつかの例とパターンが必要です。

あなたが最初にそれを見て、これが貪欲ではないこと、またはわざわざ試してみなくてもA *でなければならないことを知っているとき、誰かがいくつかの特別な極端なケースを与えることができますか.

Answer 1

通常、貪欲という用語は、バックトラックしないアルゴリズムを表すために使用されます。これらは、ヒューリスティック (通常はかなり「局所的な」もの) を最大化することによって選択を行い、その選択を再検討しないアルゴリズムです。貪欲なアルゴリズムとは、ケーキを脇に置いて別のケーキが良いかどうかを調べるのではなく、ケーキを選んですぐに食べる人のことだと考えてください。

対照的に、A*はバックトラッキング アルゴリズムです。おそらくある程度詳細に選択肢を検討しますが、後でこれらの選択肢を放棄して、他の可能性を試すことができます。

そのため、問題に「行き止まり」(極大値) があり、解決に向けてそれ以上進むことができない場合、貪欲なアルゴリズムはおそらく適切ではありません。しかし、それは必ずしも A* とそのバリアントが唯一の選択肢であることを意味するわけではありません。行き止まりから逃れるためにさまざまな手法を使用する検索アルゴリズムには、他にも多くの種類があります。シミュレーテッド アニーリング、モンテカルロ木検索、タブー検索、粒子群最適化などです。

Answer 2

貪欲なアルゴリズムが失敗する典型的なケースは、ゴール近くで行き止まりになっている廊下の状況です。ゴールまでの距離のヒューリスティックがある場合、それらの場所はゴールに近いため、貪欲なアルゴリズムは廊下を進みます。例えば、

_ _ _ _ _ _ _ _ _ _
| . S . . . . | G |
| . _ _ _ _ _ | . |
| . . . . . . . . |
| _ _ _ _ _ _ _ _ |

エージェントが最初からゴール (S) に到達するには、ゴール (G) から「離れて」行かなければならないことに注意してください。これは貪欲なアルゴリズムが示唆するものではありません。

Answer 3

A* は、単一ソース、単一宛先の最短パス アルゴリズムです。

目前の問題を最短距離問題として提示できる場合に使用できます。過大評価しないヒューリスティックを見つけることができます (たとえば、ユークリッド距離を使用します)。