So in a program I'm writing I use a bi-directional breadth first search to search a graph. I do this by running 1 breadth first search in 1 thread, and one in another. Now the search is said to have found the optimal solution when it either an element from the other search is hit, or when the goal is found (which never really happens, but just in case it does for some reason..).
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).
Is there a way to block access to the thread who gets there last? I've tried using an AtomicReference and its compareAndSet method but that didn't do the trick. The value still gets messed up....
Btw I'm using java, and for the threads I'm using Callable objects.
Looks like you have a possible Livelock
or Race condition
that is occuring because of the random order of threads. I'd recommending taking a different approach. (otherwise at some point you will run into 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).
There is a way to greatly increase your current technique. You shouldn't need to look at every solution, take a Greedy Approach
and use a Paralleled version
of Dijkstra's Shortest Path Algorithm
.
Shortest Path (or in your case Optimal Solution)
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.
Linear Implementation
The original algorithm Figure 1. (Source)
(source: iforce.co.nz)
Java Implementations can be found Here, and Here
Parallel Implementation
The parallel algorithm Figure 2. (Source)
recursion
, if you want to get classy.
(source: iforce.co.nz)
Another idea if you are still having problems, might be to use a different concurrent data structure like Map Reduce
or Hadoop
instead of using Threads
to search through a Binary Tree
, to fix your search.