回答·1
最热
最新
- 一、贪心算法 贪心算法，又称贪婪算法，是算法设计中的一种思想 其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的 举个零钱兑换的例子，如果你有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 ，我们要返回其所有可能的全排列，解决这个问题的思路是： 用递归模拟所有的情况 遇到包含重复元素的情况则回溯 收集到所有到达递归终点的情况，并返回、 三、总结 前面也初步了解到分而治之、动态规划，现在再了解到贪心算法、回溯算法 其中关于分而治之、动态规划、贪心策略三者的求解思路如下： 分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。 快速排序，归并排序，逆序对问题 MapReduce 分解：将原问题分解成一系列子问题； 解决：递归地求解各个子问题，若子问题足够小（base case），则直接求解； 合并：将子问题的结果合并成原问题 贪心 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法 最小生成树算法、单源最短路径算法 最重要的是找到贪心策略 一般会涉及到排序或对堆的使用 回溯 （暴力递归） 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试 N皇后问题等，试着写出尝试，一个原则+四个模型，有分支限界（剪枝）的技巧 动态规划 动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划，多阶段决策最优解问题。 先用暴力递归实现，然后改为动态规划，一般要建一个dp表（多维数组），根据依赖关系推演出结果，暴力递归中的依赖关系就是动态规划中的状态转移方程。 【四种算法思想的比较】 分治算法较为特殊，它不能抽象为多阶段决策最优解模型。并且分治算法要求分割成的子问题，不能有重复子问题 回溯算法(也叫暴力递归）是万金油，其实是，相当于穷举所有的情况，然后对比得到最优解，时间复杂度是指数级的，适用于小规模数据的问题 动态规划比暴力递归高效，可以由暴力递归改造成动态递归。但不是所有的暴力递归都可以改成动态规划，因为动态规划需要满足三个特征，最优子结构、无后效性（N皇后问题就有后效性）和重复子问题。 贪心算法能解决的问题需要满足最优子结构、无后效性和贪心选择性。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。