Задача одномерной упаковки. Рассматривается традиционная постановка задачи о рюкзаке: имеется набор из n предметов, каждый предмет имеет вес и цену , требуется собрать набор с максимальной ценой таким образом, чтобы он имел вес не больше w, где w – вместимость рюкзака [1]. Формальная запись постановки задачи:
Алгоритм выборки всех возможных сочетаний слагаемых для решения задачи о рюкзаке
Построение алгоритма опирается на структуру матричной формулы восстановления коэффициентов многочлена по его корням с точностью до выполнения операций, при этом непосредственно в исходном виде арифметические операции не выполняются. Коэффициенты многочлена выражаются через его корни в виде [1]:
Левые части равенств (1) и (2) одинаковы, соответственно равны правые части. В правых частях (2) – всевозможные сочетания корней, которые не повторяются, поэтому формула (1) порождает алгоритм генерации всех возможных сочетаний, если не принимать во внимание операции умножения и сложения. Если веса предметов в задаче о рюкзаке интерпретировать как корни многочлена, то из (1) следуют все возможные сочетания весов из n по m. В этой интерпретации произведение всех весов в сочетании заменяется на их сумму и не принимается во внимание знак слагаемых. Аналогично, в (2) следует заменить знак умножения на знак сложения, знак суммы – на любой знак, обозначающий сочетание элементов (в таком качестве ниже выбрано логическое «ИЛИ»). С этими поправками по ходу умножения матриц (1) на момент окончания процесса получаются все сочетания из n по m предметов с заданными весами.
Общая схема решения задачи условно строится следующим образом [1].
Первый этап. Запись данных в виде произведения матриц (1).
Правило построения матриц из (1):
- Последний множитель – частный случай матрицы – вектор, у которого верхняя координата равна единице, нижняя – первый выбранный предмет.
- Матрицы в (1) прямоугольные: строк в матрице справа столько, сколько в соседней слева от нее матрице столбцов, при этом в каждой матрице число строк на единицу больше, чем число столбцов.
- Ниже диагонали из единиц (непосредственно под диагональю) поддиагональ состоит из одного предмета (из одного и только одного корня многочлена).
- Количество матриц соответствует количеству предметов (n корней) в условии задачи, так что на каждый предмет приходится одна матрица.
Второй этап. Умножение матриц на текущем шаге записывается в виде:
Третий этап. Новое обозначение данных и операций. Последовательное вычисление сумм весов наборов предметов и цены наборов, отсеивание неперспективных наборов по весу с использованием сортировки. Используется устойчивая сортировка подсчетом одномерного массива (ниже – сортировка) на основе матрицы сравнений. Она сохраняет порядок равных элементов, является адресной с обратной адресацией на основе явного задания взаимно однозначного соответствия входных и выходных индексов. Сортировка будет применяться для максимально параллельного упорядочения и выбора оптимального набора предметов за минимальное время, при этом временная сложность ее [1]. Для допустимых по весу наборов на текущем шаге определяется максимум стоимости.
В новом обозначении окончательный результат шагов преобразования примет вид:
При этом в (4) условно не учитываются отсеянные на последовательных шагах сочетания предметов с недопустимым весом.
Четвертый этап. Для сохранившихся допустимых сочетаний на выходе схемы определяется сочетание с максимальной стоимостью. Этап выполняется с использованием максимально параллельной сортировки по стоимости за время Ο(1).
В итоге оцениваемая на модели неветвящихся параллельных программ временная сложность одномерной параллельной упаковки определяется из соотношения:
При одновременной обработке всех вариантов сочетаний оценка может быть формально улучшена [2].
Задача двумерной упаковки. Рассматривается задача упаковки прямоугольников в квадрант (2DAreaPackingProblem, 2DAP)) [3]. Дано прямоугольных предметов с размерами , требуется найти упаковку в положительном квадранте с минимальной площадью окаймляющего прямоугольника. При этом повороты запрещены, стороны прямоугольников параллельны осям координат.
Формальная запись:
В алгоритме двумерной упаковки [3] используется аналог алгоритма одномерной упаковки [1], приведенный выше для генерации всех сочетаний из n по m, но с учетом некоторых замен. Знак умножения заменяется на знак «⊗», который понимается как перечисление элементов сочетания (без выполнения каких бы-то ни было операций), знак суммы – на любой знак, обозначающий задание порядка сочетаний, в таком качестве ниже выбран знак «ν». При этом в одномерной упаковке были предмет (имеющие один параметр), а в двумерной упаковке – прямоугольники, имеющие два параметра. Прямоугольники можно интерпретировать как взаимно однозначно сопоставленные комплексным корням многочлена – ширина основания, . В данной трактовке (2) означает представление всех сочетаний из прямоугольников, положение которых в декартовых координатах задано и не меняется. Поскольку (1) алгоритмически эквивалентно (2), то формула (1) задает алгоритм генерации всех возможных сочетаний прямоугольников из n по m в виде
(5)
В силу совпадения левых частей (1), (2) результатом преобразования (5) окажется теоретико-множественный аналог соотношения (5), который можно представить в виде:
Таким образом, (5) задает алгоритм генерации всех сочетаний прямоугольников из по вида (6), которые не зависят от порядка элементов.
Сортировка применяется для максимально параллельного упорядочения элементов сочетаний и выбора оптимальной упаковки за минимальное время, при этом сохраняется ее временная сложность . Видоизменения формул Виета используются для генерации всевозможных сочетаний прямоугольников из заданного конечного множества, порядок вхождения в сочетание прямоугольников не учитывается. Предложенный алгоритм является параллельным и имеет близкую к линейной временную сложность. При любом m<n алгоритм анализирует одновременно все сочетаний, содержит последовательных шагов. Локально оптимальная упаковка достигается в каждом отдельно взятом сочетании прямоугольников на выходе шага параллельного алгоритма. Временная сложность одной из разновидностей алгоритма [3] представлена соотношением
Глобально оптимальная упаковка получается при m = n, в этом случае оценка имеет вид , где количество процессоров .
Выводы. Таким образом, временная сложность детерминированного параллельного алгоритма одномерной упаковки является линейной, временная сложность детерминированного параллельного алгоритма двумерной упаковки имеет вид близкий к линейному. Эти полиномиальные оценки достигаются за счет использования экспоненциального количества процессоров.
Список литературы:
- Ромм Я.Е., Назарьянц Е.Г. Детерминированный параллельный алгоритм решения задачи об одномерном булевом рюкзаке на основе сортировки и видоизменения формул Виета / ТИ имени А.П. Чехова (филиал) ФГБОУ ВПО «РГЭУ (РИНХ)». – Таганрог, 2015. – С. 45. Деп. в ВИНИТИ 18.02.2015, № 32-В2015.
- Ромм Я.Е., Назарьянц Е.Г. Параллельные алгоритмы решения булевой задачи о рюкзаке на основе сортировки и видоизменения формул Виета // Фундаментальные исследования. – № 2. – (часть 12) 2015. – С. 2575-2580.
- Ромм Я.Е., Назарьянц Е.Г. Параллельный детерминированный алгоритм двумерной упаковки на основе сортировки и видоизменения формул Виета / ТИ имени А.П. Чехова (филиал) ФГБОУ ВО «РГЭУ (РИНХ)». – Таганрог, 2016. – С. 39. Деп. в ВИНИТИ 14.04.2016, № 61-В2016.[schema type=»book» name=»ОДНОМЕРНАЯ И ДВУМЕРНАЯ ПАРАЛЛЕЛЬНАЯ УПАКОВКА» description=»Представлены параллельные алгоритмы решения задач одномерной и двумерной упаковки, которые основаны на видоизменении формул Виета для выражения коэффициентов многочлена по его корням с целью генерации сочетаний. Кроме того используется максимально параллельная форма сортировки подсчетом. Алгоритмы являются детерминированными, их временная сложность на модели неветвящихся параллельных программ имеет полиномиальную оценку за счет роста количества процессоров.» author=»Ромм Яков Евсеевич, Назарьянц Елена Геворговна» publisher=»Басаранович Екатерина» pubdate=»2016-12-14″ edition=»euroasia-science_6(27)_23.06.2016″ ebook=»yes» ]