Python - 算法类


算法是明确的步骤,应该通过处理零个或多个输入给我们一个明确的输出。这导致了设计和编写算法的许多方法。据观察,大多数算法可以分为以下几类。

贪婪算法

贪婪算法试图找到一个局部最优解,这可能最终导致全球优化的解决方案。但是,通常贪婪算法不提供全局优化的解决方案。

所以贪婪算法在那个时候寻找一个简单的解决方案,而不考虑它是如何影响未来的步骤的。它与人类如何解决问题的方式类似,不需要通过所提供的输入的完整细节。

大多数网络算法都使用贪婪的方法。这里列出了其中几个 -

  • 旅行推销员问题
  • Prim的最小生成树算法
  • 克鲁斯卡尔的最小生成树算法
  • Dijkstra的最小生成树算法

分而治之

这类算法涉及将给定的问题分成更小的子问题,然后独立地解决每个子问题。当问题不能进一步细分时,我们开始将解决方案合并到每个子问题上,以解决更大的问题。

分而治之算法的重要例子是 -

  • 合并排序
  • 快速排序
  • 克鲁斯卡尔的最小生成树算法
  • 二进制搜索

分而治之

动态编程涉及将较大的问题分成较小的问题,但不同于分而治之,它不涉及独立解决每个子问题。相反,较小的子问题的结果被记住并用于相似或重叠的子问题。大多数情况下,这些算法用于优化。在解决手中的子问题之前,动态算法将尝试检查先前解决的子问题的结果。

动态算法的动机是对问题进行全面优化,而不是局部优化。

动态编程算法的重要例子是 -

  • 斐波那契数列
  • 背包问题
  • 河内塔