Задача о рюкзаке

Пример задачи о ранце: необходимо уложить коробки в ранец вместимости 15 кг, так чтобы стоимость уложенных коробок была максимальной.

Задача о ранце (рюкзаке) (англ. Knapsack problem) — одна из NP-полных задач комбинаторной оптимизации. Название своё получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Задачи о загрузке (о рюкзаке) и её модификации часто возникают в экономике, прикладной математике, криптографии, генетике и логистике для нахождения оптимальной загрузки транспорта (самолёта, поезда, трюма корабля) или склада. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

Классическая постановка задачи

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.

Математически это можно сформулировать так: имеется $n$ грузов. Для каждого i-го груза определён вес $p_{i}>0$ и ценность $c_{i}>0$$,i=1,2,...,n$. Нужно упаковать в рюкзак ограниченной грузоподъёмности $P$ те грузы $x_{i}$, при которых суммарная ценность упакованного была бы максимальной.

Варианты задачи о ранце

Основная статья: Список задач о ранце

Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.

1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)
2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)
3. Не ограниченный рюкзак (целочисленный рюкзак)(англ. Unbounded Knapsack Problem (integer knapsack))
4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)
5. Мультипликативный рюкзак (англ. Multiple Knapsack Problem)
6. Многомерный рюкзак (англ. Multy-dimensional knapsack problem)

Изучение в дисциплинах

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

Изучение в математике

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о ранце. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса, датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem», особенно в 70-90-е годы 20-го века, как теоретиками, так и практиками. Во многом данный интерес вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список К. Мэннига NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»).

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

• Размещение грузов в помещении минимального объёма.
• Раскройка ткани — для заданного куска материала получить максимальное число выкроек определенной формы.
• Расчет оптимальных капиталовложений.

Оправдывая свое название, с задачей о ранце сталкивается любой человек, собирающий рюкзак.

Изучение в криптографии

Основная статья: Задача о ранце в криптографии

Проблема рюкзака лежит в основе первого алгоритма асимметричного шифрования (или иначе — шифрования с открытым ключом). Идея криптографии с открытыми ключами была выдвинута Уитфилдом Диффи, Мартином Хеллманом и независимо — Ральфом Мерклом (англ. Ralph Merkle). Впервые она была представлена Диффи и Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference). Новизна по отношению к симметричным криптосистемам заключалась в использовании парных ключей — секретного (англ. private key, secret key, SK) и открытого (англ. public key, PK), создаваемых пользователем. Из названия понятно, что секретный ключ пользователь должен скрывать, а открытый может быть общедоступным. Открытый ключ нужен для шифрования, а секретный для расшифровки. Часто из секретного ключа получают открытый ключ.

Криптосистема Меркла-Хеллмана — первый основанный на задаче о ранце алгоритм для обобщённого шифрования с открытым ключом. Разработан Ральфом Мерклом и Мартином Хеллманом в 1978 году. Был опубликован одностадийный (англ. singly-iterated) и мультистадийный вариаты (англ. multiply-iterated). Алгоритм мог быть использован только для шифрования, но Ади Шамир адаптировал его для использования в цифровых подписях.

В дальнейшем было предложено как множество модификаций криптосистемы Меркла-Хеллмана, так и совершенно новых криптосистем на основе задачи о ранце. Среди них:

1. Рюкзак Грэм-Шамира
2. Рюкзак Гудмана-Макколи
3. Рюкзак Накаше-Штерна
4. Рюкзак Шора-Ривеста

Шифрование с помощью задачи о рюкзаке

Сообщение шифруется как решение набора задач о ранце.

Def.Рюкзачным вектором $A=(a_{1},...,a_{n})$ назовём упорядоченный набор из n предметов.

Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины $n$ (например, $(11100)$ соответствует 5-ти предметам в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие.

Пример шифротекста, полученного по данному алгоритму.

Пусть задан рюкзачный вектор Α = (3 4 6 7 10 11) с длинной n = 6.

открытый текст	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
вещи в рюкзаке	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11	3 4 6 7 10 11
шифротекст	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	11

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

Изучение в информатике

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

Точные алгоритмы

К точным алгоритмам относятся следующие:

Полный перебор

Пусть в рюкзак загружаются предметы $N$ разных типов. Рассмотрим задачу, когда количество предметов каждого типа не ограничено. Нужно определить максимальную стоимость груза, вес которого равен $P$. Для получения решения алгоритмом полного перебора осуществляется перебор всех вариантов загрузки рюкзака.

Дерево полного перебора

Временная сложность алгоритма $O(N!)$, т.е он работоспособен для небольших значений $N$. С ростом $N$ задача становится неразрешимой данным методом.

На рисунке показано четырёхуровневое дерево перебора. Корень дерева соответствует нулевому весу (рюкзак пуст), в кружках показан вес предмета. Первый предмет возможно выбрать четырьмя способами, второй тремя и т. д.

Метод ветвей и границ

Дерево, упрощенное методом ветвей и границ

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

Пусть есть оптимальное решение $R$. Попытаемся его улучшить, рассмотрев решение на другой ветви. Если на рассматриваемой в данной момент ветви решение становится хуже (с какого-то шага), чем $R$, то прекращаем его исследование и выбираем другую ветвь дерева.

Пусть для предыдущего четырёхуровневого дерева есть ограничение $P=5$. Тогда, применяя метод ветвей и границ, можно сократить количество вариантов для перебора с 24-х до 8-ми. Однако метод ветвей и границ работает не для всех наборов данных. Можно привести примеры, в которых время выполнения будет таким же, как и для простого перебора.

Применение динамического программирования

При использовании метода динамического программирования строится сеть. По оси $X$ откладываем количество предметов, по оси $Y$ — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось $Y$ равны весу предмета. На втором шаге опять строим 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета.

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

Пример: Пусть вместимость рюкзака $P=14$.

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

i	Ценность	Вес
1	3	5
2	5	10
3	4	6
4	2	5

На рисунке, в квадратных скобках [] стоит суммарная ценность на каждом шаге алгоритма. Видно, что для конкретного примера она равна [7].

Приближённые алгоритмы

К приближенным алгоритмам относятся следующие:

Жадный алгоритм

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

Для сортировки предметов потребуется $O(Nlog(N))$. Далее организуется проход по всем $N$ элементам цикла.

Точное решение можно получить не всегда.

Пример. Пусть вместимость рюкзака $P=80$. Предметы уже отсортированы. Применяем к ним жадный алгоритм.

i	вес	цена	цена/вес
1	20	60	3
2	30	90	3
3	50	100	2

Кладём в рюкзак первый, а за ним второй предметы. Третий предмет в рюкзак не влезет. Суммарная ценность поместившегося равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Видно, что жадный алгоритм не обеспечивает оптимального решения, поэтому относится к приближенным.

Метаалгоритмы

Генетический алгоритм

Генетические алгоритмы были предложены Джоном Генри Холландом в 1970 году и относятся к так называемым метаалгоритмам. Идея — составление алгоритмов поиска на основе биологической модели механизмов естественного отбора. Базовыми понятиями являются: популяция, отбор, мутация, скрещивание.

Популяция. Составляется набор бинарных строк (хромосом), возможных решений. На основе первой («старой») популяции строится вторая («новая») популяция решений, которая служит «старой» для третьей популяции и т.д

Отбор. Задается функция выбора, согласно которой, лучшие представители «старой» популяции выбираются для воспроизводства «новой». Следовательно, алгоритм выбирает наилучшее решение.

Скрещивание хромосом. «Родители» обмениваются последними пятью битами и образуют новые хромосомы — «потомки».

Скрещивание. Для пары строк («родителей») с определенной длиной $r$ выбирается произвольное число $1\leq s\leq r$. «Родители» обмениваются между собой битами с $s+1$-го по $r$-й и получаются две новые строки («потомки»).

Мутация. Изменение, происходящее с определенной вероятностью.

Содержимое рюкзака представляется в виде хромосом или бинарных строк, i-й бит которых равен единице в случае наличия предмета в рюкзаке, нулю — в случае его отсутствия. Задается целевая функция $S$ — вместимость рюкзака.

Отбор осуществляется следующим образом.

Выбирается произвольная хромосома. Пусть $L_{max}=max(S,S''-S)$ — максимальное расхождение между целевой функцией и хромосомой. $S''$ суммарный вес всех предметов, входящих в рюкзачный вектор. $S'$ — вес рюкзака при выбранной хромосоме.

Если $S'\leq S$, то хромосома оценивается числом $q=1-{\sqrt {|S'-S|/S}}$.

Если $S'>S$, то хромосома оценивается числом $q=1-{\sqrt {|S'-S|/L_{max}}}$.

Блок схема генетического алгоритма

По этому числу осуществляется отбор хромосом.

На рисунке показаны все этапы алгоритма:

1. Создание случайной популяции двоичных хромосом.
2. Оценка каждой из них числом $q$.
3. Отбор на основе полученных чисел.
4. Скрещивание полученных на третьем этапе хромосом.
5. Мутация.
6. Переход на второй шаг.

Алгоритм прерывается после заданного числа итераций.

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

Литература

на русском языке

1. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 160-163. — ISBN 0-201-74395-7.
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
4. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.
5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
6. С. Окулов. Программирование в алгоритмах. — 2007. — С. 383.
7. Б. Шнайер. Прикладная криптография. — 2-ое.
8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — Springer-Verlag, 1990. — С. 102-150.
9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254.

на английском языке

1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
2. Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack problems. — 1995.
3. David Pisinger. Knapsack problems. — 1995.
4. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür. Packing the Meeting Summarization Knapsack. — Proc. Interspeech, Brisbane, Australia, 2008.

Ссылки

1. Welcome to the Knapsack (англ.)
2. Knapsack Problem By Eric Grimsom John Guttag — MIT (англ.)
3. Knapsack Problem solutions in many languages at Rosetta Code (англ.)
4. Das Rucksack-Problem (Knapsack Problem) (нем.)