並行廣度優先搜索

我比較兩種廣度優先搜索算法的時間執行差異。平行和非平行。但是對於我製作的每個圖表而言，非並行版本比並行版本快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

並行廣度優先搜索

回答

相關問題