Классика оптимизации: задача рюкзака (knapsack problem). Алгоритм рюкзака схема


Алгоритм Рюкзака - Варианты рюкзака

 После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографических методов.

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

  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) : вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна.

 Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны. Криптосистема Lu-Lee была взломана, ее модификация также оказалась небезопасной. Вскрытия. Криптосистема Pieprzyk была взломана аналогичным образом.

 Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest, несмотря на "специализированное вскрытие" - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен. Более того, учитывая легкость с которой пали все остальные варианты, доверять устоявшим пока вариантом, по видимому, неосторожно.

 

algoritm-rukzaka.narod.ru

задача рюкзака (knapsack problem) / Хабр

Рассмотрим следующую ситуацию. Допустим вы хотите поехать за границу, но валюту вам не меняют — вы можете перевезти с собой лишь товары для реализации на свободном рынке «там». С собой в самолет разрешено взять не более 20 кг. Возникает вопрос – какие товары взять, чтобы перевезти максимальную ценность, учитывая ограничение по весу? Водку (17$ / 1,5 кг), большую матрешку (30$ / 2,5 кг), балалайки (75$ / 6 кг) или еще что-то и в каких количествах? Напрашивается решение – найти товар с самым лучшим соотношением цена/вес и взять его в максимальном количестве. Посмотрим – 3 балалайки * 75$ + 1 бутылка * 17$ = 242$ (общий вес 19,5 кг). Осталось неиспользованными полкило, которые можно задействовать по-другому: 2 балалайки * 75$ + 2 большие матрешки * 30$ + 2 бутылки * 17$ = 244$ (общий вес 20 кг).

Т.е. «на глазок» не всегда может получиться самый выгодный вариант. К тому же, часто возникают дополнительные ограничения (больше 2-х бутылок не вывезти, в продаже всего 1 балалайка), да и при большом количестве товаров ручной подсчет затруднителен. Поэтому задачу формализуют для решения на компьютере.

Задача в общем виде (knapsack problem): Имеется набор предметов, каждый с определенным весом и определенной стоимостью. Из этого набора необходимо выбрать предметы с максимальной стоимостью, с учетом ограничения на максимальный вес (вес «рюкзака»).

Если в задаче можно только либо брать, либо не брать определенный товар, то задача будет бинарной (0-1 knapsack problem).

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

В нашем случае решать задачу предлагается с помощью свободно распространяемого решателя COIN-OR (www.coin-or.org) или GLPK (http://www.gnu.org/software/glpk/glpk.html), для которых есть удобная «обертка» на Python – PuLP. PuLP доступен в Google Code (http://code.google.com/p/pulp-or/).

Используя PuLP, получается вот такой код:

  1. #-*- coding: cp1251 -*-
  2. # импортируем функции PuLP
  3. from pulp import *
  4.  
  5. # Создаем новую задачу Линейного программирования (LP) с максимизацией целевой функции
  6. prob = LpProblem("Knapsack problem", LpMaximize)
  7.  
  8. # Переменные оптимизации, целые
  9. x1 = LpVariable("x1", 0, 10, 'Integer')
  10. x2 = LpVariable("x2", 0, 10, 'Integer')
  11. x3 = LpVariable("x3", 0, 10, 'Integer')
  12.  
  13. # Целевая функция ("ценность рюкзака")
  14. prob += 17*x1 + 30*x2 + 75*x3, "obj"
  15.  
  16. # Ограничение ("вес рюкзака")
  17. prob += 1.5*x1 + 2.5*x2 + 6*x3 <= 20, "c1"
  18.  
  19. # Запускаем решатель
  20. prob.solve()
  21.  
  22. # Выводим статус задачи
  23. print "Status:", LpStatus[prob.status]
  24.  
  25. # Выводим получившиеся оптимальные значения переменных
  26. for v in prob.variables():
  27.   print v.name, "=", v.varValue
  28.  
  29. # Выводим оптимальное значение целевой функции
  30. print ("objective = %s$" % value(prob.objective))
* This source code was highlighted with Source Code Highlighter. Файл можно загрузить отсюда: knapsack.py

В результате работы скрипта получаем решение:~$ python knapsack.py Status: Optimal x1 = 2.0 x2 = 2.0 x3 = 2.0 objective = 244.0$ Приятно видеть, что для данной задачи нам удалось его обнаружить самим.

Продолжая эксперименты вы можете увеличивать количество переменных, вводить новые ограничения. К тому же, большое количество других примеров можно найти в документации к PuLP (PDF)

habr.com

Алгоритм Рюкзака - Задача о рюкзаке :PTAS

Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.

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

Если мы отмасштабируем коэффициенты c1,…,cn, поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины n⋅scale.

Если потребовать, чтобы эта величина не превосходила ε1+εf∗, то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.

Обозначая оптимум «отмасштабированной» задачи через f˜, получаем, что f˜≥f∗−ε1+εf∗=f∗(1+ε), то есть оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в 1+ε раз.

При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в scale раз по сравнению с исходной. И таким образом, для отмасштабированной задачи, версия алгоритма, ориентированная на отбор «самых легких решений» будет работать существенно меньшее время.

Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f*, и не можем выбрать коэффициент scale, который, чтобы решение было 1+ε-оптимальным, не должен превышать εf∗n(1+ε), с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.

Поэтому, важное наблюдение состоит в том, что вместо f* можно рассматривать нижнюю оценку f*, обозначим ее flb, и выбирать параметр масштабирования scale=εflbn(1+ε) тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.

Таким образом, стоит задача выбора нижней оценки flb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f*, так как это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты c1,…,cn и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.

Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию ncmax≥f∗≥flb≡cmax,, где cmax=maxici; и получим функцию «knapsack_ptas_trivial».

Какова сложность этого алгоритма? Она, есть величина O(nf˜). Учитывая, что f∗≤ncmax, а f˜≤ncmaxscale, получаем оценку сложности алгоритма «knapsack_ptas_trivial»: O(nf˜)=On2cmaxscale=On3(1+ε)ε=On3ε.

Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.

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

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма: O(nf˜)=OnfGscale=On2(1+ε)ε=On2ε.

algoritm-rukzaka.narod.ru

Немного об укладке рюкзака / Хабр

Многим известна так называемая задача об укладке рюкзака. Вкратце напомню: из кучи предметов нужно выбрать такие, чтобы рюкзак был напихан под завязку и его еще можно было уволочь. Говоря более формально, необходимо из данного набора A пар чисел a(i)b(i), выбрать такие, чтобы сумма чисел а не превосходила наперед заданного S, а сумма чисел b была максимальной. Σa(n) ≤ S, Σb(n)=max.

Исходный набор:

Σ
a 3 14 25 26 32 2 28 23 1 9 163
b 11 12 5 30 31 25 19 27 32 33 225
В последней колонке указан суммарный вес Σa всех предметов и их суммарная стоимость Σb. Задаваемое S (грузоподъемность) не должна превышать Σa, иначе решение тривиально — мы можем унести все. Учитывая эти ограничения, с помощью суммарной стоимости Σb мы можем оценить, насколько суммарная стоимость полученного решения отличается от абсолютного максимума.

Существует несколько способов решения данной задачи, они описаны в Википедии. Нам интересен "жадный" алгоритм. Он заключается в вычислении для каждой пары ценности d=a/b, по которой пары сортируются и затем отбираются.

Набор с указанием ценности d:

Σ
a 3 14 25 26 32 2 28 23 1 9 163
b 11 12 5 30 31 25 19 27 32 33 225
d 3,67 0,86 0,2 1,15 0,97 12,5 0,68 1,17 32,0 3,67

Отсортированный по d набор

Σ
a 1 2 3 9 23 26 32 14 28 25 163
b 32 25 11 33 27 30 31 12 19 5 225
d 32,0 12,5 3,67 3,67 1,17 1,15 0,97 0,86 0,68 0,20

Попробуем найти решение при S=60.

Σ
a 1 2 3 9 23 26 32 14 28 25 163
b 32 25 11 33 27 30 31 12 19 5 225
d 32,0 12,5 3,67 3,67 1,17 1,15 0,97 0,86 0,68 0,20
Первые пять предметов дадут нам Σa=38, Σb=128. Следующий предмет не помещается. С ним Σa=64. Дыра, оставшаяся после укладки первых пяти предметов получилась размером: 60-38=22. Если просмотреть набор до конца, находится еще один предмет, который в эту дыру помещается.
Σ
a 1 2 3 9 23 26 32 14 28 25 163
b 32 25 11 33 27 30 31 12 19 5 225
d 32,0 12,5 3,67 3,67 1,17 1,15 0,97 0,86 0,68 0,20
Итого: Σa=52, Σb=140.

К сожалению, это не является оптимальным решением.

Если мы заменим предмет 23-27 на 26-30,

Σ
a 1 2 3 9 23 26 32 14 28 25 163
b 32 25 11 33 27 30 31 12 19 5 225
d 32,0 12,5 3,67 3,67 1,17 1,15 0,97 0,86 0,68 0,20
то Σa=55, Σb=143, что уже является оптимальным решением.

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

Вместо простого отношения d=b/a, возьмем d=b2/a и по-прежнему отсортируем по d.

Отсортированный по d=b2/a набор

Σ
a 1 2 9 3 26 23 32 14 28 25 163
b 32 25 33 11 30 27 31 12 19 5 225
d 1024 312,5 121 40,33 34,6 31,7 30,0 10,3 12,9 1,0
 Для того же S=60
Σ
a 1 2 9 3 26 23 32 14 28 25 163
b 32 25 33 11 30 27 31 12 19 5 225
d 1024 312,5 121 40,33 34,6 31,7 30,0 10,3 12,9 1,0
Σa=55, Σb=143. Мы сразу приходим к оптимальному решению.

Таким образом задача укладки рюкзака решается за линейное время и не является NP полной.

habr.com

НОУ ИНТУИТ | Лекция | Генетические алгоритмы для задач комбинаторной оптимизации

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

2.1. Задача об укладке рюкзака

Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом C и n различных предметов. Каждый предмет i имеет известный объем W_i и стоимость P_i(i=1,\dots,n). В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем C. Форма предметов здесь не учиты.

Формальная постановка задачи: для данного множества весов W_i, стоимостей P_i и объема C надо найти двоичный вектор

X=(x_1,\dots,x_n)\mbox{, где}\ x_i=\begin{cases}1,\mbox{если предмет помещается в рюкзак,}\\0,\mbox{в противном случаи.}\end{cases}

и при этом должно выполняться условие:

V=\sum_{i=1}^n W_i\le C\mbox{ и }\sum_{i=1}^n P_i=\max

Так как решение задачи можно представить двоичным вектором X= (x_1,\dots, x_n), то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом на каждом шаге итерации надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению V\le C. В случае невыполнения ограничения "неправильное" потенциальное решение должно быть уничтожено, что ведет к сокращению популяции.

В качестве фитнесс-функции в простейшем случае можно взять

P(X)=\sum_{i=1}^n x_i\cdot P_i, но в этом случае, как указано выше, есть проблемы с неправильными решениями.

Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы [4,5]: 1) введение в фитнесс-функцию дополнительного штрафа; 2) использование алгоритмов "восстановления" некорректных решений.

  1. В первом случае в фитнесс-функцию вводится дополнительная штрафная функция, которая для неправильных решений дает большие отрицательные значения ЦФ. При этом задача с ограничениями трансформируется в задачу без ограничений путем назначения штрафа для некорректных решений. Фитнесс-функция для каждой особи может быть определена следующим образом f(X)=\sum_{i=1}^n x_i\cdot P_i-Pen(X)

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

    Здесь для всех трех случаев .

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

    В этом случае в качестве фитнесс-функции используется

    f(X')=\sum_{i=1}^n x_i'P_i, где вектор X'– восстановленная версия исходного вектора X. Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления.

    При этом используются два основных способа выбора объекта:

    • случайный выбор объекта из рюкзака;
    • "жадное восстановление", при котором вначале все предметы сортируются в порядке убывания их стоимости P_i и на каждом шаге для удаления выбирается предмет минимальной стоимости (из имеющихся в рюкзаке).
  3. Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения.

    Рассмотрим один из возможных вариантов алгоритма декодирования, который основан на кодировании решения вектором целых чисел, так называемом "упорядоченном представлении" (ordinal representation), подробно описанном в разделе 3.3.2. Здесь каждая хромосома кодируется вектором e целых чисел, где i-я компонента вектора – есть целое число в диапазоне от 1 до n-i+1. "Упорядоченное представление" использует для ссылок (базовый) список предметов L. Вектор e фактически содержит указатели на базовый список L. Декодирование вектора осуществляется путем выбора соответствующего предмета из текущего списка и удаления его из базового списка. Например, при базовом списке предметов L=(1,2,3,4,5,6) текущий вектор e=(4,3,4,1,1,1) декодируется в следующую последовательность предметов: 4, 3, 6, 1,2, 5. Первым в рюкзак включается четвертый элемент списка L- 4, который устраняется из L. Далее в рюкзак включается третий элемент из текущего списка L. Затем включается 6 - четвертый элемент текущего L и т.д. Подробнее описание этого представления и выполнение кроссинговера на нем описано в разделе 2.3.2. В данном методе хромосома может интерпретироваться как стратегия (порядок) включения предметов в решение. Отметим, что основным достоинством данного кодирования хромосомы является то, что на нем работает одноточечный кроссинговер. То есть для двух допустимых решений –родителей кроссинговер порождает также допустимое решение–потомок. Оператор мутации при данном представлении выполняется путем замены i-го гена (целочисленной компоненты вектора) на случайное целое число из диапазона [1,\dots,n-i+1].

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

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

www.intuit.ru