Жадные алгоритмы — это алгоритмы, которые заключаются в выработке локально оптимальных решений на всех этапах, допуская, что результирующее решение также будет оптимальным.
Общие сведения о жадных алгоритмах
Существует значительное количество методов решения разнообразных задач, таких как, динамическое программирование, перебор и так далее. Также достаточно известными и даже распространенными могут считаться жадные алгоритмы. Жадным алгоритмом (greedy algorithm) является такой алгоритм, который на каждом шаге осуществляет локально самый лучший выбор, предполагая, что результирующее решение окажется оптимальным.
Например, алгоритм Дейкстры, способный находить кратчайший путь в графе, может считаться жадным, потому что в нём на каждом шаге ищется вершина с наименьшим весом, в которую алгоритм ещё не заходил, после чего выполняется обновление значений других вершин. Причём возможно показать, что кратчайшие пути, которые были найдены в вершинах, будут оптимальными.
А, например, алгоритм Флойда, который также осуществляет поиск кратчайших путей в графе (но уже между всеми вершинами), не может считаться примером жадного алгоритма. В этом алгоритме Флойд продемонстрировал другую методику, а именно, метод динамического программирования.
Применение жадных алгоритмов
Применение жадных алгоритмов, по сути, является довольно стандартным. Рассмотрим его использование на конкретном примере. Предположим какому-либо программисту-фрилансеру выдано «n» заданий. У всех заданий задан крайний срок их выполнения, то есть свой дедлайн, а также их цена, то есть если программист не выполнит какое-либо задание, то он теряет определённую сумму денег. Предположим, что за один день программист способен выполнить одно задание. Исполнение задания следует начинать с нулевого момента. Целью является получение максимальной прибыли.
В данном случае классическим примером будет следующий вариант жадного алгоритма. Программисту более выгодно выполнять сначала самые дорогостоящие задания, а самые дешёвые можно и не исполнять. Такой подход ведёт к получению максимальной прибыли. Задания следует распределить следующим образом. Нужно выполнить перебор заданий в порядке убывания их стоимости и заполнить очерёдность исполнения следующим образом:
- Когда для исполнения заказа есть ещё хотя бы одно свободное место в расписании до окончания срока его исполнения, то следует поставить его на самое последнее из таких мест.
- Если предыдущее условие не выполняется, то есть, в срок программист его не может исполнить, значит это задание нужно поставить в конец списка свободных мест.
В результате была сформирована следующая программа:
Рисунок 1. Программа. Автор24 — интернет-биржа студенческих работ
Иногда может появиться желание применять жадный алгоритм везде, где только это возможно, однако существуют некоторые задачи, для которых это является неприемлемым. Примером может служить задача о рюкзаке, которая формулируется следующим образом. Вор проник на склад, в котором находятся три вещи, имеющие вес 10 кг, 20 кг и 30 кг и стоимость 60, 100 и 120 рублей соответственно. Вор максимально способен унести 50 кг. Вору необходимо получить максимальную прибыль.
Если использовать жадный алгоритм и выбрать самую дорогую вещь, а именно, это шесть рублей за килограмм для первой вещи, пять рублей за килограмм для второй и четыре рубля за килограмм для третьей, то вору следует брать первую вещь. Далее по весу останется место для второй вещи, однако оптимальным решением будут вторая и третья вещи.
На основании изложенного выше можно сделать вывод, что существует определённая область применимости жадных алгоритмов. Общих рецептов не существует, однако есть достаточно мощный инструмент, при помощи которого практически всегда можно определить, способен ли жадный алгоритм привести к оптимальному решению. Этим инструментом считается матроид.
Матроидом является пара (X, I), где X является конечным множеством, называемым носителем матроида, I является некоторым множеством подмножеств X, которое называется семейством независимых множеств.
Причём необходимо выполнение следующих условий:
- Множество I должно быть не пустым. Даже если исходное множество X было пустым, то есть X = Ø, то I будет состоять из одного компонента, а именно, множества, которое содержит пустое множество I = {{Ø}}.
- Каждое подмножество каждого компонента множества I тоже будет компонентом этого множества.
- Когда множества A и B принадлежат множеству I, а также является известным тот факт, что размер А меньше B, то должен существовать какой-либо компонент x из B, который не принадлежит А, такой что объединение x и A будет принадлежать множеству I. Данное свойство считается не совсем тривиальным, но чаще всего является самым важным из всех остальных.
Матроид считается взвешенным, когда на множестве X существует аддитивная весовая функция w. Вес множества должен быть определён как сумма весов его компонентов.
Снова рассмотрим пример с заданиями программисту. Здесь можно определить следующий матроид. Предположим носителем является множество заданий, а независимыми множествами будут считаться успешно исполненные задания. Весом любого задания будет считаться его стоимость. Необходимо проверить, является ли эта пара матроидом:
- Первое свойство, очевидно, исполняется. Пустое множество выполненных заданий входит в наше множество.
- Второе множество также исполняется.
- Третье свойство, хотя это и не является очевидным, но исполняется.
Все преимущества матроидов отображены в теореме Радо-Эдмондса, которая гласит, что если доказано, что объект является матроидом, то жадный алгоритм будет функционировать корректно и выдавать правильный итоговый результат.
