Разработка контента для обучающего курса по теме «Задача о ранце»

Аннотация: Проанализирована NP-полная задача комбинаторной оптимизации - «Задача о ранце», которая представляет собой целое семейство задач. Рассмотрены разновидности этой задачи, к каждому из которых приведены примеры. Описаны методы, позволяющие получить точное решение, и алгоритмы их решения. Предлагается структура и состав активного контента обучающей системы Moodle по данной теме.

Классическая задача о ранце формулируется следующим образом. Допустим, имеется n предметов, имеющих два свойства: вес w_i > 0 и ценность p_i > 0, i = 1…n, и ранец вместимостью W. Необходимо упаковать ранец так, чтобы получить максимальную ценность, при соблюдении ограничения по вместимости. Формально задача имеет вид:

, i = 1…n

здесь:

Несмотря на простоту формулировки, задача о ранце представляет собой целое семейство задач, в зависимости от выбора «предметов» и их свойств. Например, в качестве предметов могут выступать заказы или время работы, а вес представлять собой релевантность или иную количественную оценку товара. Рассмотрим основные варианты:

1. Ограниченный рюкзак. Вводится дополнительное ограничение, и каждый предмет может быть взят лишь некое b_i число раз.
2. Неограниченный рюкзак – общий случай, в котором предполагается, что предметов каждого типа неограниченное количество.
3. Непрерывный рюкзак. Все предметы могут быть поделены, сохраняя при этом свои ценностные характеристики. Например, погрузка песка из разных карьеров.
4. Задача о суммах подмножества. Задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы, при условии, что стоимость предмета совпадает с его ценностью.
5. Задача о размене. Для каждого предмета определен лишь один параметр – его ценность. Необходимо найти минимальное количество монет, для размена суммы.
6. Задача об упаковке. Имеются M рюкзаков вместимости W и столько же предметов с весами w_i. Необходимо разместить все имеющиеся предметы, задействовав минимум рюкзаков.
7. Мультипликативный рюкзак. Есть n предметов и M рюкзаков (M ≤ n). У каждого рюкзака своя вместимость W_i. Задача: выбрать M не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

Для задачи о ранце разработано множество методов решения [1, 2]. Они отличаются по своему быстродействию, затрачиваемым ресурсам памяти, а в ряде случаев и по точности решения. Рассмотрим самые распространенные из них.

• Полный перебор. Такой подход применим почти к любой комбинаторной задаче, и эта не стала исключением. Главный принцип этого метода заключается в простом перебирании всевозможных вариантов и выбора наилучшего из них. Несомненным плюсом здесь является простота реализации данного алгоритма, однако он имеет при этом экспоненциальную временную сложность O(2ⁿ), то есть его применимость целесообразна лишь для небольших значений n. Потому на практике используются различные модификации полного перебора.
• Метод ветвей и границ. По своей сути является улучшенным методом полного перебора. На каждом шаге алгоритма мы разделяем выбранное на предыдущем шаге множество на два подмножества. Таким образом, строится дерево перебора. Отличительной особенностью является то, что по мере решения отбрасываются ветви за исключением узлов с максимальной оценкой верхней границы. Так как алгоритм не обрабатывает все возможные варианты, то временная сложность уже чуть лучше по сравнению с предыдущим методом, однако в худшем случае также равна экспоненциальной. Обычно используется для решения ограниченного, неограниченного и мультипликативного рюкзаков, либо же для задачи об упаковке.
• Метод динамического программирования. В этом методе основная задача разбивается на более простые подзадачи. При этом задача должна иметь оптимальную подструктуру, то есть набор перекрывающих подзадач, сложность которых меньше изначальной. Также для значительного сокращения объема вычислений зачастую применяется принцип мемоизации (сохранение результатов выполнения функций во избежание повторения вычислений). Трудоемкость такого алгоритма O(W × n). Чаще всего применяется при решении задач об ограниченном и неограниченном рюкзаках или задачи о размене.

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

• Жадный алгоритм. Один из самых простых в реализации методов. Согласно ему все предметы вначале сортируются по своей удельной ценности, а затем в ранец помещаются те предметы, у которых этот параметр максимальный. Чаще всего применяется для непрерывного рюкзака, где всегда даёт оптимальное решение, а также для размена монет, в котором при определенных условиях способен давать оптимальный ответ.
• Генетический алгоритм. Для рассматриваемой задачи он интерпретируется следующим образом. Каждая особь (генотип) представляет собой подмножество предметов, которые мы хотим упаковать в ранец (их общий вес может превысить допустимую грузоподъемность). Для удобства информация хранится в виде бинарных строк, в которых каждый бит определяет, помещается ли этот предмет в ранец. В этом алгоритме вводится понятие функции приспособленности, которая определяет близость решения к оптимальному. Например, таковой может служить суммарная ценность предметов, при условии, что суммарный вес не превосходит грузоподъемность. После серии смен поколений, в которых скрещиваются наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения. Часто применяется для задачи о сумме подмножеств.

Как видно из описанных методов, рассматриваемая задача имеет высокую трудоемкость решения. Своё применение задача о ранце нашла в математике, информатике [3] и в криптографии. На основе задачи о ранце был придуман первый ассиметричный алгоритм шифрования. Помимо этого задача широко распространена в различных сферах деятельности человека – промышленности, экономике, менеджменте. Например: размещение грузов в помещении минимального объёма, расчет оптимальных капиталовложений, погрузка грузовых контейнеров на грузовой лайнер и другие.

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

1. Постановка классической задачи о ранце;
2. Наиболее распространенные модификации задачи;
3. Методы решения задачи;
4. Лабораторные работы по изучению классического и эвристического метода решения.

Обучающий курс реализован в среде системы дистанционного обучения Moodle. Для обеспечения легкой переносимости сама система Moodle развернута на виртуальной машине [4].

Список литературы

1. Кофман А., Анри-Лабордер А. Методы и модели исследования операции. Целочисленное программирование. М. : Мир, 1977. 432 с.
2. Алгоритмы: построение и анализ / Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. М. : Вильямс, 2006. 1296 с.
3. Урахчинский И. Н. К задаче выбора состава дисков виртуальных машин // Образовательные технологии и общество (Educational Technology & Society). 2012. V. 15. № 4 [Электронный ресурс]. URL: http://ifets.ieee.org/russian/periodical/journal.html (дата обращения: 15.07.2017).
4. Сотников С. В., Урахчинский И. Н. Применение технологий виртуализации для построения операционной и сетевой среды обучающих систем // Международный электронный журнал «Образовательные технологии и общество (Educational Technology & Society)». 2012. V. 15. № 4. [Электронный ресурс]. URL: http://ifets.ieee.org/russian/periodical/journal.html (дата обращения: 26.07.2017).

 

Материал поступил в редакцию 07.08.2017
© Якупов Р. Р., 2017