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

Обновлено: 25.06.2024

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Кафедра прикладной математики и информатики КУРСОВАЯ РАБОТА

Методы решения задачи о рюкзаке Выполнил студент 3 курса группы ПМ-31

Перевощиков Сергей Владимирович

Научный руководитель: к.п.н, доцент кафедры

прикладной математики и информатики

Разова Елена Владимировна Киров 2010 Оглавление Введение

Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи

1.1 Постановка задачи о рюкзаке

1.2 NP – полнота задачи

Глава 2 Методы решения задачи о рюкзаке

2.1 Классификация методов

2.2 Динамическое программирование

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

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

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

2.6 Сравнительный анализ методов

2.7 Модификации задачи

Приложение 4 Введение Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.

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

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

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

Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.

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

Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм. Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и

Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес w_i и полезность p_i , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.

1. Каждый предмет можно брать только один раз.

2. Каждый предмет можно брать сколько угодно раз.

3. Каждый предмет можно брать определенное количество раз

4. На размер рюкзака имеется несколько ограничений.

5. Некоторые вещи имею больший приоритет, чем другие

1.1 Постановка задачи о рюкзаке

Задача о ранце – одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца. Традиционно полагают что W_i , V_i , W, P – целые неотрицательные числа, но встречаются и другие постановки, условия в которых могут отличаться.[6] Возможны следующие вариации задачи:

Каждый предмет можно брать только один раз. Формализуем. Пусть задано конечное множество предметов , для каждого , определена стоимость p_i и вес w_i , тогда нужно максимизировать , при ограничениях , где W-вместимость ранца, а x_i =1, если предмет взят для загрузки и x_i =0 если не взят. Если на размер рюкзака имеется только одно ограничение, то задача называется одномерной, в противном случае – многомерной.

Каждый предмет можно брать m раз. Формализация аналогична, разница лишь в том, что x_i принимает значения на интервале (0..m).

Каждый предмет можно брать неограниченное количество раз. Очевидно, что x_i лежит в диапазоне (0..[W/w_i ]) квадратные скобочки означают целую часть числа. [6]

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

1.2 NP – полнота задачи

Большинство используемых алгоритмов имеют полиномиальное время работы, если размер входных данных – n, то время их работы в худшем случае оценивается как где k это константа. Но встречаются задачи, которые нельзя разрешить за полиномиальное время. Это класс NP - полных задач. Некоторые задачи этого класса на первый взгляд аналогичны задачам разрешимым за полиномиальное время, но это далеко не так. Задача называется NP - полной, если для нее не существует полиномиального алгоритма.[3] Алгоритм называется полиномиальным, если его сложность O(N) в худшем случае ограничена сверху некоторым многочленом (полиномом) от N. Такие задачи возникают очень часто в различных областях: в булевой логике, в теории графов, теории множеств, кодировании информации, в алгебре, в биологии, физике, экономике, теории автоматов и языков. Считается что NP - полные задачи очень трудноразрешимы, а так же, что если хотя бы для одной из них удастся найти полиномиальный алгоритм, то такой алгоритм будет существовать для любой задачи из этого класса. Над поиском полиномиальных алгоритмов к таким задачам трудились многие ученые, и все же и все же при таком разнообразии NP - полных задач, ни для одной из них до сих пор не найдено полиномиального алгоритма.[10]. Из всего вышесказанного следует, что если известна NP - полнота задачи, то лучше потратить время на построение приближенного алгоритма, чем пытаться построить полиномиальный, или же, если это позволяют условия, использовать алгоритмы с экспоненциальной сложностью работы

2.1 Классификация методов

На практике очень часто возникают NP-полные задачи, задач о рюкзаке – одна из них . Конечно надежд, на то что для них найдется полиномиальный алгоритм практически нет, но из этого не следует что с задачей нельзя ничего сделать. Во первых, очень часто удается построить полиномиальный алгоритм для NP – полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во вторых, данные могут быть таковы, что экспоненциальный алгоритм, например переборный сможет работать на них разумное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП – программирование. К приближенным: Жадные алгоритмы. Полный перебор – перебор всех вариантов (всех состояний) –малоэффективный, но точный метод. Метод ветвей и границ – по сути сокращение полного перебора с отсечением заведомо “плохих” решений. ДП – алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм – основан на нахождении относительно хорошего и “дешевого” решения.

2.2 Динамическое программирование

В основе метода динамического программирования лежит принцип оптимальности Беллмана:”Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным”. Проще говоря оптимальное решение на i шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.

Имеется набор из N предметов. Пусть MaxW - объем рюкзака, P_i – стоимость i-го предмета, W_i – вес i-го предмета. Value [W, i] – максимальная сумма, которую надо найти. Суть метода динамического программирования – на каждом шаге по весу 1 Weight) or (Value[Weight, i-1] >=

Value[Weight-W[i], i-1]+P[i]) then begin

Value[Weight, i]:=Value[Weight, i-1];

Take [Weight, i]:= false;

Value [Weight, i]:=Value [Weight - W[i], i-1]

Take [Weight, i]:= true;

Как было сказано ранее, алгоритм динамического программирования для ‘рюкзака’ дает точное решение путем использования дополнительной памяти O(N*MaxW), временная сложность алгоритма так же будет порядка O(N*MaxW).

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

Название метода говорит само за себя. Чтобы получить решение нужно перебрать все возможные варианты загрузки. Здесь мы будем рассматривать такую постановку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено), каждый предмет типа I имеет вес W_i и стоимость P_i , i=(1,2..N). Требуется определить максимальную стоимость груза вес, которого не превышает W. Очевидна простая рекурсивная реализация данного подхода Рис 1.4. Временная сложность данного алгоритма равна O(N!). Алгоритм имеет сложность факториал и может работать лишь с небольшими значениями N. С ростом N, число вариантов очень быстро растет, и задача становится практически неразрешимой методом полного перебора. На рис 1.5 показано дерево перебора, дерево имеет 4 уровня. В каждом кружочке показан вес предмета, корень дерева – нулевой вес, то есть когда рюкзак пуст. Первый предмет можно выбрать четырьмя способами, второй – тремя, третий – двумя, а дальше можем взять только один оставшийся предмет.

N - Количество предметов. Пусть MaxW - объем рюкзака, P_i – стоимость i-го предмета, W_i – вес i-го предмета.

Procedure Search(Nab, OstW, Stoim:integer);

var i:integer;

if (Nab > N) and (Stoim > Max) then begin

с рассматриваемым моментом времени

и состояние достижимо, то изменяем

оценку вершины, соответствующей полноте

For i:=1 To K Do Res:=Max(Res,SNew[i]);

в окончательном массиве оценок>

Реализация метода ДП - программирования для задачи о рюкзаке:

Const MaxW = 200; MaxN = 100;

var Value:array [0..MaxW,0..MaxN] of integer;

Take :array [0..MaxW,0..MaxN] of boolean;

W,P :array [0..MaxN] of integer;

i, N, Weight, MaxWeight :integer;

for i:=1 to N do readln(W[i], P[i]);

fillchar(Take, sizeof(Take), false);

fillchar(Value, sizeof(Value), 0);

for Weight:=1 to MaxWeight do begin

if (W[i]> Weight) or (Value[Weight, i-1] >= Value[Weight-W[i], i-1]+P[i]) then begin

Дано [math]N[/math] предметов, [math]W[/math] — вместимость рюкзака, [math]w=\,w_,\dots,w_\>[/math] — соответствующий ему набор положительных целых весов, [math]p=\,p_,\dots,p_\>[/math] — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин [math]B=\,b_,\dots,b_\>[/math] , где [math]b_ = 1 [/math] , если предмет [math]n_i[/math] включен в набор, [math] b_ = 0 [/math] , если предмет [math]n_i[/math] не включен, и такой что:

[math]b_ w_+ \dots + b_ w_ \leqslant W[/math]
[math]b_ p_+ \dots + b_ p_ [/math] максимальна.

Задачу о рюкзаке можно решить несколькими способами:

Перебирать все подмножества набора из N предметов. Сложность такого решения [math]O(>)[/math] .

Методом Meet-in-the-middle. Сложность решения [math] O(>) [/math]

Метод динамического программирования. Сложность — [math]O(NW)[/math] .

Пусть [math]A(k, s)[/math] есть максимальная стоимость предметов, которые можно уложить в рюкзак вместимости [math]s[/math] , если можно использовать только первые [math]k[/math] предметов, то есть [math]\[/math] , назовем этот набор допустимых предметов для [math]A(k,s)[/math] .

[math]A(k, 0) = 0[/math]

[math]A(0, s) = 0[/math]

Найдем [math]A(k, s)[/math] . Возможны 2 варианта:

Если предмет [math]k[/math] не попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов [math]\\>[/math] , то есть [math]A(k,s) = A(k-1, s)[/math]
Если [math]k[/math] попал в рюкзак. Тогда [math]A(k, s)[/math] равно максимальной стоимости рюкзака, где вес [math]s[/math] уменьшаем на вес [math]k[/math] -ого предмета и набор допустимых предметов [math]\\>[/math] плюс стоимость [math]k[/math] , то есть [math]A(k-1, s-w_k) + p_k[/math]

[math] A(k, s) = \begin A(k-1, s), & b_k = 0 \\ A(k-1, s-w_k) + p_k, & b_k = 1 \\ \end [/math]

То есть: [math]A(k,s) = \max(A(k-1,s), A(k-1,s-w_) + p_)[/math]

Стоимость искомого набора равна [math]A(N,W)[/math] , так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака [math]W[/math] .

Восстановим набор предметов, входящих в рюкзак

Будем определять, входит ли [math]n_i[/math] предмет в искомый набор. Начинаем с элемента [math]A(i,w)[/math] , где [math]i = N[/math] , [math]w = W[/math] . Для этого сравниваем [math]A(i,w)[/math] со следующими значениями:

Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов [math]\\>[/math] , то есть [math]A(i-1, w)[/math]
Максимальная стоимость рюкзака с вместимостью на [math]w_i[/math] меньше и набором допустимых предметов [math]\\>[/math] плюс стоимость [math]p_i[/math] , то есть [math]A(i-1, w-w_i)+p_i[/math]

Заметим, что при построении [math]A[/math] мы выбирали максимум из этих значений и записывали в [math]A(i, w)[/math] . Тогда будем сравнивать [math]A(i, w)[/math] c [math]A(i-1, w)[/math] , если равны, тогда [math]n_i[/math] не входит в искомый набор, иначе входит.

Метод динамического программирование всё равно не позволяет решать задачу за полиномиальное время, потому что его сложность зависит от максимального веса. Задача о ранце (или задача о рюкзаке) — одна из NP-полных задач комбинаторной оптимизации.

Сначала генерируем [math]A[/math] .

Затем найдем набор [math]ans[/math] предметов, входящих в рюкзак, рекурсивной функцией:

Сложность алгоритма [math]O(NW)[/math]

[math]W = 13, N = 5[/math]

[math]w_ = 3, p_ = 1 [/math]

[math]w_ = 4, p_ = 6 [/math]

[math]w_ = 5, p_ = 4 [/math]

[math]w_ = 8, p_ = 7 [/math]

[math]w_ = 9, p_ = 6 [/math]

1	4	5	6	7	8	9	10	11	12	13
k = 0	0	0	0	0	0	0	0	0	0	0	0
k = 1	1	1	1	1	1	1	1	1	1	1	1
k = 2	1	6	6	6	7	7	7	7	7	7	7
k = 3	1	6	6	6	7	7	10	10	10	11	11
k = 4	1	6	6	6	7	7	10	10	10	13	13
k = 5	1	6	6	6	7	7	10	10	10	13	13

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака [math]n \geqslant 3[/math] , добавляем в рюкзак 1 предмет.

Рассмотрим [math]k = 3[/math] , при каждом [math]s \geqslant 5 ([/math] так как [math]w_3 = 5)[/math] сравниваем [math]A[k-1][s][/math] и [math]A[k-1][s-w_3]+p_3[/math] и записываем в [math]A[k][s][/math] стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на [math]w_3[/math] меньше.

Максимальная стоимость рюкзака находится в [math]A(5, 13)[/math] .

Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.

Начиная с [math]A(5, 13)[/math] восстанавливаем ответ. Будем идти в обратном порядке по [math]k[/math] . Красным фоном обозначим наш путь

Таким образом, в набор входит [math]2[/math] и [math]4[/math] предмет.

Стоимость рюкзака: [math] 6 + 7 = 13[/math]

Вес рюкзака: [math] 4 + 8 = 12[/math]

Каждый предмет может быть выбран ограниченное [math]b_i[/math] число раз. Задача выбрать число [math]x_i[/math] предметов каждого типа так, чтобы

максимизировать общую стоимость: [math]\sum_^N p_ix_i[/math] ;

выполнялось условие совместности: [math]\sum_^N w_ix_i \leqslant W[/math] ;

где [math] x_i \in (0,1,\dots,b_i)[/math] для всех [math] i= 1,2,\dots,N[/math] .

При небольших [math]b_i[/math] решается сведением к классической задаче о рюкзаке. В иных случаях:

Методом ветвей и границ.
Методом динамического программирования.

Пусть [math]d(i,c)[/math] максимальная стоимость любого возможного числа предметов типов от 1 до [math]i[/math] , суммарным весом до [math]c[/math] .

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 1 до [math]W[/math] , по рекуррентной формуле:

[math]d(i,c) = \max(d(i, c), d(i - 1, c - lw_i) + lp_i) [/math] по всем целым [math] l [/math] из промежутка [math] 0 \leqslant l \leqslant min(b_i,\lfloor c/w_i \rfloor)[/math] .

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного.

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Сложность алгоритма [math]O(NW^2)[/math] .

Каждый предмет может быть выбран любое число раз. Задача выбрать количество [math]x_i[/math] предметов каждого типа так, чтобы

максимизировать общую стоимость: [math]\sum_^N p_ix_i[/math] ;

выполнялось условие совместности: [math]\sum_^N w_ix_i \leqslant W[/math] ;

где [math] x_i \geqslant 0 [/math] целое, для всех [math] i= 1,2,\dots,N[/math] .

Самые распространенные методы точного решения это:

Метод ветвей и границ.
Метод динамического программирования.

Пусть [math]d(i,c)[/math] - максимальная стоимость любого количества вещей типов от 1 до [math]i[/math] , суммарным весом до [math]c[/math] включительно.

Заполним [math]d(0,c)[/math] нулями.

Тогда меняя i от 1 до [math]N[/math] , рассчитаем на каждом шаге [math]d(i,c)[/math] , для [math]c[/math] от 0 до [math]W[/math] , по рекуррентной формуле:

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив [math]d(c)[/math] вместо двумерного и использовать формулу:

[math] d(c) = \max(d(c), d(c - w_i) + p_i) [/math] ;

Сложность алгоритма [math]O(NW)[/math] .

Задача выбрать часть [math]x_i[/math] каждого предмета так, чтобы

максимизировать общую стоимость: [math]\sum_^N p_ix_i[/math] ;

выполнялось условие совместности: [math]\sum_^N w_ix_i \leqslant W[/math] ;

где [math] 0 \leqslant x_i \leqslant 1[/math] дробное, для всех [math] i= 1,2,\dots,N[/math] .

Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

Нужно выбрать подмножество так, чтобы сумма ближе всего к [math]W[/math] , но не превысила его. Формально, нужно найти набор бинарных величин [math]x_i[/math] , так чтобы

максимизировать общую стоимость: [math]\sum_^N w_ix_i[/math] ;

выполнялось условие совместности: [math]\sum_^N w_ix_i \leqslant W[/math] ;

[math] x_j = 1 [/math] если [math] j[/math] предмет назначен рюкзаку, иначе [math] x_ = 0 [/math] , для всех [math] i= 1,2,\dots,N[/math] .

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

Метод динамического программирования.
Использовать различные сложные алгоритмы [1][2][3][4] .

Пусть [math]d(i,c)[/math] максимальная сумма [math]\leqslant c[/math] , подмножества взятого из [math] 1, \dots,\ i[/math] элементов.

Заполним [math]d(0,c)[/math] нулями.

После выполнения в [math] d(N,W) [/math] будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма [math]O(NW)[/math] .

Часто задачу ставят как, дать сдачу наименьшим количеством монет.

минимизировать количество взятых предметов: [math]\sum_^N x_i[/math] ;

сумма весов выбранных предметов равнялась вместимости рюкзака: [math]\sum_^N w_ix_i = W[/math] ;

Где [math] x_i \geqslant 0 [/math] целое, для всех [math] i= 1,2,\dots,N[/math] .

Самые распространенные методы точного решения это:

Метод ветвей и границ.
Метод динамического программирования.

Пусть [math]d(i,c)[/math] минимальное число предметов, типов от 1 до [math]i[/math] , необходимое, чтобы заполнить рюкзак вместимостью [math]c[/math] .

Пусть [math]d(0,0) = 0[/math] , а [math]d(0,c) = \inf[/math] для всех [math]c \gt 0[/math] .

После выполнения в [math] d(N,W) [/math] будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

[math] d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, \dots, W[/math] .

Сложность алгоритма [math]O(NW)[/math] .

Математически задачу можно представить так:

минимизировать количество рюкзаков: [math]\sum_^N y_i[/math] ;

так чтобы выполнялось условие на совместность: [math]\sum_^N w_ix_ \leqslant Wy_j \qquad j \in [/math] ;

[math] x_ = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_ = 0 [/math] .

[math] y_i = 1 [/math] если [math] i[/math] рюкзак используется. Иначе [math] y_i = 0 [/math] .

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

Максимизировать [math]\sum_^M \sum_^ p_jx_[/math]

так, чтобы [math]\sum_^N w_jx_ \leqslant W_i[/math] выполнялось для всех [math] i= 1,2,\dots,N[/math] .

[math]\sum_^x_=1[/math] для всех [math] i= 1,2,\dots,N[/math] .

[math] x_ = 1 [/math] если [math] j[/math] предмет назначен [math]i [/math] рюкзаку. Иначе [math] x_ = 0 [/math] .

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

Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.

Максимизировать стоимость выбранных предметов [math]\sum_^M\sum_^N p_ x_[/math] ,

при выполнении условия совместности [math]\sum_^N w_ x_ \leqslant W_i \qquad i=1, \ldots, M[/math] .

[math] \sum_^M x_ \leqslant 1 \qquad j=1, \ldots, N[/math] .

[math] x_ \in \ \qquad i=1, \ldots, N, \quad j=1, \ldots, N[/math] .

Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом.

Для криптографии с открытым ключом требуется два ключа.

Хотя это кажется малополезным, если вы пытаетесь сохранить что-то в секрете!

Первый общий алгоритм с открытым ключом использовал алгоритмом ранца.

Что делать, если злоумышленнику стал известен открытый ключ?

Есть ответ: открытый ключ должен получаться из секретного ключа при помощи преобразования ( односторонней функции) , обладающего следующими двумя свойствами:

, зная A, вычислить саму функцию легко

, а вычислить обратную функцию трудно

Задача о рюкзаке формулируется так

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

В наиболее известном варианте задачи о рюкзаке требуется выяснить, обладает ли данная пара решением. В варианте, используемом в криптографии, нужно для данного входа построить решение, зная, что такое решение существует. Оба эти варианта являются NP-полными.

Аналогия с рюкзаком

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

Т.е представьте, что у вас есть набор гирь 1, 6, 8, 15 и 24, вам нужно упаковать рюкзак весом 30.

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

Но что будет, если существует несколько сотен чисел ?
В нашем примере n = 5, чтобы не усложнять изложение. В реальных условиях пpимер будет иметь, скажем, 300 . Суть здесь в том, что неизвестны алгоритмы, имеющие существенно меньшую сложность по сpавнению с полным перебором. Поиск среди подмножеств не поддается обработке. В самом деле, задача о рюкзаке известна как NP-полная… NP-полные задачи рассматриваются как трудновычислимые.

Подходит ли функция под указанные требования?

Определим функцию следующим образом. Любое число может быть задано двоичным представлением из pазpядов, где пpи необходимости добавляются начальные нули. Теперь определим как число, получаемое из суммированием всех таких , что соответствующий pазpяд в двоичном представлении равен 1.

Функция определялась набором . Очевидно, что если мы в состоянии вычислить из , то пpактически за то же время будет решена задача о рюкзаке: по немедленно вычисляется его двоичное представление, которое в свою очередь дает компоненты набора , входящие в сумму для . С другой стороны, вычисление из является легким. Так как задача о рюкзаке NP-полна, является хорошим кандидатом для односторонней функции. Конечно, надо потребовать, чтобы было достаточно большим, скажем, не менее .

Шифрование

Открытый текст (англ. plain text) — в криптографии исходный текст, подлежащий шифрованию, либо получившийся в результате расшифровки. Может быть прочитан без дополнительной обработки (без расшифровки).

Шифровать можно двумя способами:

Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины (например, Вы можете представить вес 30 двоичным кодом 11110). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие.

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

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

Для сверхрастущих векторов Α задача о рюкзаке легко решаема. Т.е. рюкзак собрать несложно.
Рассмотрим на примере:

Общий вес ранца сравнить с наибольшим весом в последовательности.
Если общий вес меньше числа, значит, в рюкзаке его нет. Если общий вес больше числа, он в рюкзаке.
Вычесть число из общей суммы и сравните со следующим по величине числом.
Повторить (1)-(2) пока общая сумма не достигнет нуля.
Если сумма не достигает нуля, то решения нет.

Создание открытого ключа

Обозначим наименьший неотрицательный остаток от деления на ,
где — целые, , [x/m] — целая часть,

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

Лемма. Предположим, что сверхрастущий вектор и вектор получен из сильным модульным умножением относительно . Предположим далее, что , —произвольное натуральное число и . Тогда справедливы следующие утверждения.

(i) Задача о рюкзаке разрешима за линейное время. Если решение существует, то оно единственно.
(ii) Задача о рюкзаке имеет не более одного решения.
(iii) Если существует решение для входа , то оно совпадает с единственным решением для входа .
доказательство(стр. 104)

Возмём сверхрастущую последовательность; например, . Модуль должен быть больше суммы всех чисел в последовательности, например 110. Множитель не должен иметь общих делителей с модулем. Итак, давайте выберем 31.

Итак, мы вычислили открытый ключ: и закрытый ключ — .

Некоторые преимущества открытых ключей

История

Долгое время ранцевые криптосистемы рассматривались как наиболее привлекательные и перспективные криптосистемы благодаря их NP-полноте и высокой скорости шифрования и дешифрования. Многие схемы используют задачу о ранце (в различных вариациях), вот лишь несколько из них: the compact knapsack problem, the multiplicative knapsack problem, the modular knapsack problem, the matrixcover problem, the group factorization problem…

К сожалению, большинство из них уязвимы для атак. Оказалось, что нетривиально спроектировать защищенную криптосистему на основе задачи о ранце, хотя задача известна как NP-полная. Большинство ранцевых криптосистем было взломано. Несмотря на это, в отличие от целочисленной факторизации и дискретного логарифма, общая задача о рюкзаке (решении) является доказанной NP-полной проблемой.

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

Во-первых, NP-полнота основана на анализе наихудшего случая, во-вторых, NP-полнота — это характеристики общей проблемы, а не конкретного случая. Это означает, что если рассматривать среднюю сложность, задача о рюкзаке может быть несложной.

(1) А. Саломаа. Криптография с открытым ключом/ Public-Key Cryptography. — Springer-Verlag, 1990. — Стр. 75-82, стр. 101—111

(2) Мин Кин Лай. Ранцевые криптосистемы: прошлое и будущее — Калифорнийский университет, 2001
(3) Baocang Wang, Qianhong Wu, Yupu Hu. A knapsack-based probabilistic encryption scheme. 2007

Читайте также: