2

因此，在我正在编写的程序中，我使用双向广度优先搜索来搜索图形。为此，我在 1 个线程中运行 1 个广度优先搜索，然后在另一个线程中运行一个。现在，当另一个搜索中的一个元素被命中或找到目标时（这从未真正发生过，但以防万一它出于某种原因......），就说搜索找到了最佳解决方案。

我遇到的问题是，我需要将此最佳解决方案保存到一个字段中，因为我需要继续找到所有解决方案，但是由于两个线程同时命中它，该字段值变得混乱（我认为）。

有没有办法阻止对最后到达那里的线程的访问？我尝试过使用 AtomicReference 及其 compareAndSet 方法，但这并没有成功。价值仍然被搞砸了......

顺便说一句，我使用的是 java，而对于线程，我使用的是 Callable 对象。

4

2 回答 2

1

由于线程的随机顺序，您似乎有可能Livelock或正在发生这种情况。Race condition我建议采取不同的方法。（否则在某些时候你会遇到NP-Complete）。

我遇到的问题是我需要将这个最佳解决方案保存到一个字段中。因为我需要继续寻找所有的解决方案，但是由于两个线程同时命中它，所以字段值变得混乱（我认为）。

有一种方法可以大大提高您当前的技术。您不需要查看每个解决方案，采用 aGreedy Approach并使用 a Paralleled versionof Dijkstra's Shortest Path Algorithm。

最短路径（或在您的情况下为Optimal Solution）

Dijkstra 算法是一种图搜索算法，用于解决具有非负边路径成本的图的单源最短路径问题，生成最短路径树。该算法通常用于路由和作为其他图算法中的子程序。

线性实现

原始算法图1。（来源）

并行 PDF 算法 线性
（来源：iforce.co.nz）

Java 实现可以在这里和这里找到

  • 我认为这些实现是基于 BSP 树（但你应该明白）

并行实现

并行算法 图 2.（来源）

  • recursion如果您想获得优雅，还有其他方法可以加快算法速度。

并行 PDF 算法原子
（来源：iforce.co.nz）

如果您仍然遇到问题，另一个想法可能是使用不同的并发数据结构，例如Map Reduce或Hadoop代替Threads用于搜索 a Binary 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 回答