首页 > 电脑常识 > 云计算

五大常规算法:分治法,动态规划算法,回朔法,贪心算法,分支定界法

admin 云计算 2021-04-26 15:56:48 算法   数据结构   面试  
后台-系统设置-扩展变量-手机广告位-内容正文底部

这里写目录标题

  • 五大常规算法
    • 动态规划算法
      • 回溯算法
      • 贪心算法
      • 分支定界法

五大常规算法

两部分组成:
分(divide):递归解决较小的问题
治(conquer):然后从子问题的解构建原问题的解

三个步骤

  1. 分解(Divide):将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
  2. 解决(Conquer):若子问题规模较小而容易被解决则直接解决,否则递归地解各个子问题;
  3. 合并(Combine):将各个子问题的解合并为原问题的解.

将 16 枚硬币分为左右两个部分,各为 8 个硬币,分别称重,必然会有一半轻一半重,而我们要的就是轻的那组,重 的舍去。接下来我们继续对轻的进行五五分
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

动态规划算法

分治法核心思想:从上往下分析问题,大问题可以分解为子问题,子问题中还有更小的子问题

  1. 动态规划也是一种分治思想,但与分治算法不同的是,分治算法是把原问题分解为若干子问题, 自顶向下,求解各子问题,合并子问题的解从而得到原问题的解。
  2. 动态规划也是自顶向下把原问 题分解为若干子问题,不同的是,然后自底向上,先求解最小的子问题,把结果存储在表格中, 在求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。

什么时候要用动态规划?

  1. 如果要求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题, 并且小问题之间也存在重叠的子问题,则考虑采用动态规划。

怎么使用动态规划?

  1. 判题题意是否为找出一个问题的最优解
  2. 从上往下分析问题,大问题可以分解为子问题,子问题中还有更小的子问题
  3. . 从下往上分析问题 ,找出这些问题之间的关联
  4. 讨论底层的边界问题
  5. 解决问题(通常使用数组进行迭代求出最优解)

回溯算法

  1. 在问题的解空间中,按深度优先遍历策略,从根节点出发搜索解空间树。
  2. 算法搜索至解空间 的任意一个节点时,先判断该节点是否包含问题的解。
  3. 如果确定不包含,跳过对以该节点为根的 子树的搜索,逐层向其祖先节点回溯,否则进入该子树,继续深度优先搜索。
  4. 回溯法解问题的所有解时,必须回溯到根节点,且根节点的所有子树都被搜索后才结束。回 溯法解问题的一个解时,只要搜索到问题的一个解就可结束。

回溯的基本步骤:

  1. 定义问题的解空间
  2. 确定易于搜索的解空间结构
  3. 以深度优先搜索的策略搜索解空间,并在搜索过程中尽可能避免无效搜索

贪心算法

特点:

  1. 贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法。
  2. 贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解),但是都是相对近似(接近)最 优解的结果。
  3. 贪婪算法并没有固定的算法解决框架,算法的关键是贪婪策略的选择,根据不同的问题选择 不同的策略。

基本思路:

  1. 建立数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解,得到子问题的局部最优解
  4. 把子问题对应的局部最优结合成原来整个问题的一个近似最优解

在这里插入图片描述

分支定界法

特点:

  1. 分支定界 (branch and bound) 算法是一种在问题的解空间上搜索问题的解的方法。
  2. 但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算 法中,每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是:

  1. 产生当前扩展结点的所有孩子结点;
  2. 在产生的孩子结点中,抛弃那些不可能产生可行解(或最优解)的结点;
  3. 将其余的孩子结点加入活结点表;
  4. 从活结点表中选择下一个活结点作为新的扩展结点。
  5. 如此循环,直到找到问题的可行解(最优解)或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点,根据选择方式的不同,分支定界算法通 常可以分为两种形式:

  1. FIFO(First In First Out) 分支定界算法:按照先进先出原则选择下一个活结点作为扩展结 点,即从活结点表中取出结点的顺序与加入结点的顺序相同。
  2. 最小耗费或最大收益分支定界算法:在这种情况下,每个结点都有一个耗费或收益。
  3. 假如要查找一个具有最小耗费的解,那么要选择的下一个扩展结点就是活结点表中具有最小 耗费的活结点.
  4. 假如要查找一个具有最大收益的解,那么要选择的下一个扩展结点就是活 结点表中具有最大收益的活结点。

文章来源:https://blog.csdn.net/m0_46376834/article/details/116135219

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/diannaochangshi/yunjisuan/674.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码