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

Question

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

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

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

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

Answer 1

看起来你有一个可能的 Livelock 或 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)}

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