并行算法 - 设计技巧

为并行算法选择合适的設計技巧是最困难和最重要的任务。大多数并行编程问题可能有多个解决方案。本章将讨论以下并行算法的设计技巧：

分治法

在分治法中，问题被分解成几个较小的子问题。然后递归地解决子问题，并将它们组合起来以获得原始问题的解决方案。

分治法在每一层包含以下步骤：

分治法应用于以下算法：

在贪心算法的优化方案中，在任何时刻都选择最佳方案。贪心算法很容易应用于复杂问题。它决定下一步哪个步骤将提供最准确的解决方案。

这种算法被称为贪心算法，因为当提供较小实例的最优解时，算法不会将整个程序作为一个整体考虑。一旦一个解决方案被考虑，贪心算法就不会再考虑相同的解决方案。

贪心算法递归地从最小的组成部分创建一组对象。递归是一种解决问题的程序，其中特定问题的解决方案取决于该问题的较小实例的解决方案。

动态规划是一种优化技术，它将问题分解成较小的子问题，并在解决每个子问题后，动态规划将所有解决方案组合起来以获得最终解决方案。与分治法不同，动态规划多次重用子问题的解决方案。

斐波那契数列的递归算法是动态规划的一个例子。

回溯法是一种解决组合问题的优化技术。它应用于编程问题和现实生活问题。八皇后问题、数独游戏和迷宫寻路是使用回溯算法的常见例子。

在回溯法中，我们从一个可能的解开始，该解满足所有要求的条件。然后我们移到下一层，如果该层没有产生令人满意的解，我们返回上一层并从一个新的选项开始。

分支限界算法是一种优化技术，用于获得问题的最优解。它在整个解空间中寻找给定问题的最佳解。待优化的函数中的界限与最新最佳解的值合并。它允许算法完全找到解空间的部分。

分支限界搜索的目的是维护到目标的最低成本路径。一旦找到解决方案，它就可以不断改进解决方案。分支限界搜索在深度受限搜索和深度优先搜索中实现。

线性规划描述了一大类优化作业，其中优化准则和约束都是线性函数。这是一种获得最佳结果的技术，例如最大利润、最短路径或最低成本。

在这个编程中，我们有一组变量，我们必须为它们分配绝对值以满足一组线性方程，并最大化或最小化给定的线性目标函数。

打印页面