A * Search Algorithmでは、なぜg（n）を追加するのですか？

Per the wikipedia page A * Search Algorithmでは、なぜg（n）を追加するのですか？

... F（n）はG（N）+ H（n）は、nはパスの最後のノードであり、G（n）は、パスのコストである

を= h（n）は、nから目標までの最も安い経路のコストを推定するヒューリスティックである。

開始ノードから現在の場所までのパスのコストを考えてみませんか？私はこのアルゴリズムを問題のために実装しています。優先キューを使用していましたが、g（n）+ h（n）を実行すると、h（n）を厳密に使用するよりも時間がかかります。ヒューリスティックが正確であれば、あなたがあなたの目標にどれくらい近づいているかだけ気にしているので、h（n）を使うのは理にかなっていませんか？

EDIT：実際に私のg（n）関数が間違って計算されていることがわかりましたが、論理的にg（n）+ h（n）がh（n）

出典

2017-02-01 user74018904

そうでない場合は、不正な結果が得られることがあります。例えば、完全に有効なヒューリスティックh（n）= 0を取る。 – Henry

まあ、開始から目標までの総コストは、開始からのコスト - > n + n - >目標からのコストです。すなわち、「S→G = S→n + n→G = g（n）+ h（n）」となる。 – Kevin

[java]タグは言語に依存しないため、削除することをお勧めします。 –

g（n）を省略して誤ったアルゴリズムとなる理由を知る簡単な方法は、実際のコストが決してアルゴリズムに入り込まないという事実です。それは完全にヒューリスティックに依存しており、これは下限であることが保証されているだけです。

出典

2017-02-01 06:05:42 Henry

真（h（n）は単に推定値なので、私たちがg（n）を使用していない場合、私たちは自分たちの推定値に頼っています）。あなたのお返事ありがとう！ – user74018904

欲張り探索アルゴリズムは、F（N）=のH（N）を使用して、このような理由のために、彼らは非完全なアルゴリズム（つまり、それが解決策を見つけるために保証するものではありません）です。実際には、ヒルクライミングアルゴリズムを記述していました。

出典

2017-02-01 11:55:15

A * Search Algorithmでは、なぜg（n）を追加するのですか？

答えて

関連する問題