java - 限制对字段的并发访问

Question

因此，在我编写的程序中，我使用双向广度优先搜索来搜索图形。我通过在 1 个线程中运行 1 个广度优先搜索，然后在另一个线程中运行 1 个广度优先搜索来实现此目的。现在，当搜索来自另一个搜索的元素被命中时，或者当目标被发现时(这从未真正发生过，但以防万一由于某种原因发生......)，据说搜索已经找到了最佳解决方案。 p>

我遇到的问题是，我需要将这个最佳解决方案保存到一个字段中，因为我需要继续查找所有解决方案，但是字段值变得困惑，因为两个线程都在同时(我认为)。

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

顺便说一句，我正在使用 java，对于线程，我正在使用 Callable 对象。

Answer 1

看起来您可能有一个活锁或Race condition这是由于线程的随机顺序而发生的。我建议采取不同的方法。 (否则在某些时候你会遇到 NP-Complete )。

The problem I am running into, is that I need to save this optimal solution to a field. because I need to continue to find all of the solutions, but the field value is getting messed up because both threads hit it at the same time (I think).

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

最短路径(或在您的情况下最佳解决方案)

Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

线性实现

原始算法图1。( Source )

_{(来源:iforce.co.nz)}

Java 实现可以找到 Here ，和 Here

• 我认为这些实现是基于 BSP 树(但您应该明白)

并行实现

并行算法图2。( Source )

• 如果您想变得优雅，还有其他方法可以通过递归来加速算法。

_{(来源:iforce.co.nz)}

如果您仍然遇到问题，另一个想法可能是使用不同的并发数据结构，例如MapReduce或Hadoop，而不是使用Threads > 通过二叉树进行搜索，以修复您的搜索。