1

私はダイクストラのアルゴリズムをいじっていて、それに関する多くのサイトとコードスニペットを見つけて、それを把握できると思いますが、グラフ自体を作成する方法に関する情報は見つかりませんでした. Google検索の正しい用語がわからないかもしれませんが、グラフを作成する方法に関する情報が見つかりません。

私は学習プロジェクトとして小さな C++ パックマン ゲームを作成しており、このアルゴリズムを使用してパックマンに続くゴーストを制御したいと考えています。マップ (ビットマップ) があり、迷路の各交差点に「ノード」を配置したいと考えています。

どうすればいいですか？これは私が理解できないビットです。グラフ自体を作成する方法は?

多分ビジュアルグラフエディタはありますか? どんなアドバイスも素晴らしいでしょう。

4

3 に答える 3

2

グリッドはグラフと考えることができ、検索空間の表現はグラフを使用して表示できます。

グリッドがどのようにグラフに似ているかの図

ブロック A、B、C、D はグラフのノードであり、ノード間の重みはノード間のパス距離を表すことができます。

于 2012-07-29T10:26:50.593 に答える
1

グラフはプログラムで定義できます。一般的な表現については以下で説明します (注: ジクスタのアルゴリズムでは、さまざまなエッジの重みも格納する必要があります)。たとえば、グラフで A が B に接続され (重み = 5)、B が C に接続されている (重み = 1) とします。

1)隣接リスト: エッジをリストとして表すために使用され、スパース グラフでより一般的に使用されます。A->B(5) と B->C(1) になります。(リンクされたリストの各ノードが発信頂点の識別と重みを格納する、リンクされたリストの配列としてプロマティックに表すことができます)

2)隣接行列: 次のように定義された 2 次元行列があります。

    A B C
A   0 5 0
B   0 0 1
C   0 0 0

編集: グラフに関するこのトップコーダー チュートリアルシリーズで、より詳細な情報を見つけることができます: セクション 1 ではグラフ表現について、セクション 3 ではダイクスタ アルゴリズムについて説明します。

于 2012-07-29T09:45:34.637 に答える