Описание тега greedy

Из Википедии:

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

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

Особенности

В общем, жадные алгоритмы состоят из пяти компонентов:

1. Набор кандидатов, из которого создается решение
2. Функция выбора, которая выбирает лучшего кандидата для добавления в решение
3. Функция осуществимости, которая используется, чтобы определить, можно ли использовать кандидата для внесения вклада в решение.
4. Целевая функция, которая присваивает значение решению или частичному решению, и
5. Функция решения, которая укажет, когда мы нашли полное решение.

Жадные алгоритмы дают хорошие решения для одних математических проблем, но не для других.

Большинство задач, для которых они работают, будут иметь два свойства:

Жадный выбор собственности

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

Оптимальная подконструкция

"Проблема демонстрирует оптимальную подструктуру, если оптимальное решение проблемы содержит оптимальные решения подзадач".