计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程,或者说是对计算机上执行的计算过程的具体描述。无论算法有多么复杂,都必须在有限步骤之后结束并终止运行。那么计算机五大经典算法是什么呢?
计算机五大经典算法是什么
五大经典算法分为:分治法、动态规划法、贪心算法、回溯法、分支限界法。
分治法
把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征:
- 该问题的规模缩小到一定的程度就可以容易地解决
- 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解;
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
动态规划法
每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。
贪心算法
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 常见的贪心算法有:Prim 算法、Kruskal 算法(都是求最小生成树的)。
基本思路:将问题分解为若干个小问题,逐渐求得各个子问题的局部最优解,最后合并为原来问题的解。
回溯法
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。深度优先;
回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
分支限界法
类似于回溯法,也是一种在问题的解空间树 T 上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出 T 中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
计算机算法的特性
- 有穷性:一个算法应包含有限的操作步骤,而不能是无限的;
- 确定性:算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的;
- 输入性:所谓输入是指在执行算法是需要从外界取得必要的信息;
- 输出性:算法的目的是为了求解,没有输出的算法是没有意义的;
- 有效性: 算法中的每一个 步骤都应当能有效地执行。并得到确定的结果。