并行广度优先搜索

我比较两种广度优先搜索算法的时间执行差异。平行和非平行。但是对于我制作的每个图表而言，非并行版本比并行版本快10倍。并行广度优先搜索

这是平行的广度优先搜索。我不知道问题出在哪里，但我在此方法中假设的地方：

public static int PBFS(Node start, Node end) 
{ 
    var queue = new ConcurrentQueue<Node>(); 
    queue.Enqueue(start); 

    while (queue.Count != 0) 
    { 
     bool isFinished = false; 
     if (isFinished) break; 

     Parallel.ForEach<Node>(queue, CurrentNode => 
     { 
      if (queue.TryDequeue(out CurrentNode)) 
      { 
       foreach (Node Child in CurrentNode.Children.Keys) 
       { 
        if (Child.IsVisited == false) 
        { 
         Child.IsVisited = true; 
         if (Child == end) { isFinished = true; return; } 
        } 
        queue.Enqueue(Child); 
       } 
      } 
      return; 
     }); 
    } return 1; 
}

这是不平行的BFS：

public static int BFS(Node start, Node end) 
{ 
    Queue<Node> queue = new Queue<Node>(); 
    queue.Enqueue(start); 

    while (queue.Count != 0) 
    { 
     Node CurrentNode = queue.Dequeue(); 
     CurrentNode.IsVisited = true; 

     foreach (Node Child in CurrentNode.Children.Keys) 
     { 
      if (Child.IsVisited == false) 
      { 
       Child.IsVisited = true; 
       //Console.Write(Child.Name+" "); 
       if (Child == end) return 1; 
      } 
      queue.Enqueue(Child); 
     } 
     // Console.WriteLine(); 
    } 

    // Console.WriteLine(); 
    return 0; 
}

来源

2012-09-06 bljuvko

我知道这不是你要求的，但你的并行代码总是返回1.我建议将'isFinished'的声明移到while循环之外，并将它调用为'found'。然后，在你的函数结束时，如果'found'返回1，否则返回0。 –

返回只是因为函数是int。并不意味着什么 – bljuvko

您可以通过在'while循环的每次迭代开始时创建一个新临时'ConcurrentQueue '来移除少量争用，将子队列入队列，然后使'queue'引用您的（现在是完整的）临时队列，在'while循环的每次迭代结束时。 –

并行化和并发性与共享数据需要同步。同步是很昂贵的 - 正如你可能目睹的那样。 ConcurrentQueue有它自己的同步，这可能不是您的情况最佳。

超出CPU数量的并行化（这可能不是在这里发生的，但它是相关的）会产生大量的上下文切换 - 这很昂贵并降低了并行运行的代码的生产率。即在一个问题上抛出更多线程的前提常常会产生相反的效果。

如果性能是一个问题，我想你可能想看看不同的设计，可能是Actor-based，message-passing或producer/consumer，以避免共享数据并避免共享数据的同步。

来源

2012-09-06 17:41:11

我建议你先写一个并行双向BFS：你创建两个搜索线程，一个从开始节点沿着“箭头”开始，另一个从目标节点开始反向，并终止两者当他们的搜索边界“相遇”时。例如，在Java中看起来像[this]。

来源

2013-03-27 12:34:02 coderodde

并行广度优先搜索

回答

相关问题