16
ウィキペディア（link here）以下*の複雑さにこう述べています。その時間 複雑さは、*」sのメモリ使用量よりも、A *指数関数の複雑さがなぜメモリ上にあるのですか？
より問題。 最悪のケースでは、 指数的な数のノードも覚えておく必要があります。私があるため、これが正しいか確認するために失敗
：その後、我々は、オープンノードのリストにB、C、及びDを追加
我々は後継B、C、およびDを用いて、ノードAを探索言います、各ノードはAへの参照を伴い、Aを開ノードから閉ノードに移動する。
ある時点でAを通るパスよりもBへの別のパス（Qを経由している）が見つかった場合は、Bの参照をAに変更してQを指すようにして、コスト、g（および論理的にf）。
したがって、名前、参照ノード名、およびg、h、fスコアをノードに格納すると、格納される最大ノード数はグラフ内の実際のノード数になります。それ？私は本当になぜアルゴリズムが最適（最短）パスの長さに指数関数的な量のノードをメモリに格納する必要があるのか理解できません。
説明できますか？私は今、あなたの答えを読んで理解し
編集、私は、問題の間違った観点から推論されました。私は、与えられたグラフを指摘したが、指数関数的複雑さは、概念的グラフであり、これは単に "分岐因子"によって定義されたのグラフを参照している。
簡潔で簡潔なので、間違いを一度に理解できました。いい答えだ。 – Paul
実際、Wikipediaのテキストでは、「最悪の場合、展開されるノードの数は解の長さ（最短パス）で指数関数的」となっています。 –
@ziggystar私はA *アルゴリズムで作業していますが、アルゴリズムの実行時間の複雑さを見つける方法がわかりません。私は障害物がある2Dグリッドを持っており、2点間の最短経路を探します。詳細はhttp://stackoverflow.com/questions/16141678/how-to-compute-the-running-time-of-a-star-algorithmです。どのように私はスターの実行時間を知るのですか？ありがとう。 – Kraken