Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ БУЛЕВОЙ ЗАДАЧИ О РЮКЗАКЕ НА ОСНОВЕ СОРТИРОВКИ И ВИДОИЗМЕНЕНИЯ ФОРМУЛ ВИЕТА

Ромм Я.Е. 1 Назарьянц Е.Г. 1
1 Таганрогский институт имени А.П. Чехова (филиал) ФГБОУ ВПО РГЭУ (РИНХ)
Предложены последовательный и два параллельных детерминированных алгоритма точного решения задачи об одномерном булевом рюкзаке. Первый параллельный алгоритм дает линейную оценку, при этом конструктивно задает каждое сочетание предметов с попутным вычислением веса и цены сочетания. Второй параллельный алгоритм выполняется за логарифмическое число шагов. Все варианты алгоритмов основаны на матричной модификации формул Виета для выражения коэффициентов многочлена по его корням, с помощью которой конструктивно задаются все сочетания общего вида из n предметов по l с попутным вычислением веса и цены каждого сочетания. В параллельном варианте используется алгоритм максимально параллельной сортировки подсчетом. Оценки временной сложности параллельных алгоритмов вида T(22n–3) = O(n) и T(22n–1) = O(log2n), где в скобках левой части указано количество процессоров, представлены на модели неветвящихся параллельных программ без учета обмена.
задача об одномерном булевом рюкзаке
детерминированный алгоритм точного решения
временная сложность параллельного алгоритма
видоизменение формул Виета
параллельная модификация сортировки подсчетом
1. Колпаков Р.М., Посыпкин М.А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика. – 2010. – т. 22, Вып. 1. – С. 58–73.
2. Колпаков Р.М., Посыпкин М.А., Сигал И.Х. О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. – 2010. – № 10. – С. 156–166.
3. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки: дис. ... д-ра техн. наук. – Таганрог: ТРТУ, 1999. – 546 с.
4. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. – 2007. – № 2. – С. 161–174.
5. Ромм Я.Е., Заика И.В. Численная оптимизация на основе алгоритмов сортировки с приложением к дифференциальным и нелинейным уравнениям общего вида // Кибернетика и системный анализ. – 2011. – № 2. – С. 165–180.
6. Ромм Я.Е., Назарьянц Е.Г. Детерминированный параллельный алгоритм решения задачи об одномерном булевом рюкзаке на основе сортировки и видоизменения формул Виета / ТИ имени А.П. Чехова (филиал) ФГБОУ ВПО РГЭУ (РИНХ). – Таганрог, 2015. – С. 45. Деп. в ВИНИТИ 18.02.2015, № 32-В2015.
7. Сигал И.Х, Иванова А.П. Введение в прикладное дискретное программирование. – М.: ФИЗМАТЛИТ, 2007. – 240 c.
8. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. – Л., 1982. – т. 118. – С. 159–187.

Рассматривается традиционная постановка задачи о рюкзаке: имеется набор из n предметов, каждый предмет имеет вес wi и цену pi, i = 1, 2, ..., n, требуется собрать набор с максимальной ценой таким образом, чтобы он имел вес не больше w, где w – вместимость рюкзака [7]. Формальная запись постановки задачи:

romm01.wmf

Требуется синтезировать детерминированные параллельные алгоритмы точного решения одномерной булевой задачи о рюкзаке с линейной и логарифмической оценками временной сложности. Временная сложность (кратко – время) T(R), где R – количество процессоров, будет измеряться количеством последовательных шагов алгоритма на модели неветвящихся параллельных программ без учета обмена [8]. Искомые алгоритмы строятся с применением максимально параллельной сортировки на основе видоизменения формул Виета для восстановления коэффициентов многочлена через его корни.

Алгоритм выборки всех возможных сочетаний слагаемых для решения задачи о рюкзаке

Построение алгоритма опирается на структуру матричной формулы восстановления коэффициентов многочлена по его корням с точностью до выполнения операций, при этом непосредственно в исходном виде арифметические операции не выполняются. Коэффициенты многочлена

romm02.wmf

выражаются через его корни в виде [3, 4]

romm03.wmf (1)

где xi – i-й корень многочлена, i = 0, 1, ..., n – 1, предполагается, что dn = 1.

Формулы Виета для коэффициентов того же многочлена имеют вид

romm05.wmf (2)

Левые части равенств (1) и (2) одинаковы, соответственно, равны правые части. В правых частях (2) – всевозможные сочетания корней, которые не повторяются, поэтому формула (1) порождает алгоритм генерации всех возможных сочетаний, если не принимать во внимание операции умножения и сложения. Если веса предметов в задаче о рюкзаке интерпретировать как корни многочлена, то из (1) следуют все возможные сочетания весов из n по m. В этой интерпретации произведение всех весов в сочетании заменяется на их сумму и не принимается во внимание знак слагаемых. Аналогично в (2) следует заменить знак умножения на знак сложения, знак суммы – на любой знак, обозначающий сочетание элементов (в таком качестве ниже выбрано логическое «ИЛИ»). С этими поправками по ходу умножения матриц (1) на момент окончания процесса получаются все сочетания из n по m предметов с заданными весами.

Общая схема решения задачи условно строится следующим образом [6].

Первый этап. Запись данных в виде произведения матриц (1).

Второй этап. Умножение матриц на текущем шаге записывается в виде [6]

romm06.wmf,

k = 1, 2, ..., n. (3)

Третий этап. Новое обозначение данных и операций. Последовательное вычисление сумм весов наборов предметов и цены наборов, отсеивание неперспективных наборов по весу с использованием сортировки. Для допустимых по весу наборов на текущем шаге определяется максимум стоимости.

В новом обозначении окончательный результат шагов преобразования примет вид

При этом в (4) условно не учитываются отсеянные на последовательных шагах сочетания предметов с недопустимым весом.

Четвертый этап. Для сохранившихся допустимых сочетаний на выходе схемы определяется сочетание с максимальной стоимостью.

Пример решения задачи по изложенной схеме приведен в [6].

Временная сложность последовательного алгоритма решения задачи о рюкзаке

Аналогично (4), текущий шаг (3) преобразуется к виду

romm08.wmf

k = 1, 2, ..., n. (5)

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

Алгоритм (5) в рассматриваемом контексте выполняет генерацию сочетаний из k элементов по

romm09.wmf,

ℓ = 1, 2, ..., k.

romm07.wmf (4)

При этом коэффициент di(k–j) является не числом, а обозначением набора всех сочетаний из i элементов по j.

Процесс подсчета веса каждого сочетания предметов на k-м шаге (5) заключается в однократном сложении xk–1 с весом сочетания из k – 1 предметов по ℓ, подсчитанным на (k – 1)-м шаге. Попутно подсчитывается суммарная цена предметов каждого сочетания и сравнивается с текущим максимумом по ℓ и по предшествующим значениям k. В результате получается текущее значение максимума цены на рассматриваемом шаге. Временная сложность последовательного выполнения k-го шага (5) составит

romm10.wmf

или

romm11.wmf (6)

где τ – время двух бинарных сравнений чисел, просуммированное с временем бинарного арифметического сложения по весу и по цене. Суммирование обеих частей равенства (6) по всем k = 1, 2, ..., n даст оценку временной сложности последовательного детерминированного алгоритма подсчета веса и цены каждого допустимого сочетания с отсечением недопустимых весов, а также с последовательным формированием максимальной цены:

romm12.wmf (7)

С учетом (7) на выходе алгоритма определяется искомый максимум цены среди допустимых сочетаний предметов по весам за время

romm13.wmf (8)

Предложение 1. Детерминированный алгоритм на основе (5) в последовательной форме дает точное решение задачи о рюкзаке с временной сложностью, оцениваемой из (8).

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

Параллельные алгоритмы решения задачи о рюкзаке

1. Шаг (5) выполняется параллельно по всем ℓ = 1, 2, ..., k. Процесс подсчета веса каждого сочетания заключается в однократном сложении xk–1 с весом сочетания из k – 1 предметов по ℓ, подсчитанным на (k – 1)-м шаге. Попутно подсчитывается суммарная цена предметов каждого сочетания. Временная сложность параллельного выполнения k-го шага (5) оценивается временем однократного сложения в сочетании, включающем xk–1, если количество процессоров совпадает с числом тех сочетаний из (5), в которые xk–1 входит, что составляет

romm14.wmf

Для отсечения недопустимых весов применяется параллельная модификация сортировки подсчетом на основе матрицы сравнений [5] (для данного этапа рассматриваемого варианта алгоритма такая сортировка не является необходимой, но она окажется необходимой для параллельного нахождения максимальной цены допустимых сочетаний на k-м шаге; отсечение недопустимых весов можно было бы выполнять путем одновременного сравнения найденных весов сочетаний с заданной границей). Рассматриваемая сортировка для N элементов имеет временную сложность T(R) = τ, где количество процессоров romm15.wmf. От всех отсортированных элементов параллельно вычитается граница допустимого веса, тогда смена неотрицательного элемента преобразованной последовательности на положительный отделяет всю совокупность допустимых весов от недопустимых. Аналогично сортируются цены всех допустимых на шаге весов. Максимальная цена располагается в конце отсортированного массива. Она сравнивается с текущим максимумом, определяемым по совокупности всех предшествующих k – 1 шагов, который аналогично формируется на каждом шаге данного вида. В результате сохраняется единичный порядок времени шага, при этом в оценке R следует положить N = 2k–1 + 1. Отсюда временная сложность k-го шага составит

T(R) = O(1),

где romm16.wmf. Число шагов меняется от 1 до n, поэтому суммарная оценка временной сложности данного параллельного алгоритма примет вид

T(R) = nτ,

где τ из (6) увеличивается на время одного бинарного сравнения, а число процессоров берется максимальным по всем рассматриваемым шагам,

romm17.wmf

Таким образом, имеет место

Теорема 1. В рассматриваемой постановке задача о рюкзаке может быть точно решена с помощью детерминированного параллельного алгоритма на основе (5) и максимально параллельной сортировки с временной сложностью

T(2 2n–3) = nτ, (9)

где τ включает время двух бинарных алгебраических сложений и трех бинарных сравнений.

Помимо отмеченных выше отличий алгоритм теоремы 1 включает свойство параллелизма. Как и последовательный алгоритм, он конструктивно выполняет генерацию всех сочетаний из k предметов по ℓ для всех ℓ = 1, 2, ..., k и всех k = 1, 2, ..., n.

2. Целесообразно рассмотреть параллельный алгоритм на основе непосредственно формул (4). Для ℓ-й строки (4), содержащей сочетания из n по ℓ в количестве romm18.wmf, можно найти суммарный вес и суммарную цену каждого набора предметов параллельно по всем сочетаниям данной строки и одновременно по всем номерам строк ℓ = 1, 2, ..., n. При этом вес (и цену) предметов в каждом сочетании ℓ-й строки можно найти по схеме сдваивания за время (log2ℓ)τ на romm19.wmf процессорах. Всего в ℓ-й строке с учетом числа сочетаний потребуется romm20.wmf процессоров, вес и цену каждого набора в ℓ-й строке можно найти с временной сложностью

romm21.wmf (10)

Отбрасывание недопустимых сочетаний предметов выполняется путем одновременного сравнения найденных их весов с заданной границей, для чего заведомо достаточно число процессоров (10), при этом потребуется дополнительное время одного бинарного сравнения. Максимальное по всем ℓ время согласно (10) составит romm22.wmf, а требуемое по всем параллельно обрабатываемым строкам число процессоров

romm23.wmf

В итоге получится оценка:

romm24.wmf (11)

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

T2(R) = τ, (12)

где

romm25.wmf (13)

Поскольку romm26.wmf, то из (11)–(13) следует окончательная оценка временной сложности рассматриваемого параллельного алгоритма:

romm27.wmf (14)

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

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

Заключение

В работе представлен последовательный и два параллельных детерминированных алгоритма точного решения задачи об одномерном булевом рюкзаке. Все разновидности алгоритмов основаны на модификации формул Виета для выражения коэффициентов многочлена по его корням, которая используется для параллельной генерации сочетаний. Кроме тог, использована максимально параллельная разновидность сортировки подсчетом по матрице сравнений. От известных работ [1, 2] по параллельным алгоритмам решения задачи о рюкзаке предложенный метод отличается по построению, а также детерминированным точным решением задачи с временной сложностью O(n) либо O(log2n), в зависимости от варианта алгоритма.

Рецензенты::

Веселов Г.Е., д.т.н., директор Института компьютерных технологий и информационной безопасности, Инженерно-технологическая академия Южного федерального университета, г. Таганрог;

Карелин В.П., д.т.н., профессор, заведующий кафедрой прикладной математики и информационных технологий, Таганрогский институт управления и экономики, г. Таганрог.

Работа поступила в редакцию 01.04.2015.


Библиографическая ссылка

Ромм Я.Е., Назарьянц Е.Г. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РЕШЕНИЯ БУЛЕВОЙ ЗАДАЧИ О РЮКЗАКЕ НА ОСНОВЕ СОРТИРОВКИ И ВИДОИЗМЕНЕНИЯ ФОРМУЛ ВИЕТА // Фундаментальные исследования. – 2015. – № 2-12. – С. 2575-2580;
URL: http://www.fundamental-research.ru/ru/article/view?id=37525 (дата обращения: 12.11.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074