Iva*_*van 8 algorithm global greedy
最近我一直在研究一些贪婪的算法问题.我对局部最优而感到困惑.如您所知,贪婪算法由局部最优选择组成.但是,结合局部最优决策并不一定意味着全局最优,对吧？
以改变为例:使用最少数量的硬币制作15¢,如果我们有10¢,5¢和1¢硬币,那么你可以用一个10¢和一个5¢来实现.但是如果加上12美分硬币,贪婪算法就会失败,因为(1×12¢+ 3×1¢)使用的硬币多于(1×10¢+ 1×5¢).
考虑一些经典的贪婪算法,例如Huffman,Dijkstra.在我看来,这些算法是成功的,因为它们没有退化情况,这意味着局部最优步骤的组合总是等于全局最优.我理解对吗？
如果我的理解是正确的,有没有一种通用的方法来检查贪婪算法是否是最优的？
一般来说，只要问题是凸的，局部最优解始终是全局最优解。这包括线性规划；具有正定目标的二次规划；以及具有凸目标函数的非线性规划。（但是，NLP 问题往往具有非凸目标函数。）
如果启发式函数具有某些属性，启发式搜索将为您提供具有局部最优决策的全局最优值。有关详细信息，请查阅人工智能书籍。
但总的来说，如果问题不是凸的，我不知道有什么方法可以证明局部最优解的全局最优性。