算法计划与分析|5个算法

程序员 · 2024-10-5 03:40:16

1）分治法
对于一个规模为n的标题，若该标题可以容易地办理（比如说规模n较小），则直接办理；否则将其分解为k个规模较小的子标题，这些子标题相互独立且与原标题情势类似，递归地解这些子标题，然后将各子标题标解归并得到原标题标解。
2）回溯法（深度优先）
回溯法是一种选优搜索法，按选优条件向前搜索，以到达目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技能就是回溯法。
3）贪心法
总是做出在当前来说是最好的选择，而并不从团体上加以思量，它所做的每步选择只是当前步调的局部最优选择，但从团体来说不愿定是最优的选择。由于它不必为了探求最优解而穷尽全部大概解，因此其泯灭时间少，一样平常可以快速得到满足的解，但得不到最优解。
4）动态规划法
在求解标题中，对于每一步决议，列出各种大概的局部解，再依据某种判断条件，舍弃哪些肯定不能得到最优解的局部解，在每一步都颠末筛选，以每一步都是最优解来包管全局是最优解。
5）分支限界法（广度优先）

分治算法求出的子标题是相互独立的。
动态规划算法具有最优子结构性子和重叠子标题性子。
贪默算法不追求最优解，只求可行解，因此不具备最优子结构的特性。
回溯算法把标题标解空间转化成图大概树结构，然后利用深度优先搜索战略举行遍历，遍历的过程中记载和探求全部可行解大概最优解。
分支限界算法类似于回溯算法，它以广度优先方式搜索解空间树。

算法计划与分析|5个算法

所属分类: 问答交流

新帖推荐: 30日

推荐作品