2

そのため、私が書いているプログラムでは、双方向の幅優先検索を使用してグラフを検索しています。これを行うには、1 つのスレッドで 1 つの幅優先検索を実行し、別のスレッドで 1 つの幅優先検索を実行します。現在、検索は、他の検索の要素がヒットしたとき、またはゴールが見つかったときに、最適なソリューションを見つけたと言われています (実際には決して起こりませんが、何らかの理由でヒットした場合に備えて..)。

私が直面している問題は、すべての解を見つけ続ける必要があるため、この最適な解をフィールドに保存する必要があることですが、両方のスレッドが同時にヒットするため、フィールド値が台無しになっています (おもう）。

最後にそこに到達したスレッドへのアクセスをブロックする方法はありますか? AtomicReference とその compareAndSet メソッドを使用してみましたが、うまくいきませんでした。値はまだめちゃくちゃです....

ところで、私はJavaを使用しており、スレッドにはCallableオブジェクトを使用しています。

4

2 に答える 2

1

スレッドのランダムな順序のために、可能性があるLivelockか、それが発生しているようです。Race condition別のアプローチを取ることをお勧めします。(そうしないと、ある時点で に遭遇しますNP-Complete)。

私が直面している問題は、この最適解をフィールドに保存する必要があることです。すべてのソリューションを見つけ続ける必要があるためですが、両方のスレッドが同時にヒットするため、フィールド値が台無しになっています (私は思う)。

現在のテクニックを大幅に向上させる方法があります。すべてのソリューションを見る必要はありませGreedy Approachん。Paralleled versionDijkstra's Shortest Path Algorithm

最短パス (またはあなたの場合は最適なソリューション)

Dijkstra のアルゴリズムは、非負のエッジ パス コストを持つグラフの単一ソース最短パス問題を解決し、最短パス ツリーを生成するグラフ検索アルゴリズムです。このアルゴリズムは、ルーティングでよく使用され、他のグラフ アルゴリズムのサブルーチンとして使用されます。

線形実装

元のアルゴリズム 図 1. ( Source )

並列 PDF アルゴリズム 線形
(出典: iforce.co.nz )

Java 実装は、こことここにあります。

  • これらの実装は BSP ツリーに基づいていると思います (ただし、アイデアは理解できるはずです)。

並列実装

並列アルゴリズム 図 2. ( Source )

  • recursion上品にしたい場合は、 を使用してアルゴリズムを高速化する方法が他にもあります。

並列 PDF アルゴリズム アトミック
(出典: iforce.co.nz )

それでも問題が解決しない場合の別のアイデアは、 を使用して検索する代わりに または のような別の同時データ構造を使用Map Reduceして、検索を修正することです。HadoopThreadsBinary Tree

于 2012-09-11T00:58:11.947 に答える
1

注：答えではなく、アルゴリズムの有効性を確認するだけです

あなたのアルゴリズムは実際に最短経路を生成しますか? 次のグラフを検討してください。

 1A - 2A - 3A - 4A - 5A
  \             /     
   -- 2B -------

そして、完全に織り交ぜられていると仮定します (各スレッドがまったく同じレートでノードを訪問します)。スレッドXは から始まり1A、スレッドYは から始まり5Aます。順序は次のようになります。

X visits 1A +{2A, 2B}
Y visits 5A +{4A}
X visits 2A +{3A}
Y visits 4A +{3A, 2B}
X visits 2B +{4A}
Y visits 3A +{2A}
X visits 3A (overlap; shortest path is computed to be 4)

しかし、調べてみると、最短経路は 3: であることがわかっています1A - 2B - 4A - 5A。

あなたのアプローチはどのようにこのケースを防ぎますか? 重複をチェックするためにどのアプローチを採用しても、3A前に重複が常に表示され2Bます。最適なパスの長さを決定する前に、常に「レベル」を仕上げますか?

于 2012-09-11T01:00:04.270 に答える