0

以下に示すようなグラフを作成するプログラムがあります

作成したグラフの構造

アルゴリズムは緑色のノードから開始し、グラフをトラバースします。画像の赤い点で示されているグラフに、ノード (左、右、上、下の 4 つの参照を持つリンク リスト タイプのノード) が追加されたとします。新しく作成されたノードを隣接するノードと統合するには、4 つのオブジェクトを見つけてリンクし、グラフの接続が保持されるようにする必要があります。

以下は、私が明確にする必要があるものです

  1. 黄色のノードはすべて null であり、新しく作成されたノードの隣接ノードの存在を見つける最も効率的な方法は、ノードをマップするための別のデータ構造を保持していないとします。DFS、BFS などの基本的なグラフ検索アルゴリズムと最短パス アルゴリズムは知っていますが、グラフには約 10000 個のノードがあり、グラフ検索アルゴリズム (緑色のノードから開始) を実行して、新しいノードが追加されたときの隣人は、私には計算コストがかかるようです。
  2. グラフ検索が避けられない場合、最良の代替構造は何ですか。大きな多次元配列を考えました。ただし、これにはメモリの浪費があり、負のインデックスがないという問題もあります。画像のグラフは任意の方向に成長できるためです。これに対する私の解決策は、配列ベースのデータ構造で構成される別のクラスを作成して、負のインデックスを表現することです。ただし、このオプションを選択する前に、新しい構造に解決せずに問題を解決し、多くの再作業を節約できるかどうかを知りたい.

フィードバックをいただき、この質問を読んでいただきありがとうございます。

4

3 に答える 3

1

あなたのことを正しく理解しているかどうかわかりません。あなたは__したいですか

  • (0,0) から (x1,y1) へのパスがあることを確認します

また

  • (x1,y1) の近傍のいずれかがグラフにあるかどうかを確認しますか? ((0,0)からこのネイバーのいずれにもパスがない場合でも)。

パスを探していると仮定します (それ以外の場合は、リンクされたリストを使用しません)。これは、(0,0) へのパスを持たないポイントを格納できないことを意味します。

また、2D リンクリストの代わりに / 以外のデータ構造を使用したくないとおっしゃいました。

完全なグラフ検索を避けることはできません。BFS と DFS は古典的なアルゴリズムです。あなたが最短経路を気にしているとは思いません-どんな経路でも構いません。

検討できるもう 1 つのアプローチは、A* (簡単な説明はこちら) またはその変形の 1 つ (こちらを参照) です。

別のデータ構造はノードのセットです (各ノードはもちろん < x,y > のペアです)。4 つのチェックを簡単に実行して、隣接するものが既にセットに含まれているかどうかを確認できます。チェックと追加の両方に O(n) スペースと O( logn ) 時間がかかります。プログラミング言語がペアをセットのノードとしてサポートしていない場合は、代わりに単一の整数 (x*(Ymax+1) + Y) を使用できます。

于 2013-06-29T17:53:46.800 に答える
0

データ構造を機能させることはできますが、おそらく効率的ではありません。そして、それは大変な作業になります。

現在のデータ構造では、A* 検索 (基本的な説明についてはhttps://en.wikipedia.org/wiki/A *_search_algorithm を参照) を使用して、ポイントへのパスを見つけることができます。次に、その時点で小さな男がいるふりをして、右手を壁に置き、ポイントを時計回りに回してもらいます。彼が戻ってきたとき、彼は残りを見つけているでしょう。

時計回りに彼の道を見つけるとはどういう意味ですか? たとえば、あなたが隣人から離れて彼の要点に到達するとします。次に、あなたの男は、隣人がいる右、上、左の最初に直面する必要があります。彼が右に行くことができれば、彼はそうするでしょう、そして彼は下、右、上、そして左の方向を試みます. (右手を壁に置いて迷路を通り抜けようとしているところを想像してみてください。)

この方法は狂気です。

より簡単に操作できる 2 つの代替データ構造を次に示します。

四分木を使用できます。説明については、 http://en.wikipedia.org/wiki/Quadtreeを参照してください。これにより、ノードの挿入は時間的に対数的になります。隣人を見つけることも対数です。そして、あなたが持っているデータのためのスペースだけを使用しているので、グラフが非常に広がっていても、これはメモリ効率が良いです.

または、正と負の両方のインデックスを取る配列の型のクラスを作成できます。次に、正と負の両方のインデックスを取る 2 次元クラスになるように構築されたもの。内部では、そのクラスは通常の配列とオフセットとして実装されます。したがって、正または負の数値で開始できる配列です。オフセットの前にあるデータの一部を挿入しようとする場合は、配列の長さの一定の分数だけその部分の下にある新しいオフセットを作成し、新しい配列を作成して、データを古いものから新着。現在、隣人の挿入/検索は通常O(1)行われていますが、メモリを非常に浪費する可能性があります。

于 2013-06-29T17:43:55.413 に答える
0

四分木や r-tree のような空間インデックスを使用できます。

于 2013-06-29T17:38:55.170 に答える