算法设计技术

以下是几种流行的设计方法的列表:

1.分而治之:这是一种自上而下的方法。遵循分而治之技术的算法包括三个步骤:

  • 将原始问题分为一组子问题。
  • 递归地分别解决每个子问题。
  • 将子问题(顶层)的解决方案组合为整个原始问题的解决方案。

2.贪婪技术:贪婪方法用于解决优化问题。最优化问题是给我们提供一组输入值, 这些输入值需要最大化或最小化(称为目标), 即一些约束或条件。

  • 贪婪算法总是使选择(贪婪标准)在目前看来最好, 以优化给定的目标。
  • 贪心算法并不总是保证最优解, 但是通常会产生一个与最优值非常接近的解。

3.动态编程:动态编程是一种自下而上的方法, 我们先解决所有可能的小问题, 然后将它们组合起来以解决更大的问题。

当复制子问题的数量成倍增加时, 这特别有用。动态编程通常与优化问题有关。

4.分支和边界:在分支和边界算法中, 无法约束的给定子问题必须分成至少两个新的受限子问题。分支和边界算法是非凸问题中全局优化的方法。分支和边界算法可能很慢, 但是在最坏的情况下, 它们需要的工作量随问题的大小呈指数增长, 但是在某些情况下, 我们很幸运, 而且方法的工作量也要少得多。

5.随机算法:随机算法定义为一种算法, 该算法允许访问独立的, 无偏的随机位的源, 然后允许使用这些随机位来影响其计算。

6.回溯算法:回溯算法会尝试每种可能性, 直到找到正确的可能性为止。这是一组可能解决方案的深度优先搜索。在搜索过程中, 如果替代方法不起作用, 则返回到选择点, 即提供不同替代方法的位置, 然后尝试下一个替代方法。

7.随机算法:随机算法在计算过程中至少使用随机数一次。

示例1:在快速排序中, 使用随机数选择一个轴。

示例2:尝试通过选择随机数作为可能的除数来分解大数。


循环不变式

这是一种证明技术。我们使用循环不变式来帮助我们理解为什么算法正确。为了证明关于循环的陈述S是正确的, 请定义关于一系列较小的陈述S0 S1 …. Sk的S, 其中,

  • 循环开始之前的最初要求是正确的。
  • 如果Si-1在迭代i开始之前为真, 则可以证明Si在迭代i结束之后为真。
  • 最后的陈述Sk表示我们希望证明其为正确的陈述S。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?