计算机五大经典算法是什么

乐多 问答 2022-12-09 02:43:21 阅读(...)

计算机五大经典算法是分治法,把一个复杂的问题分成两个或更多的相同或相似的子问题;动态规划法;贪心算法;回溯法,一种选优搜索法,按选优条件向前搜索,以达到目标;分支限界法。

计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程,或者说是对计算机上执行的计算过程的具体描述。无论算法有多么复杂,都必须在有限步骤之后结束并终止运行。那么计算机五大经典算法是什么呢?

计算机算法 Computer algorithm

计算机五大经典算法是什么

五大经典算法分为:分治法、动态规划法、贪心算法、回溯法、分支限界法。

分治法

把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征:

  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解;
  4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

动态规划法

每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

贪心算法

在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 常见的贪心算法有:Prim 算法、Kruskal 算法(都是求最小生成树的)。

基本思路:将问题分解为若干个小问题,逐渐求得各个子问题的局部最优解,最后合并为原来问题的解。

回溯法

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。深度优先;

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

分支限界法

类似于回溯法,也是一种在问题的解空间树 T 上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出 T 中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

计算机算法的特性

  • 有穷性:一个算法应包含有限的操作步骤,而不能是无限的;
  • 确定性:算法中的每一个步骤都应当是确定的,而不应当是含糊的、模棱两可的;
  • 输入性:所谓输入是指在执行算法是需要从外界取得必要的信息;
  • 输出性:算法的目的是为了求解,没有输出的算法是没有意义的;
  • 有效性: 算法中的每一个 步骤都应当能有效地执行。并得到确定的结果。
0个人收藏 收藏

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • 模糊算法 Fuzzy algorithm

    什么是模糊算法

    模糊算法属于智能算法,当我们对于系统的模型认识不是很深刻,或者说客观的原因导致我们无法对系统的控制模型进行深入研究的时候,智能算法常常能够起到的作用很小。这个时候就需要用到模糊算法,常见的模糊算法有均值模糊、高斯模糊等。
  • 对称密钥算法 Symmetric-key algorithm

    对称密钥算法是什么

    对称密钥算法又称为对称加密、私钥加密、共享密钥加密,是密码学中的一类加密算法。这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥。事实上这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通信联系。
  • Face recognition 人脸识别

    人脸识别三大经典算法是什么

    人脸识别三大经典算法是特征脸法,近期发展起来的用于人脸或者一般性刚体识别以及其它涉及到人脸处理的一种方法;以及局部二值模式,是计算机视觉领域里用于分类的视觉算子;还有Fisherface算法,线性鉴别分析在降维的同时考虑类别信息。
  • 搜索算法 search algorithm

    搜索算法是什么

    搜索算法是解决搜索问题的任何算法,即检索存储在某个数据结构中的信息,或者在问题域的搜索空间中计算的信息。这种结构的例子包括但不限于链表,数组数据结构或搜索树。合适的搜索算法通常取决于正在搜索的数据结构,并且还可能包括有关数据的先前知识。
  • sort 排序

    排序算法稳定性是指什么

    排序算法稳定性指假定在待排序的记录序列中,存在多个具有相同的关键字的记录,经过排序这些记录的相对次序保持不变,则是稳定的;否则为不稳定。不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。
  • 确定性算法是什么

    确定性算法是什么

    确定性算法是利用问题的解析性质,产生一确定的有限或无限点序列使其收敛于全局最优解。这类方法依据某一确定性策略搜索局部极小,并试图跳跃已获得的局部极小而达到某个全局最优点,能充分利用问题的解析性质,从而计算效率高。