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

Question

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

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

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

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

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

Answer 1

Вообще говоря, локально оптимальное решение всегда является глобальным оптимумом, когда проблема выпуклая. Это включает в себя линейное программирование; квадратичное программирование с положительно определенной целью; и нелинейное программирование с выпуклой целевой функцией. (Однако проблемы НЛП, как правило, имеют невыпуклую целевую функцию.)

Эвристический поиск даст вам глобальный оптимум с локально оптимальными решениями, если эвристическая функция обладает определенными свойствами. Обратитесь к книге AI за подробностями об этом.

В общем, хотя, если проблема не выпуклая, я не знаю ни одного метода доказательства глобальной оптимальности локально оптимального решения.

Answer 2

Существуют некоторые теоремы, которые выражают задачи, для которых жадные алгоритмы оптимальны с точки зрения матроидов (также: жадные монеты). Подробности см. В этом разделе Википедии: http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms

Answer 3

Жадному алгоритму почти никогда не удается найти оптимальное решение. В тех случаях, когда это происходит, это сильно зависит от самой проблемы. Как объяснил Тед Хопп, с помощью выпуклых кривых можно найти глобальный оптимум, предполагая, что вы, конечно, должны найти максимум целевой функции (и наоборот, вогнутые кривые также работают, если вы хотите минимизировать). В противном случае вы почти наверняка застрянете в местной оптиме. Это предполагает, что вы уже знаете целевую функцию.

Еще один фактор, о котором я могу думать, это функция соседства. Некоторые окрестности, если они достаточно большие, будут охватывать как глобальные, так и локальные максимумы, так что вы сможете избежать локальных максимумов. Однако вы не можете сделать район слишком большим, иначе поиск будет медленным.

Другими словами, найти ли вы глобальный оптимум или нет с помощью жадных алгоритмов, зависит от проблемы, хотя в большинстве случаев вы не найдете глобально оптимальный.

Answer 4

Вам нужно создать пример-свидетель, в котором ваша предпосылка о том, что алгоритм является глобальным, не выполняется.Разработайте его в соответствии с алгоритмом и задачей.

Ваш пример замены монет был недействительным.Монеты разработаны специально для того, чтобы иметь все возможные комбинации, но не для того, чтобы создавать путаницу.Ваше добавление 12с не гарантируется и является дополнительным.

С вашим добавлением проблема не в смене монет, а в другом (хотя предметом являются монеты, вы можете изменить пример на то, что хотите).Для этого вы сами привели пример-свидетель, показывающий, что жадный алгоритм для этой проблемы застрянет в локальном максимуме.