私のアルゴリズムは DEM を処理しています。DEM (数値標高モデル) は、標高がグリッド ノードで既知である地上地形の表現です。
私の問題は次のように要約できます。Q は、アクセスするノードを含むキューです。開始時に、グリッドの境界が Q にプッシュされます。
while Q is not empty, do
remove Node N from the top of Q
if N was never visited then do
consider the 8 neighbors of N
among them select the unvisited ones
among them select those with a higher elevation than N's
push these at Q's tail
mark N as visited
done
done
説明したように、アルゴリズムは、境界から継続的に上昇するパスによって到達できるすべてのノードを「訪問済み」としてマークします。キュー内のノードを処理する順序は重要ではないことに注意してください。また、いくつかのポイントは、境界から到達するために曲がりくねった上昇経路を要求する場合があることに注意してください。たとえば、円錐の周りに渦巻き状の溝があると考えてください。畝の尾根は、畝に降りることなくコーンの頂上に到達できる、独特で曲がりくねった道です。
とにかく、このアルゴリズムをマルチスレッド化したいと思います。私はまだ、獣が書かれたときに獣をデバッグする際の苦痛をできるだけ少なくするために、データとスレッドの最良の編成はどれなのか疑問に思っている最初のステップにあります.
私が最初に考えたのは、グリッドをタイルに分割し、キューをグリッド内にある数のタイルに分割することです。タイルはワークリストに積み上げられます。いくつかのスレッドが作業リストを解析し、その時点で何かを実行できるタイルを取得します。
特定のタイルで作業するには、まずタイルのキューが空でないことが必要です。ウォーカーのタイルがタイルの端にあるノードを訪問する必要がある場合は、隣接するタイルをロックできることも必要になる場合があります。
必要なときにウォーカーが隣接するタイルをロックできない場合、ローカル キューの次のノードにスキップするか、スレッド自体でタイルをワークリストに解放して別のタイルを探して、取り組む。
私のマルチスレッド プログラミングの実際の経験から、この素敵な記述がデバッグ時に悪夢に変わる可能性が非常に高いことが理解できます。しかし、アルゴリズムのプログラミングのさまざまな可能性を評価して適切な決定を下すのに十分な経験がありません。スパゲッティ皿をデバッグするための月が与えられないことを念頭に置いてください。
読んでくれてありがとう ：）