ウィキペディアは、A *の複雑さについて次のように述べています（リンクはこちら）。
時間計算量よりも問題なのは、A*のメモリ使用量です。最悪の場合、指数関数的な数のノードも記憶する必要があります。
これが正しいとは思えません。理由は次のとおりです。
後続のB、C、およびDとともにノードAを探索するとします。次に、B、C、およびDを開いているノードのリストに追加します。それぞれにAへの参照が付いており、Aを開いているノードから閉じているノードに移動します。ノード。
ある時点で、Aを経由するパスよりも優れたBへの別のパス（たとえば、Q経由）を見つけた場合、必要なのは、BのAへの参照を変更してQをポイントし、実際のコストg（そして論理的にf）。
したがって、ノードにその名前、参照ノード名、およびそのg、h、fスコアを格納すると、格納されるノードの最大数はグラフ内の実際のノード数になりますね。アルゴリズムが最適な（最短）パスの長さに対して指数関数的な量のノードをメモリに格納する必要がある理由を、私は本当に理解できません。
誰か説明してもらえますか？
編集あなたの答えを読んでいると理解しているので、私は問題の間違った観点から推論していました。私は与えられたグラフを当然のことと思っていましたが、指数関数的な複雑さは、「分岐係数」によってのみ定義される概念的なグラフを指します。