Python - 算法类

算法是由明确的步骤组成的，这些步骤应该通过处理零个或多个输入来给我们一个明确定义的输出。这导致了在设计和编写算法方面的许多方法。人们已经观察到，大多数算法可以分为以下几类。

贪心算法

贪心算法试图找到局部最优解，这最终可能导致全局最优解。但是，通常贪心算法并不能提供全局最优解。

所以贪心算法在当时寻找简单的解决方案，而不考虑它如何影响未来的步骤。这类似于人类如何解决问题，而不考虑所提供输入的完整细节。

大多数网络算法都使用贪心方法。这里列出其中一些：

• 旅行商问题

• Prim最小生成树算法

• Kruskal最小生成树算法

• Dijkstra最小生成树算法

分治法

这类算法包括将给定问题分解成较小的子问题，然后独立地解决每个子问题。当问题无法进一步细分时，我们开始合并每个子问题的解决方案，以得出较大问题的解决方案。

分治算法的重要例子包括：

• 归并排序

• 快速排序

• Kruskal最小生成树算法

• 二分查找

动态规划

动态规划包括将较大的问题分解成较小的子问题，但与分治法不同的是，它不涉及独立地解决每个子问题。相反，较小子问题的结果会被记住并用于类似的或重叠的子问题。

通常，这些算法用于优化。在解决手头的子问题之前，动态算法将尝试检查先前已解决的子问题的的结果。动态算法的目的是对问题进行整体优化，而不是局部优化。

动态规划算法的重要例子包括：

• 斐波那契数列

• 背包问题

• 汉诺塔