标签:候选 思想 算法 当前 集合 最优 贪心
贪心算法
每一步都找到当前局部最优解,短视,但是有思考
贪心算法(Greedy Alogorithm)又叫登山算法,它的根本思想是逐步到达山顶,即
逐步获得最优解,是解决最优化问题时的一种简单但是适用范围有限的策略。
贪心算法没有固定的框架,算法设计的关键是贪婪策略的选择。
每一步都找到最优解,由于其短视性,
不一定能找到总体最优解,但通常能找到还不错的近似解
局部最优 推导 整体最优
举不出
反例时,就可以用贪心算法
使用前提
贪心策略要
无后向性,也就是说某状态之后的过程不会影响以前的状态,只于当前状态有关。
走的每一步都是既定事实,不会因为之后的选择而更改
常用组成部分
1.候选集合C
待扩展节点
为了构造问题的解决方案,有一个候选集合C作为问题的可能解,问题的最终解均取自于候选集合C。
2.当前解
随着贪心选择的进行,解集合不断扩展,直到构成一个满足问题的完整解。
3.解决判断函数solution
判断当前解是否达成问题的完整解
4.选择函数select
即
贪心策略,这是贪心算法的关键,它指出哪个候选对象有希望构成成问题的解。
例如如寻路中计算下一个格子到终点的距离,然后选择距离最小的格子来走
5.判断可行函数feasible
判断解中加入一个候选对象是否可行,即解集合扩展后是否满足约束条件。
贪心与A*(纯个人理解,可能有误)
A* = 贪心 + 启发估计
A*算法也用了贪心(逐步最优解)思想,但是加入了启发式信息H(x),通过已有信息得到一种对未来预期的估算策略
A*关键:启发函数
F = G + H
G = 从起点A走到当前格的距离
H = 从当前格走到终点 B 的
估计距离,例如当前格到终点的曼哈顿距离
G来源于已知点信息,H来源于对未知点信息的
估计,F为选择下一个将遍历节点的依据。
将计算出的F最小的格子,优先进行扩展(当前局部最优解)——贪心思想
A*到Dijkstra
当启发函数h(n)始终为0,则将只由
起点到当前格距离g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法(最短路径贪心算法)。
标签:候选,
思想,
算法,
当前,
集合,
最优,
贪心
From: https://www.cnblogs.com/jk-2048/p/18029990