当局部最优解决方案等于全局最优?关于贪婪算法的思考

最近我一直在研究一些贪婪的算法问题.我很困惑局部最优.如您所知,贪婪算法由局部最优选择组成.但是,结合局部最优决策并不一定意味着全局最优,对吧?

以改变为例:如果有的话,用最少数量的硬币制作15美分
10¢,5¢和1¢硬币然后你可以用一个10¢和一个5¢实现这个目标.但是如果我们加一个12¢硬币贪婪算法失败,因为(1×12¢3×1¢)使用的硬币多于(1×10¢1×5¢).

考虑一些经典的贪婪算法,例如赫夫曼,迪克斯特拉.在我看来,这些算法是成功的,因为它们没有退化情况,这意味着局部最优步骤的组合总是等于全局最优.我理解对吗?

如果我的理解是正确的,有没有一种通用的方法来检查贪婪算法是否是最优的?

我发现了一些discussion of greedy algorithms elsewhere on the site.
但是,问题并没有详细说明.

一般来说,只要问题是凸的,局部最优解就总是最优的.这包括线性编程;具有正定目标的二次规划;和具有凸目标函数的非线性规划. (但是,NLP问题往往具有非凸目标函数.)

如果启发式函数具有某些属性,则启发式搜索将为您提供具有局部最优决策的全局最优.有关详细信息,请参阅AI书.

但是,一般来说,如果问题不是凸的,我不知道有什么方法可以证明局部最优解的全局最优性.

相关文章
相关标签/搜索