Iva*_*lin 16
我找到了答案,很高兴分享:
什么是最优/非最佳子结构？如果可以从其子问题的最优解构建有效地构造最优解,则认为问题具有最优子结构.此属性用于确定问题的动态编程和贪婪算法的有用性
什么是本地和全球最优？优化问题的局部最优是在相邻候选解集合中最优(最大或最小)的解决方案. 全局最优 - 是所有可能解决方案中的最佳解决方案,而不仅仅是特定价值邻域中的解决方案.
如何证明贪婪算法能够产生全局最优？通常,可以通过归纳证明全局最优.通常,贪婪算法用于解决具有最佳子结构的问题,如果可以通过归纳证明这在每个步骤是最佳的.否则,提供问题也表现出重叠的子问题,使用动态编程.
为了证明使用贪婪算法可以解决优化问题,我们需要证明问题具有以下内容:
最优子结构属性:最优全局解包含所有子问题的最优解.
贪婪的选择属性:通过贪婪地选择局部最优选择,可以获得全局最优解.
在某些情况下,可以使用拟阵来机械地证明特定问题可以通过贪婪方法来解决.
最后,一些贪婪算法的好例子.
| 归档时间： |
|
| 查看次数： |
9898 次 |
| 最近记录： |