4

グラフを表すためのデータ構造として使用しているHashMap-HashMap(1つは地域用、もう1つは目的地を表すために地域内)、20000の地域を挿入しました。次に、2つのローカリティ間にパスが存在するかどうかを知る関数を作成する必要があります。この関数は再帰的であり、ハッシュマップのgetオブジェクトを多数作成してそれらを操作する必要があります。宛先ごとに、APIでgetメソッドを実行する必要があり、宛先を含むhashMapのコピーを取得する必要があります。プログラムを実行するたびに、Stackoverflowエラーが発生します。なぜこれが常に起こるのですか?再帰呼び出しが多いためですか?または、常にgetメソッドを呼び出して、地域の宛先のhashMapのコピーを取得する必要がありますか?

ありがとう。

4

5 に答える 5

2

スタックオーバーフローは、再帰の深さが一定の制限を超えることによって発生します。HashMapこれはおそらく;のコピーとは何の関係もありません。それはを引き起こしますOutOfMemoryError。グラフ検索を再帰的に実行している場合、エラーは次のいずれかが原因である可能性があります

  1. 深さ優先探索が深すぎる、または
  2. 再帰ロジックのバグ。

それ以上のデータがなければ、私はそれがどれであるかを言うことができません。ただし、DFSは、明示的なスタックを使用して繰り返し記述し、探索するノードを格納できることに注意してください。より多くのコードを投稿すると、より良い診断を行うのに役立ちます。

お役に立てれば!

于 2012-05-25T02:40:11.340 に答える
1

それは再帰的な呼び出しです。再帰呼び出しの各レベルはスタック上のスペースを消費するため、これらの呼び出しを多数取得すると、スタックスペースが不足します。アルゴリズムを非再帰的に変更します。

于 2012-05-25T02:40:44.877 に答える
1

助けてくれてありがとう、問題はすでに解決されています。再帰呼び出しを忘れて、DFSバリアントを選択することにしました。

于 2012-05-26T16:15:32.440 に答える
0

最短経路を見つけるためにどのアルゴリズムを使用しますか?円や負のエッジウェイトを含めることはできますか?それに応じて、Dijktra、Prim、Floyd-Warshallなどを使用します。スティーブンスキーナの「アルゴリズム設計マニュアル」、p。206ffは、さまざまな最短経路グラフアルゴリズムに関する詳細な説明を提供します。確かに、それらの多くは再帰的ではなく反復的です。

于 2012-05-25T02:49:41.433 に答える
0

小さいグラフでも同じことが起こりますか?もしそうなら、あなたはおそらく無限の再帰を引き起こすあなたの再帰にいくつかのバグがあります。小さいグラフで発生しない場合、これはあなたをノックダウンするアルゴリズムです。

于 2012-05-25T02:52:55.673 に答える