1

As the title says, I'm looking for the best way to do a parallel BFS in C#. I want it to be as fast as possible and use as little memory as possible. If there is no 'best' way, what are good options?

I want to use this for solving a puzzle (in my case Rush Hour). My current algorithms use a taboo HashSet which contains all previously explored states. This prevents high memory usage and significantly increases the speed of the algorithm. I currectly have a sequential and a parallel version of my algorithm. The sequential version is always faster or equally fast. This is my current parallel code:

public static void SolveParallel(Board start)
{
    ConcurrentQueue<Board> q = new ConcurrentQueue<Board>();
    q.Enqueue(start);
    HashSet<Board> taboo = new HashSet<Board>();
    taboo.Add(start);
    Board goal = null;

    ParallelOptions po = new ParallelOptions();
    po.MaxDegreeOfParallelism = Environment.ProcessorCount;

    while ((q.Count > 0) && (goal == null))
    {
        Parallel.ForEach<Board>(q.Take(q.Count), po, (b, state) =>
        {
            foreach (Board succ in b.Successors(taboo))
            {
                if (succ.Solved)
                {
                    state.Stop();
                    goal = succ;
                    return;
                }
                else
                    q.Enqueue(succ);
            }
        });
    }
    // Print solution (ignore this).
    if (goal != null)
        PrintSolution(goal);
    else
        Console.WriteLine("No solutions found");
}

Now there are problems with this I can see myself.

  1. ConcurrentQueue is not wait-free. I assume it has built-in locks which makes it use extra time.
  2. If the solution is found, other iterations of the Parallel.ForEach will continue running. I have tried solving this with cancellation tokens and parallel states, but it doesn't seem to work (or at least it doesn't improve the running time).
  3. States can be explored multiple times, since a state can be found in multiple iterations of the foreach loop before it is added to the taboo list.
  4. I'm not sure if Parallel.ForEach is the best way to solve my problem.

I have searched around the internet, including stackoverflow, but I can't find any algorithm that solves the problem. Everyone seems to use Parallel.ForEach and ConcurrentQueue. But I'm sure there are better options.

Any help is appreciated!

4

0 回答 0