並行演算法 - 設計技巧

為並行演算法選擇合適的設計技巧是最困難和最重要的任務。大多數並行程式設計問題可能有多個解決方案。本章將討論以下並行演算法的設計技巧：

分治法

在分治法中，問題被分解成幾個較小的子問題。然後遞迴地解決子問題，並將它們組合起來以獲得原始問題的解決方案。

分治法在每一層包含以下步驟：

分治法應用於以下演算法：

在貪心演算法的最佳化方案中，在任何時刻都選擇最佳方案。貪心演算法很容易應用於複雜問題。它決定下一步哪個步驟將提供最準確的解決方案。

這種演算法被稱為貪心演算法，因為當提供較小例項的最優解時，演算法不會將整個程式作為一個整體考慮。一旦一個解決方案被考慮，貪心演算法就不會再考慮相同的解決方案。

貪心演算法遞迴地從最小的組成部分建立一組物件。遞迴是一種解決問題的程式，其中特定問題的解決方案取決於該問題的較小例項的解決方案。

動態規劃是一種最佳化技術，它將問題分解成較小的子問題，並在解決每個子問題後，動態規劃將所有解決方案組合起來以獲得最終解決方案。與分治法不同，動態規劃多次重用子問題的解決方案。

斐波那契數列的遞迴演算法是動態規劃的一個例子。

回溯法是一種解決組合問題的最佳化技術。它應用於程式設計問題和現實生活問題。八皇后問題、數獨遊戲和迷宮尋路是使用回溯演算法的常見例子。

在回溯法中，我們從一個可能的解開始，該解滿足所有要求的條件。然後我們移到下一層，如果該層沒有產生令人滿意的解，我們返回上一層並從一個新的選項開始。

分支限界演算法是一種最佳化技術，用於獲得問題的最優解。它在整個解空間中尋找給定問題的最佳解。待最佳化的函式中的界限與最新最佳解的值合併。它允許演算法完全找到解空間的部分。

分支限界搜尋的目的是維護到目標的最低成本路徑。一旦找到解決方案，它就可以不斷改進解決方案。分支限界搜尋在深度受限搜尋和深度優先搜尋中實現。

線性規劃描述了一大類最佳化作業，其中最佳化準則和約束都是線性函式。這是一種獲得最佳結果的技術，例如最大利潤、最短路徑或最低成本。

在這個程式設計中，我們有一組變數，我們必須為它們分配絕對值以滿足一組線性方程，並最大化或最小化給定的線性目標函式。

列印頁面