对贪心算法的理解 贪心算法中,通常会让证明贪心选择性,请问,证明贪心选择性的实质是什么?怎样说明一个问题具有贪心选择呢?
浏览量:2183
时间:2021-03-11 09:02:41
作者:admin
贪心算法中,通常会让证明贪心选择性,请问,证明贪心选择性的实质是什么?怎样说明一个问题具有贪心选择呢?
贪婪选择性质:问题的全局最优解可以通过一系列局部最优选择得到。
也就是说,您需要证明当前的问题可以通过选择最佳的元素来解决(例如01背包,它总是可以通过选择当前权重最小的项目得到最优解)
]//基本思想:研究问题的最优解,证明最优解是可以修改的,让它从贪婪选择开始,然后用数学归纳法证明了每一步都可以通过贪心选择得到最优解
1,假设首选元素不是贪心选择所需的元素,证明了用贪心选择所需的元素代替第一个元素仍然可以得到最优解数学归纳证明,每一步都可以通过贪心选择得到最优解
贪心算法(greedy algorithm,又称贪心算法)就是在求解问题时做出最佳选择。也就是说,在不考虑全局优化的情况下,他所做的只是某种意义上的局部最优解。贪心算法不能得到所有问题的全局最优解,但它能产生广泛问题的全局最优解或近似解。
什么是贪心算法?
在某种程度上,是的,但这个贪婪的步骤也是一个寻求最佳解决方案的过程。
版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。