并行算法 - 设计技术

为并行算法选择合适的设计技术是最困难和最重要的任务。大多数并行编程问题可能有不止一种解决方案。在本章中，我们将讨论以下并行算法的设计技术 −

分而治之法

在分而治之的方法中，问题被分为几个小子问题。然后对子问题进行递归求解并合并得到原问题的解。

分而治之的方法在每个级别都涉及以下步骤 −

分而治之的方法应用于以下算法中 −

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

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

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

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

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

回溯是一种解决组合问题的优化技术。它适用于程序和现实生活中的问题。八皇后问题、数独谜题和走迷宫都是使用回溯算法的常见例子。

在回溯中，我们从一个可能的解决方案开始，它满足所有必需的条件。然后我们进入下一个级别，如果该级别没有产生令人满意的解决方案，我们将返回一个级别并从一个新选项开始。

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

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

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

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