Содержание к диссертации
Введение
1 Введение 4
1.1 Задачи раскроя, упаковки и теории расписаний 4
1.1.1 Классификация задач раскроя 6
1.1.2 Классификация задач упаковки 7.
1.1.3 Задачи ортогональной упаковки 8
1.1.4 Задачи планирования при ограниченных ресурсах . 10
1.2 Размещения и графы 11
1.2.1 Граф размещения на плоскости 11
1.2.2 Граф многомерного размещения 13
1.3 Модели вычислений 14
1.4 Структура работы 17
2 Разделение размещения прямоугольников посредством угловых разрезов 19
2.1 Размещения, содержащие вырожденные прямоугольники . 21
2.2 Существование разделяющей последовательности разрезов 24
2.3 Нижняя оценка сложности 25
2.4 Построение разделяющей последовательности разрезов . 26
2.5 Обобщение для гофров 27
2.6 Трехмерный случай 29
3 Построение графа размещения 32
3.1 Плоский случай 32
3.1.1 Алгоритм построения графа размещения 32
3.1.2 Доказательство оптимальности 34
3.1.3 Обобщение для гофров 36
3.2 Случай с?-мерного пространства 37
3.2.1 Задача регионального поиска 37
3.2.2 Два метода построения графа размещения 38
4 Наклонная нумерация для размещений прямоугольников 41
4.1 Существование 42
4.2 Построение 44
4.2.1 Нижняя оценка сложности 45
4.2.2 Оптимальный алгоритм 45
4.2.3 Обоснование корректности 48
4.2.4 Обработка вырожденных случаев 51
4.3 Минимальный и максимальный номер прямоугольника . 52
4.4 Взаимнооднозначные соответствия 54
4.5 Обобщение для гофров 57
4.6 Обобіцение для пространств высших размерностей 58
4.6.1 Нумерация без повторений 58
4.6.2 Нумерация с повторениями 60
4.7 Задача об упаковке полосы 63
5 Заключение 66
- Задачи планирования при ограниченных ресурсах
- Существование разделяющей последовательности разрезов
- Два метода построения графа размещения
- Минимальный и максимальный номер прямоугольника
Введение к работе
Множество R невырожденных прямоугольников на плоскости, стороны которых параллельны осям координат, называется размещением, если прямоугольники из R попарно не перекрываются. Размещения естественным образом возникают в задачах прямоугольного раскроя, ортогональной упаковки, теории расписаний и т. д. Понятие размещения легко обобщается на пространства высших размерностей.
В данной диссертационной работе рассматривается ряд задач, возникающих в применении к размещениям, а именно: задача о разделении множества прямоугольников посредством угловых разрезов, задача о построении графа размещения, задача о построении наклонной нумерации, задача об упаковке в полосу прямоугольников с заданной наклонной нумерацией, а также обобщение этих задач на случай d-мерного пространства.
Задачи планирования при ограниченных ресурсах
Одна из классических задач теории расписаний заключается в следующем. Задан набор одномерных объектов - "заданий", а также множество (одномерных) контейнеров - "машин". Требуется найти оптимальное назначение, которое и задает процесс выполнения заданий. При этом длина объекта-задания соответствует, естественно, времени его выполнения.
На практике возникает естественное обобщение данной задачи: кроме времени, необходимого для выполнения некоторой работы, мы должны принимать во внимание объем различных ресурсов, задействованных при ее выполнении. Общий объем ресурсов каждого типа, имеющихся в нашем распоряжении, ограничен в любой момент времени.
Таким образом, теперь мы сопоставляем каждому заданию уже не отрезок - временной интервал, - а так называемый d-мерный бокс, или d-бокс, размер которого вдоль каждой из осей координат соответствует объему ресурсов, необходимых для его выполнения. Такие задачи известны в литературе как задачи планирования процесса при ограниченных ресурсах (resource-constrained project scheduling problems); результаты, полученные в данной области, а также ряд полезных ссылок, могут быть найдены в монографии Й. Вегларца (J. Weglarz) [44] и в статье Р. X. Меринга (R. Н. Mohring), А. С. Шульца (A. S. Schulz), Ф. Шторка (F. Stork) и М. Уетца (М. Uetz) [31].
Для исследования комбинаторных свойств размещений часто используются графы: например, так называемые графы размещения (placement graphs) [8, 50, 17, 58, 59], графы компонент (component graphs) [20, 18] и их дополнения - графы сравнимости (comparability graphs) [19].
При решении интересующих нас задач о размещениях нам неоднократно придется использовать графы размещений и их свойства, поэтому в данном параграфе мы остановимся на понятии графа размещения более подробно. Приведенная в данном параграфе терминология заимствована из [50].
Условимся для прямоугольника р обозначать его левую нижнюю вершину через Ар, левую верхнюю - через Вр, правую верхнюю - через Ср, правую нижнюю - через Dp. Зоной Z(p) прямоугольника р будем называть открытый левый нижний квадрант, построенный из точки Ср. Будем обозначать верхнюю границу зоны Z(p) через и(р), а правую ее границу через г(р). Соответственно, и(р) представляет собой горизонтальный луч с началом в точке Ср, направленный влево, а г(р) - верти Рис. 2: а) Прямоугольник р и его зона Z(p): и(р) и г(р) — соответственно верхняя и правая границы зоны. Ь) Размещение прямоугольников и соответствующий ему грае}) размещения.
Сопоставим размещению R ориентированный граф GR, не содержащий петель. Каждому прямоугольнику из R соответствует вершина графа: две различные вершины pus соединяются дугой (p,s), если р Г) Z(s) ф 0. Будем называть GR графом размещения (рис. 2Ь).
Граф размещения был предложен В. В. Бухваловой в 1986 г.; в 1988 г. А. И. Липовсцким были опубликованы работы [58, 59J, содержащая, в частности, доказательства некоторых свойств данного графа (см. ниже).
Заметим, что граф размещения может содержать 0(п2) дуг (рис. За), но может и не иметь дуг вообще (рис. ЗЬ). Оба примера, приведенных на рис. 3, были построены В. В. Бухваловой. Следующие три свойства были доказаны в [50, 58, 59].
Как следует из названия данной работы, основная ее цель заключается в разработке полиномиальных алгоритмов решения задач, возникающих в контексте размещений. Это означает, что мы должны прежде всего формализовать и зафиксировать модель вычислений, которая будет далее использоваться при анализе временной сложности алгоритмов.
В качестве базовой модели вычислений, которую мы намереваемся использовать, выберем так называемую машину с произвольным доступом к памяти, которую называют также равнодоступной адресной машиной (РАМ). "Классическая" модель РАМ, описанная в [2], предназначена для вычислений, выполняемых только над целыми числами. Мы же будем следовать модифицированному определению РАМ, введенному Ф. Пре-паратой (F. Preparata) и М. Шеймосом (М. Shamos) в [34]; в соответствии с их определением, каждая ячейка памяти РАМ способна хранить единственное целое число. Следующие операции считаются элементарными и обладают единичной стоимостью (т. е. выполняются за единицу времени): 1. Арифметические операции (+,-,х,/). 2. Сравнения двух вещественных чисел ( , , =, ф, , ) 3. Косвенная адресация памяти (допустимы только целочисленные адреса). 4. Дополнительные операции (только для тех приложений, где это необходимо): корни &-й степени, тригонометрические функции, exp, log (и вообще аналитические выражения).
Существование разделяющей последовательности разрезов
Существование для произвольного размещения прямоугольников разделяющей последовательности угловых разрезов представляет собой простое следствие результатов, полученных в [49. 58, 59]. Так как граф GR не содержит контуров, его вершины могут быть топологически отсортированы; следовательно (см. [50, 58, 59, 8]), Предположим, что для размещения R = {p }"=i прямоугольников, мы построили нумерацию IR; без ограничения общности будем полагать, что IR(P 1 ) = і, где 1 і п. Рассмотрим последовательность из (п— 1) угловых разрезов, построенных из вершин Ср(и, Срт, ..., Cp(n-i . Легко заметить, что указанная последовательность будет разделяющей для R. Будем говорить, что такая последовательность индуцирована нумерацией IR (рис. 11). Таким образом, мы доказали следующую теорему. Теорема 2.3. ДЛЯ любого размещения R прямоугольников существуют разделяющая последовательность угловых разрезов. Разделяющая последовательность угловых разрезов, индуцированная нумерацией, обладает следующим свойством: на очередном таге, применяя угловой разрез к множеству из к прямоугольников, мы отделяем ровно один из них от оставшихся (к — 1) прямоугольников. Рис. 11:
Пример разделяющей последовательности угловых разрезов для размещения R, индуцированной нумерацией Ід. Задача ПОСЛЕДОВАТЕЛЬНОСТЬ УГЛОВЫХ РАЗРЕЗОВ. Дано размещение R прямоугольников на плоскости. Требуется построить для R разделяющую последовательность угловых разрезов. Для получения нижней оценка сложности задачи ПОСЛЕДОВАТЕЛЬНОСТЬ УГЛОВЫХ РАЗРЕЗОВ мы воспользуемся сведением к ней задачи сортировки вещественных чисел. Доказательство. Сведем к задаче ПОСЛЕДОВАТЕЛЬНОСТЬ УГЛОВЫХ РАЗРЕЗОВ задачу сортировки п различных вещественных чисел xi, Х2, . , х„. Без ограничения будем полагать, что Х{ О, 1 г п. Для каждого Xj построим прямоугольник pi, вырожденный в вертикальный отрезок с концами (хг-, 0) и (х , ) (см. рис. 12); положим R = {pi}"=i Очевидно, что единственная существующая для R разделяющая последовательность угловых разрезов в точности соответствует упорядочению по возрастанию чисел хі, хг, ..., хп. Приведенное выше сведение может быть осуществлено за линейное время. Тем самым, требуемое утверждение доказано. Вернемся мысленно к доказательству существования разделяющей последовательности угловых разрезов для произвольного размещения прямоугольников R. Из выбранного нами способа доказательства немедленно вытекает, что для нахождения такой последовательности достаточно построить нумерацию IR и рассмотреть индуцированную ей последовательность угловых разрезов. С учетом сказанного выше заключаем, что для построения разделяющей последовательности угловых разрезов, соответствующей размещению R прямоугольников на плоскости, достаточно построить граф размещения GR
И выполнить топологическую сортировку его вершин. Однако временная сложность такого алгоритма с необходимостью составит по крайней мере 0(п2), поскольку граф GR может содержать 0(п2) ребер (а следовательно, в худшем случае для его построения потребуется не менее 0(п2) времени). Забегая вперед, скажем, что нумерация IR может быть построена за оптимальное время O(nlogn) при затратах памяти 0(п), где п — \Щ; оптимальный алгоритм ее построения будет изложен в главе 4.
Таким образом, мы можем сформулировать следующую теорему. Теорема 2.5. Для размещения R прямоугольников, разделяющая последовательность угловых разрезов может бить построена за оптимальное время 0(nlogn) при затратах памяти 0[п), где п = \R\. Тем не менее, метод построения разделяющей последовательности угловых разрезов при помощи графа размещения по-прежнему представляет интерес: выбирая различные способы топологического упорядочения его вершин, мы будем получать различные нумерации IR прямоугольников из R, и следовательно, различные последовательности угловых разрезов. С использованием графа мы сможем построить все возможные разделяющие последовательности угловых разрезов, индуцированные какой-либо из существующих нумераций IR. В главе 3 мы подробно рассмотрим задачу о построении графа размещения - как для плоского случая, так и для случая d-мерного пространства.
Два метода построения графа размещения
Эффективность второго подхода может быть улучшена за счет использования модифицированного дерева регионов, называемого также расслоенным деревом регионов (layered range tree) [28, 45, 6, 34]. Как сама задача регионального поиска, так и оба данных метода ее решения могут быть естественным образом обобщены на случай пространства произвольной размерности d 2. Оценки сложности для них приведены ниже в форме теорем. Теорема 3.2. kd-дерево для множества Р из п точек в d-мерном пространстве может быть построено за время 0(п log п) при затратах памяти 0(п). Обработка регионального запроса с использованием kd-дерева требует 0(v} d -\-к) времени, где к - число точек, выдаваемых при ответе на запрос. Теорема 3.3. Расслоенное дерево регионов для множества Р из п точек в d-мерном пространстве может быть построено за время 0(ralog_1n) при затратах памяти 0(пlog га). Обработка регионального запроса с использованием расслоенного дерева регионов требует 0(logd n+k) времени, где к - число точек, выдаваемых при ответе на запрос. 3.2.2 Два метода построения графа размещения Для размещения прямоугольников R = {г{}=1, рассмотрим множество Сд = {Сг.}"=1, содержащее правые верхние вершины всех прямоугольников из R. Построим точку С , положив Для того чтобы определить, в какие вершины ведут всевозможные дуги графа, выходящие из некоторой вершины г , достаточно выполнить для множества точек Сд региональный запрос, окно которого задается точками АГк и С .
Ответом на такой запрос будут в точности вершины Сг,п прямоугольников гт Є R, для которых х(АГк) х{СТт) и у(АГк) у{СГт), и, сверх того, вершина СГк в случае если прямоугольник г& невырожденный. Рис. 19: а) Размещение прямоугольников В. = {ГІ}7 . для точки С имеем: х(С ) — тахі ,; п{ж(Сп)} + 1 и у(С ) = тахі 7; га{х(Сг,:)} + 1. b) Окно запроса, соответствующего прямоугольнику Гк, задается точками АГк и С . Ответом на запрос будут точки СГт. СТ, и СГк; в граф размещения следует добавить дуги (rk,rm) и (rfc, п). Таким образом, задача построения графа размещения сводится к последовательной обработке п региональных запросов для множества Сд. Корректность полученного алгоритма обусловлена леммой 1.2. Принимая во внимание оценки для методов регионального поиска, приведенные в параграфе 3.2.1, и учитывая, что для представления графа размещения необходимо 0(п + \ER\) памяти, а для его построения - не менее 0(n\ogn + \ER\) времени, заключаем, что в пространстве размерности d 2 справедливы две следующие теоремы. Теорема 3.4. Пусть R - размещение d-боксов. Граф размещения GR может быть построен за время 0{п + \ER\) при затратах памяти 0(п + 1- ), где п = \R\, -с использованием kd-деревьев как вспомогательной структуры данных для выполнения региональных запросов.
Теорема 3.5. Пусть R - размещение d-боксов. Граф размещения GR может быть построен за время 0(п log п+ \ER\) при затратах памяти 0(пlog п+ \ER\), где п — \R\, - с использованием расслоенных региональных деревьев как вспомогательной структуры данных для выполнения региональных запросов. Пусть R = {ГІ}=1 - размещение прямоугольников на плоскости. Нумерацией без повторений, или просто нумерацией, прямоугольников из R назовем взаимнооднозначную функцию сопоставляющую каждому прямоугольнику из R его помер - натуральное число из диапазона от 1 до п. В случае если функция IR не является взаимнооднозначной, мы будем говорить о нумерации с повторениями. Будем называть нумерацию /д для размещения прямоугольников R наклонной [42], если для любой прямой / с неотрицательным тангенсом угла наклона номера прямоугольников, пересекаемых I, возрастают вдоль I (рис. 20). Рис. 20: Пример размещения прямоугольников и соответствующей ему наклонной нумерации. Прямая I последовательно пересекает прямоугольники с номерами 1, 3, 5, 7. Аналогично, нумерацию с повторениями 1ц для размещения прямоугольников R будем называть наклонной, если для любой прямой / с неотрицательным тангенсом угла наклона номера прямоугольников, пересекаемых I, образуют неубывающую последовательность (рис. 21). Рис. 21:
Пример размещения прямоугольников и соответствующей ему наклонной нумерации с повторениями. Прямая I последовательно пересекает прямоугольники с номерами 1, 2, 4, 4. В данной главе рассматриваются вопросы существования и эффективного построения наклонной нумерации для размещений прямоугольников на плоскости, а также возможности обобщения понятия наклонной нумерации на случай пространств высшей размерности. Очевидно, что наклонная нумерация с повторениями существует для любого размещения прямоугольников: для того чтобы получить такую нумерацию, достаточно присвоить всем прямоугольникам номер 1. В этом параграфе мы докажем более содержательное утверждение: для любого размещения прямоугольников существует наклонная нумерация без повторений. Как будет показано ниже, свойство, лежащее в основе определения наклонной нумерации, эквивалентно свойству нумерации, существование которой было доказано в теореме 1.2. Таким образом, для того чтобы доказать существование наклонной нумерации, достаточно показать эквивалентность двух этих свойств.
Минимальный и максимальный номер прямоугольника
Теперь проанализируем, каким образом мог быть добавлен в список прямоугольник 5. Очевидно, что s обрабатывался позднее, чем і, следовательно, s не мог быть добавлен в конец списка. Значит, s был вставлен в список перед некоторым прямоугольником v. Согласно правилам вставки, („)х {Bs)x {Dt)x. Отсюда следует, что (v)y {Dt)y: в противном случае t П Z(v) т 0, и в силу индукционного предположения t предшествует v в Lfc. Так как s был добавлен в Lk непосредственно перед v, мы получили бы, что t предшествует s в Lk, что противоречит нашему предположению.
Очевидно также, что v целиком лежит правее г(). Рассуждая аналогично для прямоугольника v, мы заключаем, что он также был добавлен в список перед некоторым прямоугольником, распо ложенным не выше прямой (AtDt) и правее г(), и так далее. Но перед добавлением w в L содержалось к прямоугольников (включая t), поэто му мы можем провести такое рассуждение только к —2 раза. В итоге мы получим цепочку из (к — 1) прямоугольников, первый из которых был помещен в конец списка непосредственно после і, а остальные поочеред но добавлялись в список друг за другом. Соответственно, вся цепочка будет расположена в списке после прямоугольника t. Завершает цепочку прямоугольник s. Таким образом, t предшествует s в L \ мы пришли к противоречию, что и доказывает свойство (28). В двух предыдущих параграфах мы предполагали, что все прямоугольники в R невырождены. Допустим теперь, что размещение R = {pi}f=\ может содержать вырожденные прямоугольники. Во-первых, затруднения могут возникнуть, если в R найдется прямоугольник р, вырожденный в горизонтальный отрезок, содержащий вершину Cq невырожденного прямоугольника q или прямоугольника q -вертикального отрезка. Эти случаи будут обрабатываться алгоритмом ComputeEmimeration некорректно.
Для того чтобы избежать подобных ситуаций, достаточно немного уменьшить высоту невырожденных прямоугольников, а также прямоугольников, вырожденных в вертикальные отрезки, за счет уменьшения на є у-координаты верхней стороны Определим є следующим образом. Рассмотрим множество точек X = Опустим верхние стороны невырожденных прямоугольников, а также верхние концы прямоугольников - вертикальных отрезков, на є. Таким образом мы избавимся от неблагоприятных случаев взаимного расположения прямоугольников, упомянутых выше (см. рис. 29а). С другой стороны, результирующему размещению R соответствует тот же граф, что и размещению R. Следовательно, построив при помощи алгоритма ComputeEnumeration нумерацию /д», мы незамедлительно получим и нумерацию IR. Вторая неблагоприятная ситуация возникает, если прямоугольник, вырожденный в вертикальный отрезок, лежит на правой границе г(р) зоны прямоугольника р, и Ср лежит выше Cq (рис. 29b). Соответственно, прямоугольник р обрабатывается раньше, чем q. В этом случае мы добавляем q в список согласно обычным правилам вставки, но статус на данном шаге не обновляется. Пусть R - размещение прямоугольников на плоскости. Рассмотрим всевозможные наклонные нумерации 1 , 7д, .... /Jf, которые могут быть построены для R. Рассмотрим произвольный прямоугольник р Є R; в каждой из нумераций PR, 1 j К, ему соответствует некоторый номер Nj(p), и эти номера, вообще говоря, могут быть различны. Таким образом, с каждым прямоугольником р Є R мы можем связать два натуральных числа из диапазона от 1 до п = \R\ - соответственно минимальный и максимальный номера Nmm(p) и Nmax(p), которые р может получить в какой-либо наклонной нумерации: Легко понять, что для вычисления Nmin(p) и Nmax(p) нет необходимости в построении всех нумераций IR, IR, ..., IR. Величина Nmm(p) в точности равна числу вершин графа размещения GR, из которых может быть достигнута вершина р, а для того чтобы вычислить значение Nmax(p), достаточно вычесть из п число вершин, в которые существует путь из р в графе GR. Для произвольного орграфа G и для произвольной его вершины v, условимся обозначать через AQ(V) число вершин, достижимых из v. Кроме того, обозначим через G орграф, полученный из G реверсированием всех его ребер. В новых обозначениях получаем: Nmm(p) — AG-(p) и Nmax(p) = Легко понять, что для вычисления величины AG(V) может быть использован алгоритм поиска в глубину (или же в ширину) в графе G, стартующий из вершины v. Время работы такого алгоритма составит, очевидно, 0(\V\ + \Е\), где V - число вершин графа G, a \Е\ - число его ребер (см. [64, 68]). Итак, построив граф размещения GR - например, при помощи оптимального алгоритма, изложенного в главе 3, - мы сможем затем вычислить JV""" и iVmax за дополнительное время 0(п + \ER\). Таким образом, мы доказали следующую теорему. Теорема 4.4. Пусть R - размещение прямоугольников на плоскости.
Для произвольного прямоугольника р Є R, значения Nmm(p) и Nma,x(p) могут быть вычислены, за время 0(п + \Ед\) при затратах на предобработку O(nlogn + \ER\) времени и 0(п + \Ец\) памяти, где п = \R\. Под предобработкой здесь подразумевается построение графа размещения GR.
Похожие диссертации на Полиномиальные алгоритмы для решения комбинаторных задач размещений прямоугольников
