1. 贪心算法
1.1. 介绍
贪心算法, 又叫贪婪算法, 是寻找最优解问题的常用办法 这种模式一般将求解过程分成若干个步骤, 对每一个步骤应用贪心原则, 选取当前状态下的最好/最优的选择(局部最有利的选择), 并以此希望最后堆叠出的结果也是最好的/最优的解.
1.2. 步骤
- 从某个初始解出发;
- 使用某个迭代的过程, 当可以向目标前进一步时, 就根据局部最优策略, 得到一部分的解, 缩小问题规模;
- 将所有解综合起来;
在背包问题中, 局部最优解的评定标准很重 要, 比如说可以按照以下三种最优策略来, 可以得到不同的解
- 物品最小重量
- 物品最高价值
- 物品的价格密度
1.3. 使用贪心算法的前提
- 原问题复杂度过高
- 求全局最优解的数学模型难以建立
- 求全局最优解的计算量过大
- 没有太大必要一定求出全局最优解
1.4. 如何把原问题分解为子问题
- 按串行任务分
时间串的任务, 按照子任务分解, 即每一步都是在上一步的基础上再选择当前的最优解.
- 按规模递减
规模较大的复杂问题, 可以借助递归的思想, 分解成一个规模小一点点的问题,循环解决, 当最后一步的求解完成后就得到了所谓的"全局最优解"
- 按并行任务分
这种任务不分先后, 可能是并行, 可以分别求解后, 再按照一定的规则(比如某种配比公式)将其组合后得到最终解
1.5. 如何知道贪心算法结果逼近了最优解
算法和数学不同, 并不追求绝得的最优值, 因为追求的过程需要考虑以下几个问题:
成本: 耗费多少资源, 花掉多少编程时间 速度: 计算量是否过大, 计算速度能否满足要求 价值: 得到了最优解与次优解是否真的有那么大差别, 还是说差别可以忽略