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

ПРИНЦИПЫ ПОСТРОЕНИЯ И ОСОБЕННОСТИ М.В. Ульянов, доктор технических наук, профессор кафедры Прикладная математика и моделирование систем Московского государственного университета печати (МГУП), Адрес: 127550, Москва, ул. Прянишникова, 2а, кафедра Прикладная математика и моделирование систем, Ульянов М.В. Тел: 8 916 589 9404. E mail: muljanov@mail.ru О.А. Наумова, студентка кафедры Персональная электроника Московского государственного университета приборостроения и информатики (МГУПИ), E mail: helga_13_07@mail.ru В статье рассмотрены базовые алгоритмы точного решения задачи одномерной оп тимальной по стоимости упаковки: рекурсивный и табличный. На основе их рациональ ного совмещения предлагаются комбинированный и волновой алгоритмы, обладающие лучшими ресурсными характеристиками. Указаны особенности их применения и разли чия в ресурсных требованиях.

Ключевые слова: Задача оптимальной упаковки;

комбинированный алгоритм;

волновой алгоритм;

ресурсная эффективность.

Введение ние повышения временной эффективности её реше ния в настоящее время остаётся актуальным.

ачиная с конца 50 х годов XX века, когда Точный классический алгоритм Беллмана для Р. Беллман предложил и обосновал идеи задачи одномерной упаковки может быть реализо Нметода динамического программирования, ван двумя принципиально разными алгоритмами:

задача оптимальной по стоимости одномерной упа табличным алгоритмом, опирающимся на вы ковки привлекает внимание программистов и уче числение и хранение векторов оптимальной ных, занимающихся разработкой и анализом алго упаковки для всех последовательных целочис ритмов. Именно этой задачей открывается ряд иллю ленных значений объема;

стративных примеров в классической книге рекурсивным алгоритмом, непосредственно Р. Беллмана и Р. Дрейфуса Прикладные задачи дина реализующим основное функциональное мического программирования [1]. Повышенный ин уравнение Белламна.

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

БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Математическая постановка задачи одномерной упаковки При значительном разбросе значений vi оценка Постановка задачи: пусть задано множество по произведению значительно лучше, чем (m +1)n, но всё равно неприемлема для практически значи мых постановок задачи упаковки.

Отметим, в этой связи, что рассматриваемая за где каждый элемент yi обладает целочисленным дача является NP трудной [1], и для неё в общем ви линейным размером - vi, или лобъёмом в обще де отсутствуют сегодня полиномиальные по n точ принятых терминах задачи упаковки, и ценовой ха ные алгоритмы решения. Это приводит к необходи рактеристикой - ci, которая содержательно отра мости использования более эффективных точных жает практически значимые предпочтения для за методов решения задачи одномерной оптимальной грузки объектов данного типа. Также целочислен упаковки, существенно сокращающих полный пе ным значением задан основной объём упаковки V. ребор, одним из которых является метод динамиче В классической постановке элементы yi называют ского программирования.

ся типами грузов. Для описания количества загру жаемых в объем V элементов yi введём в рассмотре Функциональное уравнение Беллмана ние характеристический вектор:

Опираясь на терминологию метода динамичес, кого программирования, будем считать, что в рас сматриваемой задаче распределяемым ресурсом яв где xi - неотрицательное целое. ляется объём упаковки V, а максимизизация дохо да, заданного линейным функционалом Pn(x) про Значение компонента вектора xi = k соответ изводится путём распределения ограниченного ре ствует загрузке k элементов типа yi в объём V. Таким сурса V между грузами указанных типов. Поскольку образом, описание некоторой упаковки грузов целевой функционал Pn(x) обладает свойством ад представляет собой точку в n мерном целочислен дитивности, то метод динамического программи ном пространстве Ezn. Среди всех возможных упа рования применим, и основное функциональное ковок объема V грузами из Y должна существовать уравнение Беллмана имеет вид [1] по крайней мере одна упаковка, максимизирующая суммарную стоимость, что приводит к постановке задачи как задачи максимизации линейного функ ционала [1]: (2) Таким образом, метод предусматривает последо вательное решение одномерных задач целочислен (1) ной оптимизации с использованием информации об оптимальной упаковке объёма v предыдущими типа Содержательно ограничение в (1) означает, что ми грузов. Решением поставленной задачи является суммарный объём, занимаемый грузами всех типов значение fn(V) и соответствующий вектор оптималь в количествах, указанных компонентами характери ной упаковки. Поскольку значения f1(v) могут быть стического вектора x, не должен превышать общего элементарно вычислены на основе (2), то в дальней объёма упаковки. Поскольку и целевая функция шем будет рассматриваться следующее основное и ограничение линейны, а значения xi - неотрица функциональное уравнение для задачи одномерной тельные целые числа, то задача (1) является задачей оптимальной упаковки, записанное в виде рекур линейного целочисленного программирования. рентного соотношения, определяющего рекурсивно Оценку вычислительной сложности решения заданную функцию fm(v) [2] данной задачи методом полного перебора можно получить, если рассматривать прямоугольный па раллелепипед в пространстве Ezn, размеры сторон которого определяются типами грузов. Это приво дит к верхней оценке количества точек перебора (3) в виде [2] 28 БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Рекурсивный алгоритм этом чем дерево шире, а глубина рекурсии больше, решения задачи упаковки тем выше вероятность повторных вычислений.

В общем случае трудоёмкость этого алгоритма Рекурсивная реализация функционального урав асимптотически определяется биномиальными ко нения Беллмана для задачи одномерной упаковки эффициентами при специальной параметризации достаточно проста. Рекурсивный алгоритм, напря [1], что приводит ряда входов к значительному вре мую реализующий рекуррентное соотношение (3) - мени получения решения.

алгоритм A1, останавливается при значении m =1, когда значение функции f1(v) может быть вычислено непосредственно. Рекурсия при m 2 выполняется Табличный алгоритм решения задачи упаковки для вычисления оптимальной по стоимости упаков ки текущего объёма v грузами типа m совместно Рассмотрим другой алгоритм точного решения с грузами предыдущих mЦ1 типов. этой задачи методом динамического программиро Рассмотрим пример решения задачи одномерной вания - табличный алгоритм A2, позволяющий по упаковки с использованием данного алгоритма - лучить оптимальное решение не только для задан нас интересует порождённое дерево рекурсии. ного объёма V, но и набор оптимальных решений Пусть необходимо решить задачу для трёх типов для всех промежуточных дискретных значений это грузов при общем объёме упаковки V = 10. Инфор го объёма. Обозначим вектор оптимальной упаков Ц - мация об объёмах vi и стоимостях ci для типов гру ки для объёма v элементами yi, i =1,m, m n, через m зов приведена в табл. 1. xv, а через fm(v) стоимость оптимальной упаковки в этом объёме. В силу принципа оптимальности [1] Таблица Описание типов грузов i vi ci а порядок предъявления элементов не является су щественным. Результатом решения задачи является 1 2 набор оптимальных значений целевой функции 2 3 fn(v) и соответствующих векторов оптимальной упа n ковки xv для всех объемов v от 0 до V исходными 3 4 элементами (грузами различных типов) из множес тва Y. Отметим, что поскольку табличный способ Решением поставленной задачи будет значение позволяет получить оптимальные решения для всех функции Беллмана f3(10), при этом алгоритм по промежуточных объемов упаковки, то эту инфор рождает дерево рекурсии, показанное на рис. 1. мацию можно использовать, например, для иссле дования чувствительности целевой функции fn(v) F3(10) по изменению объёма упаковки. Заметим также, что рекурсивный вызов в функциональном уравне x3 = x3 = 1 x3 = нии (3) в табличном алгоритме есть не что иное, как F2(2) обращение к предыдущей таблице оптимальной F2(10) F2(6) упаковки для определённого значения объёма.

Пример формирования таблицы оптимальной x2 = упаковки для исходных данных, приведённых в x2 = 0 x2 = 0 x2 = x2 = табл. 1, представлен в табл. 2.

x2 = 1 x2 = 2 x2 = Очевидным недостатком данного алгоритма яв ляются пустые вычисления в тех строках табли F1(10) F1(7) F1(4) F1(1) F1(6) F1(3) F1(0) F1(2) цы, которые не будут задействованы в будущем. Та ким образом, алгоритм выполняет лишние вычис Рис. 1. Дерево рекурсии, порождаемое рекурсивным ления, объём которых может быть значительным.

алгоритмом упаковки. Явная зависимость трудоёмкости данного алгорит ма от объёма упаковки приводит к тому, что для Характерным недостатком данного алгоритма больших значений объём лишних вычислений воз является повторное вычисление значений функции растает.

fm(v) в различных фрагментах дерева рекурсии. При БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Таблица 2 Предположим, что табличным алгоритмом на Таблица оптимальной упаковки ходится оптимальное решение для упаковки первы ми (в порядке предъявления) m типами грузов, при v x1 f1(v) v x1 x2 f2(v) v x1 x2 x3 f3(v) чем m 1, при этом для остальных nЦm типов зада ча решается рекурсивным алгоритмом. В листьях 1 0 0 1 0 0 0 1 0 0 0 порождённого дерева рекурсии на уровне nЦm+ 2 1 3 2 1 0 3 2 1 0 0 происходит копирование вектора оптимальной упаковки, полученного табличным алгоритмом.

3 1 3 3 0 1 5 3 0 1 0 Это приводит к необходимости модификации ре 4 2 6 4 2 0 6 4 0 0 1 курсивного алгоритма. Этот модифицированный алгоритм, обозначим его через A1M, отличается от 5 2 6 5 1 1 8 5 1 1 0 алгоритма A1 фрагментом останова рекурсии, в ко 6 3 9 6 0 2 10 6 0 2 0 тором происходит копирование строки результатов табличного алгоритма.

7 3 9 7 2 1 11 7 0 1 1 Параметризуем исходные данные числом грузов 8 4 12 8 1 2 13 8 0 0 2 среднего объёма, размещаемых в общем объёме 9 4 12 9 0 3 15 9 0 3 0 15 упаковки. Обозначим этот параметр через k. По скольку на основе исходных данных значения 10 5 15 10 2 2 16 10 0 2 1 (n, V, k) известны, то можно построить функцию g(m), значением которой является совокупная тру доёмкость комбинированного алгоритма, при этом Комбинированный алгоритм предполагается, что значения n, V, k, определяемые входом, фиксированы:

Совместное рассмотрение недостатков рекур сивного и табличного алгоритмов позволяет сде лать вывод о том, что в крайних случаях, например, при значительном объёме упаковки и больших зна Оптимальное значение может быть найдено как чениях объёмов грузов рекурсия будет существенно эффективнее табличных расчётов, а при малых (4) объёмах грузов мы будем наблюдать противопо ложную ситуации. Таким образом, мы можем гово Отметим, что значение m* =m*(n, V, k). Посколь рить, что эти два классических алгоритма являются ку значение m является целым числом, то m* может в определённом смысле комплементарными - они быть найдено простым перебором значений функ дополняют друг друга, обладая противоположным ции g(m) при 1 m nЦ1. Тогда трудоёмкость комби поведением функции трудоёмкости [3]. Эта особен нированного алгоритма, назовём его AC, составит ность позволяет создать комбинированный алго ритм, использующий табличный расчёт и рекурсию в их рациональных диапазонах.

Комбинированное алгоритмическое решение со стоит в выборе одного из двух алгоритмов, что может В общем случае возникает задача построения быть реализовано при заданных значениях n, V, k, на комбинированного алгоритмического решения - основе сравнения их трудоёмкостей [3]. При опреде рационального выбора одного из трёх алгоритмов лённых условиях, зависящих от исходных данных, на основе анализа текущего входа. Мы сравниваем более рациональным является построение комбини между собой рекурсивный, табличный и комбини рованного алгоритма, основной идеей которого рованный алгоритмы - A1, A2, AC. Критерием вы является предвычисление оптимальных упаковок бора является минимум значения функций тру для некоторого числа типов грузов табличным алго доёмкости. Понимая под аргументом оптимизации ритмом и дальнейшее решение задачи рекурсивным индекс алгоритма, и фиксируя значения (n, V, k), алгоритмом с сокращённым числом типов грузов. определённые текущим входом, можно записать Каков оптимальный по трудоемкости порог, т.е. оп тимальное число типов грузов обрабатываемых табличным алгоритмом? Ответ на этот вопрос мож (5) но получить на основе следующих рассуждений.

30 БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ при этом возможны три следующих случая, возник формула нивелирует порядок предъявления типов новение которых определяется текущим входом ал грузов, тем не менее, порожденный фрагмент дере горитма: ва рекурсии в комбинированном алгоритме будет 1. Случай 1 - меньше (в смысле общего числа вершин), если ис ходные типы грузов будут первоначально отсорти рованы по убыванию их объёмов. Такой приём позволяет несколько сократить ширину уровней В этом случае рекурсивный алгоритм A1 обеспе дерева рекурсии, порожденного рекурсивным алго чивает минимальную трудоёмкость, и комбинации ритмом, и получить лучшие временные характерис с табличным алгоритмом не требуется. тики для рекурсивного и комбинированного алго 2. Случай 2 - ритмов.

Волновой алгоритм В этом случае табличный алгоритм A2 имеет ми В основе волнового алгоритма также лежит идея нимальную трудоёмкость для данного входа, и ком как эффективного сочетания достоинств обоих бинации с рекурсивным алгоритмом не требуется. классических решений, так и их комплементарнос 3. Случай 3 - ти. Главное отличие волнового алгоритма от комби нированного - это отсутствие предвычисления по рога переключения. Ни до, ни во время поиска ре шения мы не анализируем функции трудоёмкости В этом случае рациональным является примене табличного и рекурсивного алгоритмов. Вместо ние комбинированного алгоритма AC с порогом пе этого, после расчёта упаковки очередным грузом, реключения равным m*. При этом на первом этапе значение некоторого параметра определяет, каким табличный алгоритм получает таблицу оптималь из алгоритмов лучше обрабатывать последующий Ц - ной упаковки заданного объёма грузами типов 1,m* тип грузов.

, а рекурсивный алгоритм на втором этапе, порожда Так как табличный алгоритм на каждом шаге ет дерево рекурсии от груза с номером n до груза вычисляет оптимальную упаковку для всех дис с номером m*, останавливает рекурсию на уровне кретных значений объёма от 0 до V, то его разумно nЦm*+1, копирует результаты табличного алгорит использовать, когда следующий шаг рекурсии будет ма в свою структуру данных, и цепочкой рекурсив порождать значительное число листьев с различны ных возвратов получает вектор оптимальной упа ми значениями объёма упаковки. К тому же эффек ковки и значение целевого функционала для исход тивность рекурсии при обработке каждого последу ной задачи. ющего груза в общем случае падает, т.к. возрастает Программная реализация комбинированного число вершин, имеющих одинаковый аргумент це алгоритма содержит управляющий фрагмент, кото левой функции. Исходя из этого, на первом этапе рый по параметрам текущего входа решаемой зада волнового алгоритма управление передаётся рекур чи (n, V, k) определяет значение оптимального по сии. Но в отличие от комбинированного и рекур рога переключения m* по формуле (4) и запускает сивного алгоритма в чистом виде, здесь использует табличный, а затем рекурсивный алгоритмы, - это ся иная структура данных. Мы разворачиваем ре реализация статически адаптивного подхода к со курсию в таблицу хранения рекурсивных обраще зданию комбинированных алгоритмов. ний. Что это означает? Порождение очередной вер Совокупно программная реализация, представ шины дерева рекурсии обрабатывается как созда ляющая собой комбинированное алгоритмическое ние строки таблицы с номером, соответствующим решение будет содержать табличный, рекурсивный значению оставшегося объёма упаковки, и записью и комбинированный алгоритмы, а также управляю дополнительной информации, позволяющей орга щий модуль, который выбирает в соответствии низовать быстрые вычисления на последнем этапе с формулой (5) алгоритм, наиболее рациональный волны обратных расчётов, эквивалентном цепочке для текущего входа. рекурсивных возвратов. Для следующего типа груза Дополнительно отметим, что хотя окончатель создаётся новая таблица, при этом рекурсивные ный результат, получаемый как табличным, так вызовы, порождающие цепочку таблиц, будут про и рекурсивным алгоритмами, не зависит от по должаться до передачи управления табличному ал рядка предъявления типов грузов, а теоретическая горитму. Порог переключения между алгоритмами БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г. МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ определяется динамически, исходя из условия ра Как и в случае комбинированного алгоритма, ционального продолжения развёртывания рекур степень использования рекурсивного и табличного сии. После обработки очередного уровня рекурсии, алгоритмов зависит от входных данных с той лишь т.е. создания таблицы для соответствующего типа разницей, что для всех входов волнового алгоритма груза, подсчитывается число заполненных строк те обязательно будет построена таблица хранения ре кущей структуры данных - таблицы хранения ре курсивных обращений хотя бы для первого типа курсивных обращений. Если число обращений до грузов. Таким образом, остаётся два варианта пове стигло значения (V+1)/2, то мы предполагаем, что дения волнового алгоритма:

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

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

Первый этап алгоритма - волна порождения це почки таблиц, эквивалентных рекурсии по типам грузов. Первый этап продолжается до достижения Сравнение комбинированного рационального порога переключения на табличный и волнового алгоритмов алгоритм, т.е. до достижения половины заполнен ных строк таблицы хранения рекурсивных обраще Рациональное совмещение рекурсивного и таб ний. Второй этап - классический табличный алго личного алгоритмов решения задачи одномерной ритм выполняется для оставшихся типов грузов. упаковки - общий принцип построения волново В точке переключения выполняется копирование го и комбинированного алгоритмов. Этот прин из структуры данных табличного алгоритма в таб цип во многом обусловливает и схожесть структур лицу хранения рекурсивных обращений. Третий, этих алгоритмов. Так какой же из методов пред заключительный этап - волна обратных расчётов, почтительнее использовать для получения быст формирующая на последнем шаге решение постав рого решения? Ответ на этот вопрос не является ленной задачи упаковки в первой порождённой вполне очевидным и зависит от аппаратных воз таблице рекурсии. можностей.

Рис. 2. Схема волнового алгоритма упаковки 32 БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г.

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Если определяющим фактором является время Заключение получения точного решения, то выбор за волновым алгоритмом. Он обеспечивает более быстрое реше Таким образом, в статье предложены два алго ние за счёт: ритма решения задачи одномерной оптимальной отсутствия модуля предвычисления порога по стоимости упаковки, основанные на рациональ переключения;

ном совмещении классических алгоритмов её ре отсутствия повторных расчётов целевой шения - рекурсивном и табличном.

функции с одинаковым аргументом для вер Комбинированный алгоритм использует резуль шин дерева рекурсии разных уровней;

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

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

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

Литература 1. Беллман Р., Дрейфус Р. Прикладные задачи динамического программирования: Пер. с англ. - М.: Наука, 1965, - 457 с.

2. Головешкин В. А., Ульянов М. В. Теория рекурсии для программистов. - М.: Издательство Наука ФИЗМАТЛИТ, 2006. - 296 с.

3. Ульянов М. В., Гурин Ф. Е., Исаков А. C., Бударагин В. Е. Сравнительный анализ табличного и рекурсивного алгоритмов точного решения задачи одномерной упаковки // Exponenta Pro Математика в приложениях. 2004.

№2(6). С. 64Ц70.

Издательство Техносфера пополнило серию Мир программирования новой книгой Виктора Александровича Сердюка, преподавателя кафедры управления разработкой программного обеспечения ГУ ВШЭ и генерального директора ЗАО ДиалогНаука Новое в защите от взлома корпоративных систем.

БИЗНЕС-ИНФОРМАТИКА №2(08)Ц2009 г.    Книги, научные публикации