A *検索は同じノードを複数回展開しますか？

A *検索は、Arad、Sibiuおよび他の繰り返し状態のf値を再計算したように見えます。これらのノードは、すでに展開されて閉じられているので実行してはいけません。では、私はここで何が欠けていますか？ラッセルとNorvigから（イメージ - 人工知能A *検索は同じノードを複数回展開しますか？

イメージ

：。、それはどのような彼らのF値が最適パスよりもあるので、この場合は

は、これらのノードが展開されていないではなかった場合最も近いf値が前のノードに戻った場合はどうなるでしょうか？A *はそれを行いますか？

出典

2017-03-19 Kirtiman

これは、ノードとその先行ノード間の距離が負の場合にのみ起こります。 – beaker

しかし、ここから真実ではないイメージから分かるように。 – Kirtiman

教科書は、見えているかどうかに関わらず、盲目的にすべての*接続ノードをツリーに追加しているようです。繰り返しノードを持つパスが決して最短パスになることはないため（ネガティブでない距離を仮定して）、それは問題ありません（少し無駄ですが）。チェックされ続けるが、決して最短になることはない。 – beaker

ほとんどのA *アルゴリズムはバックトラックします。逆方向ポインタが壊れてパスを回復できませんが、対角線移動がarの場合、優先キューのノードの下位ノードが訪問先ノードに低コストでアクセスできる状況が生じる可能性があります正方形の動きよりも高価です。通常、あなたはそれを無視して訪問先のノードを見分けがたいものとして扱います - あなたが変わった素晴らしいヒューリスティックを使用しているか、非常に奇妙なグラフを持っていない限り、パスの長さにはほとんど違いはありません。

出典

2017-03-19 20:29:04

アラドのヒューリスティックは、当初のものと変わりはありません。しかし、f値は持っています。 – Kirtiman

A *検索は同じノードを複数回展開しますか？

答えて

関連する問題