Задача о ранце | это... Что такое Задача о ранце? (original) (raw)
Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной.
Задача о ранце (рюкзаке) (англ. Knapsack problem) — одна из задач комбинаторной оптимизации. Название своё получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Очевидно, что писать программу для упаковки рюкзака в путешествие никто не станет. Существует более широкое применение. Задачи о загрузке (о рюкзаке) и её модификации часто возникают в экономике, прикладной математике, криптографии, логистике для нахождения оптимальной загрузки транспорта (самолёта, поезда, трюма корабля) или склада[1][2], генетике. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Содержание
- 1 Классическая постановка задачи
- 2 Изучение в дисциплинах
- 2.1 Изучение в математике
- 2.2 Изучение в криптографии
* 2.2.1 Шифрование с помощью задачи о рюкзаке - 2.3 Изучение в информатике
* 2.3.1 Точные алгоритмы
* 2.3.1.1 Полный перебор
* 2.3.1.2 Метод ветвей и границ
* 2.3.1.3 Применение динамического программирования
* 2.3.2 Приближённые алгоритмы
* 2.3.2.1 Жадный алгоритм
* 2.3.3 Метаалгоритмы
* 2.3.3.1 Генетический алгоритм
- 3 Примечания
- 4 Литература
- 5 Ссылки
Классическая постановка задачи
Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.
Математически это можно сформулировать так: имеется грузов. Для каждого i-го груза определён вес и ценность . Нужно упаковать в рюкзак ограниченной грузоподъёмности те грузы , при которых суммарная ценность упакованного была бы максимальной[3].
Варианты задачи о ранце
Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.
- Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[1]
- Ограниченный рюкзак (англ. Bounded Knapsack Problem)[4]
- Не ограниченный рюкзак (целочисленный рюкзак)(англ. Unbounded Knapsack Problem (integer knapsack))[4]
- Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[5]
- Мультипликативный рюкзак (англ. Multiple Knapsack Problem)[6]
- Многомерный рюкзак (англ. Multy-dimensional knapsack problem)[5]
Изучение в дисциплинах
Наглядная постановка задачи о ранце привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В вычислительной лингвистике в одной из работ[7] предложена формулировка задачи автоматического реферирования текстов (англ.)русск., вырожденный (более простой) случай которой соответствует постановке задачи о ранце.
Изучение в математике
Доподлинно неизвестно, кто первым привел математическую формулировку задачи о ранце. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса (англ.)русск.[8][9], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцига в 1957 году книги «англ. _Discrete Variable Extremum Problem_»[10], особенно в 70-90-е годы 20-го века, как теоретиками, так и практиками[1]. Во многом данный интерес вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список К. Мэннига NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[11].
С практической точки зрения задача о рюкзаке может служить моделью для большого числа промышленных ситуаций[1][2]:
- Размещение грузов в помещении минимального объёма.
- Раскройка ткани — для заданного куска материала получить максимальное число выкроек определенной формы.
- Расчет оптимальных капиталовложений.
Оправдывая свое название, с задачей о ранце сталкивается любой человек, собирающий рюкзак.
Изучение в криптографии
Проблема рюкзака лежит в основе первого алгоритма асимметричного шифрования (или иначе — шифрования с открытым ключом). Идея криптографии с открытыми ключами была выдвинута Уитфилдом Диффи, Мартином Хеллманом и независимо — Ральфом Мерклом (англ. Ralph Merkle). Впервые она была представлена Диффи и Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference). Новизна по отношению к симметричным криптосистемам заключалась в использовании парных ключей — секретного (англ. private key, secret key, SK) и открытого (англ. public key, PK), создаваемых пользователем. Из названия понятно, что секретный ключ пользователь должен скрывать, а открытый может быть общедоступным. Открытый ключ нужен для шифрования, а секретный для расшифровки. Часто из секретного ключа получают открытый ключ[12][13].
Криптосистема Меркла-Хеллмана — первый основанный на задаче о ранце алгоритм для обобщённого шифрования с открытым ключом. Разработан Ральфом Мерклом и Мартином Хеллманом в 1978 году. Был опубликован одностадийный (англ. singly-iterated) и мультистадийный вариаты (англ. multiply-iterated). Алгоритм мог быть использован только для шифрования, но Ади Шамир адаптировал его для использования в цифровых подписях[14].
В дальнейшем было предложено как множество модификаций криптосистемы Меркла-Хеллмана, так и совершенно новых криптосистем на основе задачи о ранце. Среди них[15]:
- Рюкзак Грэм-Шамира
- Рюкзак Гудмана-Макколи
- Рюкзак Накаше-Штерна
- Рюкзак Шора-Ривеста
Шифрование с помощью задачи о рюкзаке
Сообщение шифруется как решение набора задач о ранце[14].
Def.Рюкзачным вектором назовём упорядоченный набор из n предметов[16].
Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины (например, соответствует 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-полных, для неё нет полиномиального алгоритма, решающего её за разумное время. Поэтому при решении задачи о ранце всегда нужно выбирать между точными алгоритмами, которые не применимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не обеспечивают оптимального решения задачи. Естественно, создание быстрого и достаточно точного алгоритма представляет большой интерес.
Точные алгоритмы
К точным алгоритмам относятся следующие:
Полный перебор
Пусть в рюкзак загружаются предметы разных типов. Рассмотрим задачу, когда количество предметов каждого типа не ограничено. Нужно определить максимальную стоимость груза, вес которого равен . Для получения решения алгоритмом полного перебора осуществляется перебор всех вариантов загрузки рюкзака.
Дерево полного перебора
Временная сложность алгоритма , т.е он работоспособен для небольших значений [17]. С ростом задача становится не разрешимой данным методом.
На рисунке показано четырёхуровневое дерево перебора. Корень дерева соответствует нулевому весу (рюкзак пуст), в кружках показан вес предмета. Первый предмет возможно выбрать четырьмя способами, второй тремя и т. д.
Метод ветвей и границ
Дерево, упрощенное методом ветвей и границ
Метод ветвей и границ является вариацией метода полного перебора с той разницей, что мы сразу исключаем заведомо неоптимальные решения.
Пусть есть оптимальное решение . Попытаемся его улучшить, рассмотрев решение на другой ветви. Если на рассматриваемой в данной момент ветви решение становится хуже (с какого-то шага), чем , то прекращаем его исследование и выбираем другую ветвь дерева[18].
Пусть для предыдущего четырёхуровневого дерева есть ограничение . Тогда, применяя метод ветвей и границ, можно сократить количество вариантов для перебора с 24-х до 8-ми. Однако метод ветвей и границ работает не для всех наборов данных. Можно привести примеры[источник не указан 33 дня], в которых время выполнения будет таким же, как и для простого перебора.
Применение динамического программирования
При использовании метода динамического программирования строится сеть[19]. По оси откладываем количество предметов, по оси — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось равны весу предмета. На втором шаге опять строим 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета.
Таким образом, любому решению задачи соответствует некоторый путь в сети. Наша задача свелась к нахождению пути максимальной длины.
Пример: Пусть вместимость рюкзака .
Сеть, иллюстрирующая наполнение рюкзака. В квадратных скобках указаны суммарная ценность на данном шаге алгоритма, оптимальное решение помечено кругом
i | Ценность | Вес |
---|---|---|
1 | 3 | 5 |
2 | 5 | 10 |
3 | 4 | 6 |
4 | 2 | 5 |
На рисунке, в квадратных скобках [] стоит суммарная ценность на каждом шаге алгоритма. Видно, что для конкретного примера она равна [7].
Приближённые алгоритмы
К приближенным алгоритмам относятся следующие:
Жадный алгоритм
Согласно жадному алгоритму предметы сортируются по убыванию стоимости единицы каждого. Помещаем в рюкзак то, что помещается и одновременно и самое дорогое, т.е с максимальным отношением цены к весу.
Для сортировки предметов потребуется . Далее организуется проход по всем элементам цикла.
Точное решение можно получить не всегда.
Пример. Пусть вместимость рюкзака . Предметы уже отсортированы. Применяем к ним жадный алгоритм.
i | вес | цена | цена/вес |
---|---|---|---|
1 | 20 | 60 | 3 |
2 | 30 | 90 | 3 |
3 | 50 | 100 | 2 |
Кладём в рюкзак первый, а за ним второй предметы. Третий предмет в рюкзак не влезет. Суммарная ценность поместившегося равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Видно, что жадный алгоритм не обеспечивает оптимального решения, поэтому относится к приближенным.
Метаалгоритмы
Генетический алгоритм
Генетические алгоритмы были предложены Джоном Генри Холландом в 1970 году[20] и относятся к так называемым метаалгоритмам. Идея — составление алгоритмов поиска на основе биологической модели механизмов естественного отбора[21]. Базовыми понятиями являются : популяция, отбор, мутация, скрещивание.
Популяция. Составляется набор бинарных строк (хромосом), возможных решений. На основе первой («старой») популяции строится вторая («новая») популяция решений, которая служит «старой» для третьей популяции и т.д[21]
Отбор. Задается функция выбора, согласно которой, лучшие представители «старой» популяции выбираются для воспроизводства «новой». Следовательно, алгоритм выбирает наилучшее решение[21].
Скрещивание хромосом. «Родители» обмениваются последними пятью битами и образуют новые хромосомы — «потомки».
Скрещивание. Для пары строк («родителей») с определенной длиной выбирается произвольное число . «Родители» обмениваются между собой битами с -го по -й и получаются две новые строки («потомки»)[21].
Мутация. Изменение, происходящее с определенной вероятностью[20][21].
Содержимое рюкзака представляется в виде хромосом или бинарных строк, i-й бит которых равен единице в случае наличия предмета в рюкзаке, нулю — в случае его отсутствия. Задается целевая функция — вместимость рюкзака.
Отбор осуществляется следующим образом.
Выбирается произвольная хромосома. Пусть — максимальное расхождение между целевой функцией и хромосомой. суммарный вес всех предметов, входящих в рюкзачный вектор. — вес рюкзака при выбранной хромосоме[21].
Если , то хромосома оценивается числом .
Если , то хромосома оценивается числом .
Блок схема генетического алгоритма
По этому числу осуществляется отбор хромосом.
На рисунке показаны все этапы алгоритма[21]:
- Создание случайной популяции двоичных хромосом.
- Оценка каждой из них числом .
- Отбор на основе полученных чисел.
- Скрещивание полученных на третьем этапе хромосом.
- Мутация.
- Переход на второй шаг.
Алгоритм прерывается после заданного числа итераций.
Генетический алгоритм не гарантирует нахождение оптимального решения, однако показывает хорошие результаты за меньшее время по сравнению с другими алгоритмами[21][22].
Примечания
- ↑ 1 2 3 4 Silvano, 1990, p. 2
- ↑ 1 2 Бурков, 1974, p. 217
- ↑ Silvano, 1990, p. 1
- ↑ 1 2 Pisinger, 1995, p. 127
- ↑ 1 2 Pisinger, 1995, p. 147
- ↑ Silvano, 1990, p. 157
- ↑ Riedhammer et al, 2008, pp. 2436
- ↑ G. B. Mathews On the partition of numbers (англ.). — 1897. — P. 486-490.
- ↑ Kellerer, 2003, p. 3
- ↑ Pisinger, 1995, p. 9
- ↑ Р. Карп Reducibility Among Combinatorial Problems (англ.). — 1972.
- ↑ Шнаер, 2002, p. 19.2
- ↑ Э. М. Габидулин, А. С. Кшевецкий, А. И. Колыбельников Защита информации (рус.). — 2011.
- ↑ 1 2 Шнаер, 2002, p. 19.1
- ↑ Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future (рус.). — 2001.
- ↑ Саломаа, 1990, p. 103
- ↑ Окулов, 2007, p. 114
- ↑ Бурков, 1974, p. 225
- ↑ Новиков, p. 12
- ↑ 1 2 Zaheed Ahmed, Irfan Younas A Dynamic Programming based GA for 0-1 Modified Knapsack Problem (англ.).
- ↑ 1 2 3 4 5 6 7 8 С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития (рус.).
- ↑ Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин Применение генетических алгоритмов к решению задач дискретной оптимизации (рус.).
Литература
на русском языке
- Ананий В. Левитин. Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 160-163. — ISBN 0-201-74395-7
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
- Роберт Седжвик. Фундаментальные алгоритмы на 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
- В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.
- В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
- С. Окулов. Программирование в алгоритмах. — 2007. — С. 383.
- Б. Шнайер. Прикладная криптография. — 2-ое.
- А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — Springer-Verlag, 1990. — С. 102-150.
- Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254.
на английском языке
- Silvano Martelo, Paolo Toth Knapsack problems. — Wiley, 1990. — 306 с.
- Hans Kellerer, Ulrich Pferschy, David Pisinger Knapsack problems. — 1995.
- David Pisinger Knapsack problems. — 1995.
- K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür Packing the Meeting Summarization Knapsack. — Proc. Interspeech, Brisbane, Australia, 2008.
Ссылки
- Welcome to the Knapsack (англ.)
- Knapsack Problem By Eric Grimsom John Guttag — MIT (англ.)
- Knapsack Problem solutions in many languages at Rosetta Code (англ.)
- Das Rucksack-Problem (Knapsack Problem) (нем.)
Задача о ранце | |
---|---|
Изучение в | криптографии • математике • информатике |
Реализации | Меркля — Хеллмана • Наккаша — Штерна • Грэма — Шамира |
Дополнительно | Список задач о ранце |
NP-полные задачи | |
---|---|
Математика | |
Исследование операций:Оптимизация:Комбинаторная оптимизация | |
Максимизационная задача укладки (упаковки) | Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) |
Теория графов теория множеств | Задача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра |
Алгоритмические задачи | Задача выполнимости булевых формул (в конъюнктивной нормальной форме) |
Логические игры и головоломки | Обобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро |
См. также | Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа |
Классы сложности |