Когда локально оптимальные решения равны глобальным оптимальным? Размышления о жадном алгоритме

Недавно я столкнулся с некоторыми проблемами жадного алгоритма. Я не понимаю, как оптимизировать локально. Как известно, жадные алгоритмы состоят из локально оптимальных вариантов. Но объединение локально оптимальных решений не обязательно означает глобально оптимальное, не так ли?

Возьмем в качестве примера внесение изменений: использование наименьшего количества монет для получения 15 центов, если у нас есть 10 ¢, 5 ¢ и 1 монеты, тогда вы можете получить это с одним 10 и одним 5. Но если мы добавим монету 12, жадный алгоритм не сработает, поскольку (1 × 12 ¢ + 3 × 1 ¢) использует больше монет, чем (1 × 10 + 1 × 5).

Рассмотрим некоторые классические жадные алгоритмы, например Хаффман, Дейкстра. На мой взгляд, эти алгоритмы успешны, поскольку у них нет вырожденных случаев, что означает, что комбинация локально оптимальных шагов всегда равна глобальному оптимальному. Правильно ли я понимаю?

Если я правильно понимаю, существует ли общий метод проверки оптимальности жадного алгоритма?

Я нашел обсуждение жадных алгоритмов в другом месте на сайте . Тем не менее, проблема не слишком подробно описана.