申请试用
HOT
登录
注册
 
贪婪算法

贪婪算法

乐乐
/
发布于
/
2011
人观看
贪婪算法是组合算法的常用范例。直觉上的组合问题是那些可行解决方案是有限集的子集(通常来自输入项)的问题。因此,原则上,这些问题总是可以通过检查每个可行解决方案在指数时间(例如,O(2n))中最佳地解决。贪婪算法的目标是通过仅搜索一小部分来找到最优。我们将探讨贪婪在解决计算或优化问题时的效果。准确定义贪婪算法的难度,如果不是不可能的话。以非正式的方式,算法遵循贪婪设计原则,如果它做出一系列选择,并且每个选择都是局部优化的; 换句话说,当孤立地观察时,该步骤被最佳地执行。棘手的问题是何时以及为何这样的近视策略(单独查看每个步骤,忽略全局考虑因素)仍然可以导致全局最优解决方案。事实上,当一个贪婪的策略导致一个最优的解决方案时,它会说问题本身的结构(性质)有些有趣!在其他情况下,即使贪婪没有给出最佳,在许多情况下,它导致可证明的良好(不太远离最佳)解决方案。
3 点赞
0 收藏
0下载
相关文档
确认
3秒后跳转登录页面
去登陆