XVI Международная студенческая научная конференция Студенческий научный форум - 2024

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

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

Вторым неотъемлемым характерным признаком жадного алгоритма является оптимальность для подзадач. Оптимальность для подзадач подразумевает под собой оптимальное решение как для всей задачи, так и для её отдельных элементов (подзадач) в частности. Иначе говоря, решение задачи строится на оптимальных решениях подзадач.

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

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

Приведём решение этой задачи. Поскольку любое число можно представить через сумму , где – это количество суммирований числа , – произвольное число, – остаток от деления некоторого числа на . Логично предположить, что разменять сумму так, чтобы задействовалось наименьшее количество монет, выгоднее всего через ( , , …, – максимально возможное количество монет, которые можно взять так, чтобы сумма, которую заполняют эти монеты (для : , для : , для : и т.д.) была больше либо равна сумме этих монет) монет с максимальным номиналом, монет с наибольшим номиналом после номиналом (при условии, что монет достоинством не хватило, чтобы полностью разменять сумму ) и т.д. до тех пор, пока не будет получена сумма .

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

Таким образом, на каждом шаге всегда выбирается монета с наибольшим номиналом.

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

Однако утверждать, что выполняется принцип жадного выбора нельзя, т.к. для этого необходимо знать сами номиналы. Потому что если номиналы будут равны, к примеру: ( ), ( ), ( ), ( ), а сумма , следуя жадному алгоритму для получения суммы , необходимо последовательно брать все монеты номинала , далее, все монеты номинала , а затем, все монеты номинала , не беря в расчёт номинал (т.к. после взятия всех монет номинала и полученная сумма будет равна 23, а прибавив 5 уже получается 28 > 27). В результате для получения суммы было использовано 7 монет (1 по 9, 2 по 7 и 4 по 1), что является не оптимальным решением. Ведь взяв 1 по 9, 1 по 7, 2 по 5 и 1 по 1, в сумме получается вся та же , но с использованием уже 5 монет.

Иначе обстоит дело с номиналами: ( ), ( ), ( ), ( ) – работая с данными номиналами работает принцип жадного выбора. Докажем это, оставив сумму неизменной. Следуя алгоритму, необходимо взять столько монет номинала , сколько может уместиться в сумме , так что берутся 2 монеты номинала . Затем, берутся столько монет номинала , сколько может уместиться в сумме . Аналогичные действия проводятся над номиналом . В итоге получаем, что сумма может быть получена как . Для чего потребовалось 4 монеты. Поскольку для каждого номинала в этой задаче выполняется неравенство: , что значит, что любая сумма представленная в виде: как минимум будет использовать не меньшее количество монет при любом ином решении. Отсюда следует, что с данными номиналами принцип жадного выбора применим к этой задаче. Что и требовалось доказать.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Учебники, монографии, брошюры

1. Рафгарден Тим Совершенный алгоритм. Жадные алгоритмы и динамическое программирование. – СПб.: Питер, 2020. – 256 с.: ил. – (Серия «Библиотека программиста»).

2. Ришал Харбанс Грокаем алгоритмы искусственного интеллекта. – СПб: Питер, 2023 – 368 с.: ил. – (Серия «Библиотека программиста»)

3. Рафгарден Тим Совершенный алгоритм. Алгоритмы для NP-трудных задач. — СПб.: Питер, 2021. — 304 с.: ил. — (Серия «Библиотека программиста»).

Электронные ресурсы

4. Теорема Радо-Эдмондса (жадный алгоритм): сайт. – URL: https://neerc.ifmo.ru/wiki/index.php?title=Теорема_Радо-Эдмондса_(жадный_алгоритм) (дата обращения 10.05.2023)

5. Жадные алгоритмы для задачи о ранце: поведение в среднем Г. Н. Дюбин, А. А. Корбут: сайт. – URL: https://www.mathnet.ru/links/263db00c1c6ac94b9c670a56d83d874f/sjim68.pdf (дата обращения 15.05.2023)