グラフ全体のスキャンタスク全体を高速化できるように、一方のプロセスがもう一方の以前にアクセスしたノードにステップインすることなく、2つまたはnのプロセスを使用してグラフを並行してトラバースできるアルゴリズムを見つけるために、インターネットで検索しています。しかし、私は何も見つけることができません。そのようなタスクを並行して実行するのに役立つアルゴリズムはありますか？その価値はありますか？
注：n個のプロセスは、visitedノードとtovisitノードの同じメモリを共有します
ありがとうございました
時間の大部分が実際のトラバーサルに費やされていない限り、単一のスレッドでグラフをトラバースし、複数のプロセスから並行して処理されるように各ノードで作業をキューに入れることができます。キューに入れたら、単純な生産者/消費者モデルを使用できます。
グラフをトラバースするためにコンシューマープロデューサーモデルを試すことができますが、純粋なモデルからいくつかの変更を加えます。
visitedセットも更新します。それはあなたに同期時間を節約するでしょう-それはより少ない頻度で行われる必要があるでしょう。visitedセット）を変更する場合は、セットが最後にチェックされてからすでにアクセスされたデータを追加しないように、追加の作業を行う必要があります。このアプローチでは、いくつかの頂点を数回検索する可能性が高くなりますが、キューとvisitedセットが更新される頻度でバインドできることに注意してください。
それは価値がありますか？これらのことで言うのは難しいです-それは多くのもの（グラフ構造、サイズ、キューの実装など）に依存しています。
いくつかのテストを実行し、「更新の頻度」のパラメーターを微調整して、どちらが経験的に優れているかを確認する必要があります。統計ツールを使用して（通常、ウィルコクソン検定がこれの事実上の標準です）、一方が他方より優れているかどうかを判断する必要があります。