Жадные алгоритмы — это класс алгоритмов, которые получают оптимальное решение, делая локально оптимальный выбор. Эти алгоритмы часто являются одними из самых простых, потому что они интуитивно понятны и просты. Их легко понять и доказать правильность. Однако, к сожалению, большинство задач невозможно решить с помощью жадного алгоритма.
Так как же выглядит жадный алгоритм? Давайте рассмотрим следующую проблему: у вас есть набор классов, все с временем начала и окончания. Цель состоит в том, чтобы создать действительное расписание занятий с максимально возможным количеством занятий. Это означает, что никакие два класса в расписании не пересекаются.
Сначала это может показаться сложной задачей. Использование решения грубой силы потребовало бы перебора всех возможных комбинаций классов, что заняло бы слишком много времени для больших входных данных. Но с помощью жадного алгоритма мы можем довольно легко найти правильное решение.
Во-первых, мы сортируем классы по времени их окончания в порядке возрастания. Таким образом, урок, который заканчивается раньше всех, считается первым. Теперь у нас есть расписание занятий, которое пока пусто. Таким образом, локально оптимальное решение состоит в том, чтобы взять класс с самым ранним временем окончания и включить его в наше расписание. Это локально оптимально, так как мы хотим уместить в расписании как можно больше занятий. Поэтому, естественно, мы хотели бы выбрать самое раннее время окончания, чтобы у нас оставалось больше времени, чтобы соответствовать другим классам. Выбрав класс с самым ранним временем окончания, мы исключаем все перекрывающиеся классы. То есть любые занятия, время начала которых предшествует выбранному времени окончания. Затем мы продолжаем этот процесс до тех пор, пока в нашем списке не останется классов и мы не получим оптимальное решение.
Интуитивно это жадное решение имеет смысл. Если наше жадное решение было неверным, то мы должны убрать один из выбранных классов и заменить его как минимум двумя другими. Но это произойдет только в том случае, если один из двух новых классов закончится раньше, чем жадный выбор. Но это противоречие, так как тогда жадный алгоритм изначально выбрал бы неправильно.
Другие примеры проблем с жадными алгоритмами включают задачу о дробном рюкзаке, интервальную раскраску и кодирование Хаффмана. Алгоритмы, подобные алгоритму Дейкстры для поиска кратчайших путей или алгоритму Крускала и Прима для минимальных остовных деревьев, также являются жадными алгоритмами.
Чтобы придумать жадный алгоритм, вы просто принимаете наилучшее решение на каждом этапе с доступной информацией. Но это может быть ловушкой, поэтому важно всегда доказывать, что ваш алгоритм верен для данной задачи.
Жадные алгоритмы являются важным классом алгоритмов для изучения. Хотя они могут быть бесполезны для большинства задач, обычно их легче всего построить и доказать. Большинство доказательств для жадных алгоритмов индукции, которые предполагают, что алгоритм верен на предыдущем шаге, и доказывают, что он должен быть верен на следующем шаге.
