computer-science - A-Star アルゴリズムの詳細

Question

A* アルゴリズムを開始しましたが、詳細な仕組みがわかりません。

たとえば、グラフがあり、それは次のとおりです。

A -> B = 9 (最初に誤って尋ねられた 90 ではありません)

A -> C = 20

C -> D = 40

今、私はAから始めて、言及されたパスを使用してDに行きたいと思っています。

このヒューリスティック関数を使用する場合: h(n) = D までの直接的な距離 B と D の間の直接距離は 2 ですが、B と D の間にパスはありません。

私が知りたいのはそれです：

A* アルゴリズムは最初に B に行き、次に再び A に戻りますか (B と D の間にパスがないため (ゴール)?

または 私のヒューリスティック関数は許容されませんか? （教科書で見たことあるけど大丈夫）

Answer 1

そうですね、あなたの役割についてもっと詳しく教えてください。

一般的に言えば、A* はパスが存在する場合はパスを返す必要があるため、存在しないパスを無限コストとして、または単に「ここで停止」記号として扱うことができます。目的地に到達せずにパスの終点に到達すると、他の可能性がある前のノードにロールバックします。したがって、最初の質問に対する答えは「はい」です。