侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

前端实现贪心算法,又称贪婪算法、回溯算法

前端  /  管理员 发布于 8年前   552
目录
一、贪心算法
二、回溯算法
三、总结
参考文献

design2

# 面试官:说说你对贪心算法、回溯算法的理解?应用场景?

# 一、贪心算法

贪心算法,又称贪婪算法,是算法设计中的一种思想

其期待每一个阶段都是局部最优的选择,从而达到全局最优,但是结果并不一定是最优的

举个零钱兑换的例子,如果你有1元、2元、5元的钱币数张,用于兑换一定的金额,但是要求兑换的钱币张数最少

如果现在你要兑换11元,按照贪心算法的思想,先选择面额最大的5元钱币进行兑换,那么就得到11 = 5 + 5 + 1 的选择,这种情况是最优的

但是如果你手上钱币的面额为1、3、4,想要兑换6元,按照贪心算法的思路,我们会 6 = 4 + 1 + 1这样选择,这种情况结果就不是最优的选择

从上面例子可以看到,贪心算法存在一些弊端,使用到贪心算法的场景,都会存在一个特性:

一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法

至于是否选择贪心算法,主要看是否有如下两大特性:

  • 贪心选择:当某一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次做出的选择可以依赖以前做出的选择,但不需要依赖后面需要做出的选择
  • 最优子结构:如果一个问题的最优解包含其子问题的最优解,则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在

# 二、回溯算法

回溯算法,也是算法设计中的一种思想,是一种渐进式寻找并构建问题解决方式的策略

回溯算法会先从一个可能的工作开始解决问题,如果不行,就回溯并选择另一个动作,知道将问题解决

使用回溯算法的问题,有如下特性:

  • 有很多路,例如一个矩阵的方向或者树的路径
  • 在这些的路里面,有死路也有生路,思路即不符合题目要求的路,生路则符合
  • 通常使用递归来模拟所有的路

常见的伪代码如下:

result = []
function backtrack(路径, 选择列表):
  if 满足结束条件:
    result.add(路径)
  return

  for 选择 of 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

重点解决三个问题:

  • 路径:也就是已经做出的选择
  • 选择列表
  • 结束条件

例如经典使用回溯算法为解决全排列的问题,如下:

一个不含重复数字的数组 nums ,我们要返回其所有可能的全排列,解决这个问题的思路是:

  • 用递归模拟所有的情况
  • 遇到包含重复元素的情况则回溯
  • 收集到所有到达递归终点的情况,并返回、

用代码表示则如下:

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

# 三、总结

前面也初步了解到分而治之、动态规划,现在再了解到贪心算法、回溯算法

其中关于分而治之、动态规划、贪心策略三者的求解思路如下:

其中三者对应的经典问题如下图:

# 参考文献

  • https://zh.wikipedia.org/wiki/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95
  • https://leetcode-cn.com/problems/permutations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-mfrp/
  • https://cloud.tencent.com/developer/article/1767046

  • 上一条:
    前端实现分而治之、动态规划算法
    下一条:
    简述TCP的三次握手过程_tcp三次握手的本质理解
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 使用 Alpine.js 排序插件对元素进行排序(0个评论)
    • 在js中使用jszip + file-saver实现批量下载OSS文件功能示例(0个评论)
    • 在vue中实现父页面按钮显示子组件中的el-dialog效果(0个评论)
    • 使用mock-server实现模拟接口对接流程步骤(0个评论)
    • vue项目打包程序实现把项目打包成一个exe可执行程序(0个评论)
    • 近期文章
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 在go + gin中gorm实现指定搜索/区间搜索分页列表功能接口实例(0个评论)
    • 在go语言中实现IP/CIDR的ip和netmask互转及IP段形式互转及ip是否存在IP/CIDR(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • Laravel 11.15版本发布 - Eloquent Builder中添加的泛型(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客