并行BFS高峰时间求解器

因此，对于uni，我们必须执行此任务，其中我们必须使高峰时间求解器的串行实现并行。解算器使用bfs实现。

以下是默认bfs实现的一部分：

// Initialize empty queue
        Queue<Tuple<byte[], Solution>> q = new Queue<Tuple<byte[], Solution>>();
        // By default, the solution is "no solution"
        foundSolution = new NoSolution();
        // Place the starting position in the queue
        q.Enqueue(Tuple.Create(vehicleStartPos, (Solution)new EmptySolution()));
        AddNode(vehicleStartPos);
        // Do BFS
        while (q.Count > 0)
        {
            Tuple<byte[], Solution> currentState = q.Dequeue();
            // Generate sucessors, and push them on to the queue if they haven't been seen before
            foreach (Tuple<byte[], Solution> next in Sucessors(currentState))
            {
                // Did we reach the goal?
                if (next.Item1[targetVehicle] == goal)
                {
                    q.Clear();
                    foundSolution = next.Item2;
                    break;
                }
                // If we haven't seen this node before, add it to the Trie and Queue to be expanded
                if(!AddNode(next.Item1))
                    q.Enqueue(next);
            }
        }
        Console.WriteLine(foundSolution);
        Console.ReadLine();

我设法把它变成了类似的东西：

ConcurrentQueue<Tuple<byte[], Solution>> q = new ConcurrentQueue<Tuple<byte[], Solution>>();
    foundSolution = new NoSolution();
    q.Enqueue(Tuple.Create(vehicleStartPos, (Solution)new EmptySolution()));
    AddNode(vehicleStartPos);
    while (q.Count > 0 && !solutionFound)
    {
        Tuple<byte[], Solution> currentState;
        q.TryDequeue(out currentState);
        Parallel.ForEach(Sucessors(currentState), (next) =>
        {
            // Did we reach the goal?
            if (next.Item1[targetVehicle] == goal)
            {
                solutionFound = true;
                foundSolution = next.Item2;
                return;
            }
            // If we haven't seen this node before, add it to the Trie and Queue to be expanded
            if (!AddNode(next.Item1))
                q.Enqueue(next);
        });
    }

正如您所看到的，我尝试用concurrentQueue实现一个并行foreach循环。我感觉concurrentQueue工作得很好，但它会自动锁定，因此花费了太多时间，使这种并行实现比串行实现慢得多。

我想有一个无等待或至少无锁定的队列，这样我就可以节省一点时间，但我不知道如何实现这一点。你们能不能深入了解一下这是否可行，以及它是否比使用常规队列更快？或者可以使用不同的并发数据结构来更好地适应这种情况。不确定ConcurrentBag之类的东西能放得多好。你能解释一下吗？

此外，在搜索了并行bfs实现之后，我找不到任何实现。对于像我这样想要并行实现bfs的人，有什么一般的提示和提示？对于队列，有哪些好的替代方案可以使其线程安全？

第1版：我设法实现了这样的任务：

int taskNumbers = Environment.ProcessorCount;
    Task[] tasks = new Task[taskNumbers];
    // Set up the cancellation token
    ctSource = new CancellationTokenSource();
    for (int i = 0; i < taskNumbers; i++)
        tasks[i] = new Task(() =>
        {
            try{    Traverse(); }
            catch{ }
        }, 
        ctSource.Token);
    for (int i = 0; i < taskNumbers; i++)
        tasks[i].Start();
    Task.WaitAll(tasks);
    ctSource.Dispose();

他们调用了一个遍历方法，看起来像这样：

 private static void Traverse()
{
    ctSource.Token.ThrowIfCancellationRequested();
    while (q.Count > 0)
    {
        Tuple<byte[], Solution> currentState;
        if (q.TryDequeue(out currentState))
        {
            foreach (Tuple<byte[], Solution> next in Sucessors(currentState))
            {
                // Did we reach the goal?
                if (next.Item1[targetVehicle] == goal)
                {
                    ctSource.Cancel();
                    foundSolution = next.Item2;
                    return;
                }
                // If we haven't seen this node before, add it to the Trie and Queue to be expanded
                if (!AddNode(next.Item1))
                    q.Enqueue(next);
            }
        }
        if (ctSource.IsCancellationRequested)
            ctSource.Token.ThrowIfCancellationRequested();
    }
}

然而，我很难弄清楚遍历方法中while循环的条件。当前条件允许任务过早退出循环。据我所知，我没有所有可用节点的完整列表，所以我无法将访问的树与所有节点的列表进行比较。除此之外，我对如何在while循环中保持任务循环没有任何其他想法，直到我找到答案或没有新节点为止。你们能帮我吗？

Thnx@Brian Malehorn感谢您的帮助，到目前为止，我设法使并行bfs版本的性能几乎与串行版本的性能持平。我现在所需要的就是让任务停留在我认为的时间循环中。