A *グラフヒューリスティック値h（A）所与の検索

Question

= 5、H（B）= 1、それはFでフロンティアにAとBを配置します（A） = 2 + 5 = 7、f（B）= 4 + 1 = 5とすると、拡張のためにBを選択し、f（G）= 4 + 4 = 8で境界にGを置くと、 SとBの両方が既に拡張されていてフロンティアではないので何もしないので、G nextを選択して最適ではない解を返します。

私の議論は正しいですか？

Answer 1

フロンティアで順序付けられたオブジェクトの優先キューを維持します。次に、最良の候補を取り、使用可能なすべての方向に展開し、新しいノードを優先順位キューに入れます。実際には最適なパスが通過しても、Aがキューの後ろにプッシュされる可能性があります。最適以下の経路で到達したネイバーによってAが辺りをつくることも可能です。その場合、ほとんどのアルゴリズムは、あなたが言うようにそれを拡張しようとはしません。

スターは妥当なパスを見つけるための方法であり、グローバルに最適なパスを見つけることはできません。

Answer 2

ここでは2つのヒューリスティック概念がある：

1. 許容ヒューリスティック：各ノードのグラフでN、H（N）のためは決してを過大評価しない場合の目標に到達するコスト。

2. 一致ヒューリスティック：その後継のグラフと各ノードメートル、H（N）= <のH（M）+ C（n、m）は内の各ノードのN、ここで、c（n、m）は、円弧のコストです。nからmです。あなたが示されているようので

あなたヒューリスティック関数は、許容なく一貫していない。

H（A）> H（B）+ C（A、B）、5> 2。

ヒューリスティックに一貫性がある場合には、部分的な解決策の推定最終コストは常にパスに沿って成長する、すなわちF（n）は< = F（M）、我々は再び見ることができるように：

をf（A）= g（A）+ h（A）= 7f（B）= g（B）+ h（B）= 5,

このヒューリスティック関数はこの特性を満足しない。 *に関して

：

1. A *目標に開始から最短経路を見つけるために許容ヒューリスティック保証を使用。
2. A *一貫性のあるヒューリスティックを使用して、最短経路を見つけることに加えて、は、ノードが探索されると既にこのノードへの最短経路を発見したので、再探索する必要はありません。

したがって、ノードへのパスが短い場合（新しいパスコストを更新する場合）には、ノードを再オープンするためにA *アルゴリズムを実装する必要があります。この新しいパスは、したがって、Bはフロンティアに追加し直さなければならないので（今度はS-> A-> B、コスト3）という引数が正しくないので、引数が正しくないです。

A *が一貫性のあるヒューリスティック機能でのみ使用されるように制限できる場合は、すでに探索されているノードへのパスを破棄できます。