算法思想

sshe 发布于2019-08-15 17:50 / 3192人阅读

摘要：基础算法思想类别递推枚举递归分治贪婪回溯试探模拟递推递推分类顺推法从已知条件出发，逐步推算出要解决问题的方法。贪心算法的局限不能保证最后的解是最优的不能求最大最小解问题只能求满足某些约束条件的可行解范围。

基础算法思想类别

递推

枚举

递归

分治

贪婪

回溯（试探）

模拟

递推 递推分类

顺推法：从已知条件出发，逐步推算出要解决问题的方法。

逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

递推算法的经典运用

斐波那契数列（顺推法）：由n-2，n-1项得到第n项银行存款（逆推法）

枚举

将问题的所有可能答案都列举出来，根据判断条件判断此答案是否合适，一般用循环实现。

枚举算法的经典运用

百钱买百鸡、填写运算符

递归

递归算法在函数或子过程的内部，直接或间接调用自己的算法

递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解

注意：必须有一个明确的递归结束条件；如果递归次数过多，容易造成栈溢出。

递归算法的经典运用

汉诺塔问题、阶乘问题

分治

　　将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

分治算法的基本步骤

分解，将要解决的问题划分成若干个规模较小的同类问题

求解，当子问题划分得足够小时，用较简单的方法解决

合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

分治算法的经典运用

大数相乘问题、比赛日程安排

贪心

从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。

贪心算法的局限

不能保证最后的解是最优的；

不能求最大最小解问题；　　　

只能求满足某些约束条件的可行解范围。

贪心算法的基本过程

　1. 从问题的某一初始解出发　　　

while能向给定总目标前进一步　　

求出可行解的一个解元素　　　　

由所有解元素组合成问题的一个可行解

贪心算法的经典运用

装箱问题、找零方案

试探

　　在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。

　　（为求得问题的正确解，会先委婉地试探某一种可能情况。在进行试探过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探。反复进行，直到得到解或证明无解时才死心）

试探算法的基本步骤

　　　　1.针对所给问题，定义问题的解空间

　　　　2.确定易于搜索的解空间结构

　　　　3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

试探算法的经典运用

八皇后问题、29选7彩票组合

模拟

对真实事物或者过程的虚拟。

模拟算法的经典运用

猜数字游戏、掷骰子问题

云服务器 GPU云服务器最短路径算法思想最优合并问题的算法思想编程思想 python思想

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69477.html

基本算法思想：递归+分治+动态规划+贪心+回溯+分支限界

摘要：代码实现见下面评论对应代码动态规划基本思想和分治法基本思想有共同的地方，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因此把已经计算好的问题记录在表格中，后续如果需要查询一下，可以避免重复计算，这是动态规划的基本思想。作者：心叶时间：2018-05-01 19:28 本文对应github地址：https://github.com/yelloxing/... 以上实现...

EscapedDog 2019-08-26 11:52 评论0 收藏0
❤️思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题, 力扣4❤️

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...

XanaHopper 2021-09-10 10:51 评论0 收藏0
算法系列——JavaScript中广度优先搜索思想实现

摘要：散列表上面的地图向我们展示了如何用广度优先搜索的思想找到北京到广州的最短路线。在广度优先搜索中，我们需要用到队列的这种思想来实现查找。建立了下面这个模型武汉广州西藏上海上海武汉广州代码完整实现，利用递归和广度优先搜索的思想实现。什么是广度优先搜索？如果只是是背概念，幼儿园的小朋友都能背下来念给你听。假设看这篇文章的都和我一样是个前端工程师，我们要从广度优先搜索（BFS）中学到什么...

everfly 2019-08-21 17:36 评论0 收藏0
关于Web开发中“程序=数据结构+算法”的思考

摘要：在这里统一说开发，可能有失颇偏，毕竟我后端一直都是用实现的，没用过也没用过，但我想大体都是一样都，我就此阐述一下我所认为的程序数据结构算法。这套的想法主要目的是把复杂程序尽量做简化，并以数据和算法的思想去思考程序本身。在这里统一说Web开发，可能有失颇偏，毕竟我后端一直都是用PHP实现的，没用过.net也没用过java，但我想大体都是一样都，我就此阐述一下我所认为的程序=数据结构+算...

fish 2019-06-27 15:58 评论0 收藏0