Python - 算法类

---

---

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

贪婪算法

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

因此，贪婪算法在那个时间点寻找简单的解决方案，而不考虑它如何影响未来的步骤。它类似于人类在不浏览所提供输入的完整详细信息的情况下解决问题的方式。

大多数网络算法都使用贪婪方法。以下是其中的一些列表 -

• 旅行推销员问题（Travelling Salesman Problem）
• Prim 最小生成树算法（Prim's Minimal Spanning Tree Algorithm）
• Kruskal 最小生成树算法（Kruskal's Minimal Spanning Tree Algorithm）
• Dijkstra 最小生成树算法（Dijkstra's Minimal Spanning Tree Algorithm）

分治算法

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

分治算法的重要示例是 -

• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• Kruskal最小生成树算法（Kruskal's Minimal Spanning Tree Algorithm）
• 二分搜索（Binary Search）

动态规划

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

大多数情况下，这些算法用于优化。在解决手头的子问题之前，动态算法将尝试检查先前解决的子问题的结果。动态算法的动机是问题的整体优化，而不是局部优化。

动态规划算法的重要示例是 -

• 斐波那契数列（Fibonacci number series）
• 背包问题（Knapsack problem）
• 河内塔（Tower of Hanoi）