A *は常に最短経路を提供しますか？

Question

私はA *、統一されたコストと貪欲な検索アルゴリズムがどのように機能するかを理解しようとしています。私は、ノードが3つのアルゴリズムすべてで探索される方法を知っています（欲張りはヒューリスティックな値に基づいて探索します、A *はヒューリスティック+距離に基づいて、距離に基づく均一）。

3つのアルゴリズムがすべて最短パスを提供するか（別の数の都市を調査したのか）、特定の送信元と送信先に対して異なる経路を提供できるかどうかを知りたいと思います。

私は大部分が混乱しています。ノードをキューに格納すると、宛先ノードを探索しようとしているときに最短パスがありますが、パスのキュー（およびこのキューヒューリスティック+距離に基づいてソートされています）、最短パスを取得するとは限りません。

Answer 1

必ずしもあなたのヒューリスティックによって異なります。詳しくは、this section in Wikipediaを参照してください。

要約すると、ヒューリスティックが許容可能な（これは決してコストを過大評価しないことを意味する）である場合、A *は最適解を与える。

Answer 2

実際、ヒューリスティックは許容されるべきです。さもなければ、A *は次善の解を見つけるでしょう。私はキューが次のノードの距離によって調整されるべきではないが、次のノードとして最も有望なヒューリスティックを使用することを考える。 次のノードは、現在のノードから最も離れている可能性がありますが、同時に宛先に最も近いノードである可能性があります。