Full Text

Метод динамического программирования подразумевает решение задач большей размерности на основе известных решений похожих задач меньшей размерности [1]. В применении к задаче о рюкзаке при каждом увеличении размерности задачи в рюкзачном векторе появляется новый элемент, после чего принимается управляющее решение: следует ли включить новый элемент в состав «наилучшей» укладки (за счет удаления части старых предметов) или оставить ее без изменений. Отметим фундаментальное отличие подхода к решению задачи о рюкзаке методом динамического программирования от других методов: перебору подлежат возможные веса и наборы предметов, а не варианты укладок (см. статью [2]). Тем не менее, природа данного алгоритма схожа с природой других алгоритмов решения задачи о рюкзаке: происходит отсечение части укладок, заведомо не являющихся решениями. В данном случае это происходит за счет установления границ таблицы: все веса укладок, превосходящие целевое значение, не рассматриваются. Точно такой же по формулировке подход используется в алгоритмах обхода дерева вариантов укладки [1] и в алгоритме Хоровица-Сани [4]. Динамическое программирование позволяет найти одно точное решение задачи о рюкзаке. Для практических задач оптимизации, как правило, достаточно приближенного решения. Тем не менее в ряде случаев, в частности, при анализе систем шифрования, основанных на сложности задачи о рюкзаке (например, систем шифрования Касахары [5], Растаги [6], Осипяна [7]), поиск приближенного решения не имеет смысла - должно быть найдено точное решение. Соответственно, исследование данного алгоритма представляет интерес. Схема исследуемого алгоритма описана в статье [8]. Рассматривается задача о рюкзаке в формулировке, приведенной в [9]: каждому предмету сопоставляется только значение веса. При выполнении шагов алгоритма формируется таблица весов укладок. По строкам откладывается текущее количество предметов в наборе, по столбцам - возможные веса укладок, составленных из этого набора. Заполнение данной таблицы - операция, в значительной степени определяющая сложность алгоритма и по времени, и по памяти. Каждая строка матрицы соответствует подмножеству предметов рюкзака. Строка с наибольшим номером соответствует всему множеству предметов. Строка с номером соответствует подмножеству из первых предметов. По столбцам откладываются веса укладок, а каждый элемент с координатами обозначает максимальную сумму, не превышающую , которую можно составить с использованием первых предметов. Таблица заполняется слева направо и сверху вниз. Причем решение о значении элемента в строке и столбце (обозначим его ) принимается следующим образом. Существуют три возможных варианта. Если вес нового предмета (предмет с номером ) превышает значение (т.е. новый предмет не влезет даже в пустой рюкзак), то элемент матрицы приравнивается к элементу того же столбца предыдущей строки , следовательно, комбинация предметов, дающая максимальный вес, не меняется. Если вес нового предмета не превышает , то можно добавить его в рюкзак. В этом случае там останется свободного места. Уже известно, как эффективно заполнить это место предметами - вес соответствующего поднабора уже рассчитан и находится в ячейке . Но, вполне возможно, что вес нового набора, составленного таким образом, оказался меньше, чем у составленного до этого набора из предметов. Поэтому необходимо сравнить и . Если больше, значит, добавив новый предмет в рюкзак и эффективно заполнив оставшееся место остальными предметами, можно увеличить наибольшую сумму. В противном случае новый предмет не позволяет улучшить результат и, как следствие, максимальное значение суммы (как и соответствующая укладка) остается без изменений. Можно формализовать процесс принятия решения следующим образом: Рассмотрим пример. Предположим, что предметы имеют веса (1; 4; 5; 6; 9), целевой вес . Соответствующая таблица будет иметь 11 столбцов ( ) и 6 строк ( ). Нулевая строка (тривиальные решения подзадачи размерности ) и нулевой столбец таблицы (задача с нулевой максимальный весом) являются нулевыми. Далее таблица заполняется в соответствии с приведенным выше процессом принятия решения. В качестве примера рассмотрим заполнение ячейки . Элемент располагается в четвертой строке, что соответствует добавлению в рюкзак четвертого по счету элемента, имеющего вес 6. Ограничение позволяет добавить этот элемент в укладку. Оставшееся место 1 необходимо распределить оптимально между оставшимися тремя предметами. Уже известно, что суммарный вес такой укладки составляет . Добавляя к весу этой укладки вес нового элемента 6, получаем суммарный вес, равный 7. Это больше, чем вес прежней оптимальной укладки . Значит, . Для вычисления укладки, являющейся решением, достаточно проследить изменения суммарного веса по таблице. Целевой вес (если он достижим) всегда хранится в последней ячейке таблицы. В данном случае . Поскольку , можно сделать вывод, что пятый элемент не существенен для достижения максимальной суммы (это не значит, что данный элемент не может являться частью решения). Исключив пятый элемент, можно рассмотреть подзадачу с четырьмя предметами и таким же целевым весом. Аналогично четвертый элемент не существенен: . Теперь рассматривается следующая подзадача: имея набор предметов (1; 4; 5), построить укладку с весом . Легко видеть, что значения для данной подзадачи совпадают со значениями для исходной задачи. Видим, что при добавлении третьего элемента величина максимальной суммы увеличилась с 5 до 10. Соответственно, этот элемент входит в оптимальную укладку. Третий элемент имеет вес . Удаление данного элемента из рассмотрения приводит к очередной подзадаче: имея набор предметов (1; 4), построить укладку с весом . Рассчитанные ранее значения по-прежнему верны. Аналогично второй предмет входит в оптимальную укладку: . Этот предмет имеет вес 4, значит, очередная подзадача будет звучать так: имея набор из одного предмета 1, найти укладку с весом, равным: . Как и на предыдущих шагах, применимы ранее рассчитанные значения . Повторяя описанное действие в последний раз, убеждаемся, что первый предмет также входит в укладку. Таким образом, искомая оптимальная укладка имеет вид (1; 1; 1; 0; 0). У данной задачи есть и другие решения, но вычисляется лишь одно из них, причем строение алгоритма таково, что предпочтение отдается элементам с младшими номерами. Целевой вес должен находиться в диапазоне в противном случае решение задачи тривиально. Заметим, что показатель плотности рюкзачного вектора связывает и . Можно вычислить: Соответственно, рассматриваемый диапазон весов будет следующим: Каждый из столбцов содержит строк, потребление ячеек памяти для алгоритма будет составлять: Для размерности задачи при плотности это будет ячеек памяти. Если предположить, что для хранения суммарных весов достаточно 8 бит, то объем памяти, необходимый для проведения вычислений, составит свыше ГБ, что практически недостижимо на практике. Разумеется, при размерности задачи 100 и более приводить данный подсчет не имеет смысла. Однако требования к памяти резко падают с увеличением плотности рюкзачного вектора, поэтому очень плотные экземпляры задач вполне могут быть решены при помощи динамического программирования. Например, рюкзачный вектор той же размерности плотности 100 потребует всего байт памяти. Временная сложность алгоритма растет линейно по и по , так как на первом этапе работы алгоритма заполняется таблица размером , а на втором за операций строится вектор укладки. Соответственно, именно экспоненциальный рост сложности по памяти ограничивает применение данного алгоритма. Далее на рис. 1 приводится расчетный график роста сложности алгоритма по памяти. Отражена зависимость требуемого объема оперативной памяти (в битах) от размерности задачи. Построены линии (по худшему случаю - целевой вес близок к сумме всех элементов) для плотностей от (1) до (8) с шагом 1. Предполагается, что для хранения суммарных весов достаточно ячеек памяти объемом 64 бита. На рис. 2 приведены результаты вычислительного эксперимента. Решаются задачи о рюкзаке различных размерностей; суммы элементов рюкзачного вектора не превышают размерности 18 бит. Рассмотрены случаи, при которых целевой вес лежит в районе 50 % и в районе 100 % от максимально возможного значения. Для сравнения приведено также время решения этих же задач методом прямого перебора (красная линия). Для вычислительного эксперимента использовался компьютер со следующими характеристиками: Intel Core 2 Quad Q9505; 4 ядра с тактовой частотой 2,83 МГц, оперативной памятью объемом 8 ГБ с установленной интегрированной средой разработки Microsoft Visual Studio 2013 Express. Для сборки исходных кодов использовался компилятор Microsoft Visual C++ версии 12. Стенд функционирует под управлением 64-разрядной операционной системы Windows 7 Enterprise с установленным пакетом обновлений Service Pack 1. Рис. 1. Рост сложности алгоритма динамического программирования по памяти Рис. 2. Рост временной сложности алгоритма динамического программирования Несмотря на ощутимое преимущество во временной сложности, высокие требования к объему памяти резко ограничивают возможность применения алгоритма динамического программирования. При плотности рюкзачных векторов, близкой к 1, его применение затруднено даже для задач малой размерности. Тем не менее, с ростом плотности рюкзачных векторов пространственная и временная сложность алгоритма заметно сокращается. Поскольку развитие методов анализа рюкзачных систем шифрования, основанных на использовании атак низкой плотности, принуждает исследователей повышать плотность генерируемых рюкзачных векторов (см. [10]), следует иметь в виду влияние данной особенности алгоритма динамического программирования на стойкость современных рюкзачных систем шифрования.

About the authors

M. A Kupriyashin

National Research Nuclear University “MEPhI”

Email: kmickle@yandex.ru

G. I Borzunov

National Research Nuclear University “MEPhI”

Email: parproc@gmail.com

References

Statistics

Views

Abstract - 106

PDF (Russian) - 25

Refbacks

• There are currently no refbacks.