2

我的算法正在处理 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

如上所述，该算法将通过连续上升的路径从边界到达的每个节点标记为“已访问”。值得注意的是，队列中节点的处理顺序并不重要。另请注意，某些点可能会要求从边界到达曲折的上升路径。例如，想象一个圆锥体，其周围有一个螺旋形的沟。犁沟的脊是一条独特而曲折的路径，能够到达圆锥体的顶部，而不会下降到犁沟中。

无论如何，我想多线程这个算法。我仍然处于想知道哪个是最好的数据和线程组织的第一步，以便在编写野兽时尽可能减少调试痛苦。

我的第一个想法是将网格划分为瓦片，并将队列拆分为网格中的瓦片。瓷砖堆积在工作清单中。一些线程正在解析工作列表，并抓取当前可以做某事的任何图块。

处理特定图块首先需要图块的队列不为空。如果步行者的瓷砖必须访问瓷砖边缘的节点，我可能还需要锁定相邻的瓷砖。

我在想，当步行者无法在需要时锁定相邻的瓦片时，它可以跳到本地队列中的下一个节点，甚至线程本身也可以将瓦片释放到工作列表并寻找另一个瓦片从事于。

我对多线程编程的实际经验足以理解，这个可爱的描述很可能在我调试时变成一场噩梦。但是，我没有足够的经验来评估对算法进行编程的各种可能性并做出正确的决定，因为我不会有一个月的时间来调试意大利面。

谢谢阅读 ：）

4

0 回答 0