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