Содержание к диссертации
Введение
1. Задача о ширине графа и ее обобщения 7
1.1. Постановки задач 7
1.2. Приложения задач 9
1.3. Обзор результатов 14
1.4. Анализ L-структуры задачи о ширине графа 19
2. Полиномиально разрешимые случаи задачи о ширине графа 28
2.1. Вспомогательные утверждения 28
2.2. Прямоугольные решетки с угловыми выемками 35
2.3. Решетки с диагональными ребрами 85
3. Задача проектирования изделий сложной структуры 89
3.1. Математические модели 89
3.2. Генетический алгоритм для задачи проектирования изделий сложной структуры 92
3.3. Программное обеспечение 97
3.4. Результаты расчетов 101
Заключение 107
Введение к работе
Диссертация посвящена исследованию известной задачи комбинаторной оптимизации -- задачи о ширине графах некоторых вариантов более общей задали проектирования изделий сложной структури
Графы традиционно и успешно применяются для моделирования и анализа различных систем, имеющих сложную сетевую структуру, например, транспортных, информационно-вычислительных сетей, систем взаимоотношений в коллективе и т.д. [6,27].
Широко распространенной моделью реальных систем является структурная схема системы [26]. Она содержит информацию об элементах системы, о связях между элементами, а также о связях системы с окружающей средой. Абстрагируясь от содержательной стороны структурной схемы и выявляя ее математическую сущность, мы получаем схему, в которой содержится только информация о наличии элементов и связей между ними. Эта схема может быть представлена графом, вершины которого соответствуют элементам системы, а ребра - наличию связей между элементами. Таким образом, графы являются адекватными и наглядными математическими моделями многих реальных систем.
В задаче о ширине графа требуется пронумеровать вершины графа последовательными натуральными числами так, чтобы минимизировать максимальное значение модуля разности номеров смежных вершин. Она интересна как с теоретической, так и с практической точки зрения, поскольку имеет ряд важных приложений в различных областях, таких как решение систем линейных уравнений, проектирование интегральных схем и других объектов. Задача о ширине графа относится к задачам оптимальной нумерации. Общим для всех задач данного класса является вид допустимого решения - нумерация вершин, а отличаются они друг от друга лишь оптимизируемой функцией. Этот класс включает, в частности, задачу оптимального линейного упорядочения, которой посвящено значительное число работ [28,66,68,77], а также ряд других задач [3,30,60,78]. Обзор результатов по задачам нумерации можно най-
ти в (39,63].
Задачи оптимальной нумерации, в свою очередь, можно отнести к более широкому классу задач размещения графа на линии. Они изучаются в работах [9,10,19,79].
Приведем содержательную постановку задачи проектирования изделий сложной структуры. Предположим, что проектируемое изделие состоит из конечного числа образующих элементов. Структура изделия задается графом, вершины которого соответствуют возможным местам размещения элементов, а ребро между парой вершин указывает на взаимосвязь данных позиций. Элементы изделия характеризуются фиксированным числом параметров, которые могут быть выражены в числовых величинах. Если пара элементов оказывается размещенной во взаимосвязанных позициях, то могут накладываться ограничения на разность значений их параметров. Требуется расположить в вершинах графа элементы изделия (по одному в каждой вершине) таким образом, чтобы полученное размещение являлось оптимальным в смысле одного или нескольких критериев, Как правило, для каждого параметра известен "вес", поэтому в качестве целевой функции может быть выбрана, например, линейная свертка критериев - взвешенная сумма максимальных разностей значений параметров взаимосвязанных элементов.
Эта задача имеет важное прикладное значение. Она возникает, в частности, при проектировании изделий из натурального меха или кожи. Заметим, что если число элементов равно числу вершин, и каждый элемент имеет единственный параметр, значение которого совпадает с номером элемента, мы получаем задачу о ширине графа-Задача о ширине графа, а следовательно, и более общая задача проектирования, являются JVP-трудными [71]. поэтому особый интерес представляет выделение полиномиально разрешимых частных случаев и разработка алгоритмов приближенного решения этих задач. Исследованиям в области алгоритмов для задачи о ширине графа посвящены работы [30,34,36,40,44,45,51-53,67,72,73,76]. В работах [29,32,33,41,54,56, 62,70,74,75] описываются некоторые классы графов, для которых задача о ширине может быть решена за полиномиальное время. Заметим, что задача о ширине остается iVP-трудной даже для графов достаточно простой структуры - деревьев с максимальной степенью вершины 3 [45], а также для решеточных графов [38]. Граф называется решеточным, если множество его вершин - это подмножество множества Z2, и две вершины смежны тогда и только тогда, когда евклидово расстояние между ними
равно единице.
Вопросы вычислительной сложности задачи о ширине на решеточных графах являются недостаточно изученными. До настоящего времени в этом классе был известен лишь один нетривиальный полиномиально разрешимый случай - прямоугольные решетки [33]. Решеточные графы часто возникают в приложениях. Так, например, в задаче проектирования изделий из меха граф изделия обычно либо решеточный, либо имеет структуру, близкую к решеточной. Поэтому актуально выделение новых подклассов решеточных графов, для которых задача о ширине полиномиально разрешима.
Поскольку задача проектирования изделий сложной структуры является NP-'Tрудной, помимо выделения полиномиально разрешимых частных случаев этой задачи актуален также поиск приближенных решений. В последнее время для получения приближенных решений А'Р-трудных задач дискретной оптимизации активно разрабатываются подходы, основанные на аналогиях с природой. К данному классу относятся, в частности, эволюционные алгоритмы, алгоритмы имитации отжига, муравьиной колонии. Эволюционные алгоритмы основаны на принципе моделирования процесса биологической эволюции и хорошо зарекомендовали себя при решении многих оптимизационных задач.
Целью данной работы является исследование задачи о ширине графа и некоторых вариантов задачи проектирования изделий сложной структуры, разработка алгоритмов их решения, выделение полиномиально разрешимых случаев, проведение экспериментальных исследований. Основное внимание уделяется задаче о ширине на решеточных графах.
Диссертация состоит из введения, трех глав, заключения и списка литературы.
В первой главе приводятся постановки исследуемых задач, описываются их приложения. Дается обзор результатов в области исследований задачи о ширине графа. Рассматриваются вопросы вычислительной сложности этой задачи, указываются некоторые полиномиально разрешимые случаи, кратко описываются существующие подходы к ее решению. В первой главе рассматривается также лексикографическая постановка задачи о ширине графа и проводится анализ задачи в терминах L-разбиения. Получена нижняя оценка мощности L-накрытия задачи. Показано, что при ряде упорядочений переменных мощность L-накрытия ограничена снизу экспонентой от ширины графа.
Вторая глава посвящена выделению полиномиально разрешимых
случаев задачи о ширине графа. В данной главе рассматриваются специальные семейства решеточных графов - прямоугольные решетки с угловыми выемками, а также графы, имеющие структуру, близкую к решеточной. Установлена полиномиальная разрешимость задачи на прямоугольных решетках с одной и двумя прямоугольными угловыми выемками и на прямоугольных решетках с диагональными ребрами. Показано, что ширину любого графа из соответствующего семейства можно определить аналитически. Указаны способы построения оптимальных нумераций.
В третьей главе исследуется задача проектирования изделий сложной структуры, которую можно рассматривать как обобщение задачи о ширине графа. Построены математические модели для некоторых вариантов указанной задачи. Для приближенного решения задач на основе этих моделей предложен генетический алгоритм. Разработан пакет программ для решения задачи проектирования с помощью генетического алгоритма, проведены экспериментальные исследования. Представлены результаты расчетов для задач с реальными исходными данными, которые показывают перспективность предложенного подхода для рассматриваемой задачи проектирования.
В заключении приведены основные результаты работы.
Основные результаты диссертации опубликованы в работах [1,12-18, 22-24, 57-59] и докладывались на Российских конференциях "Дискретный анализ и исследование операций (Новосибирск, 2002, 2004), международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2002), XII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003), международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006), The XIV Meeting of EURO Working Group on Location Analysis (Корфу, Греция, 2003), The 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics" (Омск, 2004), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005), а также на научных семинарах в Институте вычислительной математики и математической геофизики СО РАН, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.
Автор выражает благодарность научному руководителю профессору А. А. Колоколову, а также В.П. Ильеву за внимание, поддержку и полезные советы при выполнении данной работы.
Постановки задач
Задача о ширине графа и родственные задачи. Приведем постановку задачи о ширине графа, а также некоторых близких к ней задач. Задала о ширине графа, формулируется следующим образом. Пусть G = (V,E) - неориентированный граф. N — \V\. Нумерацией графа G называется биекция ц : V — {1,2 N}. Множество всех нумераций графа G обозначим через Ф(С). Длиной ребра uv [u.v Є V) при нумерации (р называется величина \ р{и) — f{v)\- Наибольшая длина ребра называется шириной нумерации р и обозначается B(G, tp). Задача состоит в отыскании нумерации р , для которой значение B(Ghip ) минимально: Величина B(G) — В{Слр ) называется шириной графа G, а нумерация р - оптимальной нумерацией. Задача о ширине графа относится к задачам оптимальной нумерации. Общим для всех задач данного класса является вид допустимого решения - нумерация вершин, а отличаются они друг от друга лишь оптимизируемой функцией. Приведем постановки некоторых задач оптимальной нумерации. Для ір є Ф(с7) "введем следующие обозначения; S{k, tp) = {ueV : ip{u) fc}, S{k. ip) = {uV : ip{u) k}: dS(k. tp) = {u є S(k, (p) : uv є E для некоторой v Є S(k, tp)}, 9(k,ip) = \{uv E : и Є S(k, p) и v Є S(k,p)}\. Задача оптимального линейного упорядочения (Minimum Linear Arrangement Problem): Задача о ширине разреза (Cutmdih Problem): Задача о величине вершинного разделения (Vertex Separation Problem): Линейное упорядочение с минимальным разрезанием (Sum Cut Problem): Все эти задачи являются jVP-трудпыми [37,46,47,61]. Заметим, что задача о ширине графа, остается Л Р-трудной даже для деревьев с максимальной степенью вершины 3 [45], в то время, как остальные задачи полиномиально разрешимы на деревьях [4.25,42,78]. Задача проектирования изделий сложной структуры. Наряду с задачей о ширине графа в работе рассматриваются некоторые варианты ее обобщения - задачи проектирования изделий сложной структуры.. Приведем содержательную постановку этой задачи. Проектируемое изделие состоит из конечного числа образующих элементов. Структура изделия задается графом С — (V. Е). вершины которого соответствуют возможным местам размещения элементов; а. ребро между парой вершин указывает на наличие взаимосвязи данных позиций. Элементы изделия выбираются из конечного множества, мощность которого не меньше числа вершин графа, и характеризуются фиксированным числом параметров, которые могут быть выражены в числовых величинах. Если пара элементов оказывается размещенной во взаимосвязанных позициях, то могут накладываться ограничения на разность значений их параметров. Требуется расположить в вершинах графа совокупность из \V\ элементов таким образом, чтобы полученное размещение удовлетворяло указанным условиям и являлось оптимальным в смысле одного или нескольких критериев. Желательно, чтобы взаимосвязанные элементы как можно меньше отличались друг от друга по всем параметрам. Поскольку для каждого параметра известен "вес", соответствующий его относительной важности, то в качестве целевой функции может быть выбрана, например, линейная свертка критериев - взвешенная сумма максимальных разностей значений параметров взаимосвязанных элементов. Если число элементов равно числу вершин и каждый элемент имеет единственный параметр, значение которого совпадает с номером элемента, то мы получаем задачу о ширине графа. Комбинаторные постановки этой задачи и некоторых ее вариантов будут рассмотрены в третьей главе. Задача о ширине графа имеет ряд важных приложений в различных областях. Решение систем линейных уравнений. Во многих задачах одним из этапов является решение больших систем линейных алгебраических уравнений. Часто матрицы коэффициентов оказываются симметричными и разреженными (матрица называется разреженной, если количество ненулевых элементов в ней мало по сравнению с общим числом элементов). Например, они могут возникать как матрицы коэффициентов систем дифференциальных уравнений в численном анализе и физике, Несмотря на то, что объем памяти компьютера и его быстродействие существенно возросли в последние годы, решение систем линейных уравнений по-прежнему требует больших затрат памяти и времени. Так. непосредственное хранение в памяти компьютера матрицы размерап х п требует ячеек для всех ее п2 элементов, многие из которых являются нулевыми. Если бы мы могли игнорировать нули, ято позволило бы существенно сэкономить память и время.
Приложения задач
Второй часто используемый критерий - минимизация задержки перс-дачи сигнала. Чем длиннее проводник, тем больше задержка, поэтому при проектировании схемы желательно минимизировать максимальную лличу проводника, уменьшая тем самым длительность задержки. Поскольку модула не могут нахилиться очень близко друг к другу, их располагают в вершинах двумерной сетки (решетки). При некоторых схемах трассировки накладываются ограничения: проводники следуют только вдоль линий сетки, причем два проводника по должны проходить вдоль одного и того же сегмента пути, хотя горизонтальный сегмент может пересекаться вертикальным. Интегральной схеме можно поставить в соответствие неориентированный граф: ве.ртпипы графа соответствуют модулям, а ребра - связям между НИМИ. Такой граф представляет собой упрощенную модель интегральной схемы. Требуется разместить вершины графа на плоскости так. чтобы длина связей (проводников) была как можно меньше. Формально возникают следующие две задачи; 1. Дан неориентированным, граф; требуется разместить его верыипи на двумерной решетке так, чтобы минимизировать суммарную длину ребер. 2. Дай неориентированный граф; требуется разместить его вершины на двумерной релиетж тещ чгп,оби минимизировать машшм-альиую длину ребро.. Здесь под длиной ребра понимается расстояние между его концами на решетке, которое может измеряться как в евклидовой метрике, так и в метрике її. Рассмотрим теперь частный случай задачи проектирования СБИС. когда модули располагаются на кристалле вдоль линии, т.е. в целочисленных точках прямой, Б этом случае задача 1 превращается в задачу оптимального „ынейною упорядочения а задача 2 - п задачу о нейрине графа. Задача оптимального линейного упорядочения применяется при размещении модулей для минимизации суммарной длины проводников. Ширина графа соответствует максимальному расстоянию между модулями, поэтому минимизация ширины эквивалентна минимизации задержки передачи сигнала между ними. Вложения графов. Линейные упорядочения - это частный случай вложений графа в d-мерные решетки или другие графы. В общей форме задача вложения графа G в граф Н состоит в определении инъективной функции, отображающей вершины графа G в вершины графа Н. и назначении пути в графе Я каждому ребру графа О. Одним из параметров, определяющих качество вложения, является ()члагпац ая- максимальная из длин путей в графе Я. соответствующих реГфмм графа G. Нахождение хороших влояалшй важно в некоторых приложениях, например, при параллельных вычислениях. В качестве модели сети параллельных вычислений используется граф G = [\% Е). Каждая вершина графа G соответствует процессору и uv Є Е тогда и только тогда., когда, существует прямая свя:-зь между процессорами и и v {u,v є 1/). Процессоры получают входные данные; главная программа определяет, какие вычисления должны быть произведены каждым процессором- За единицу времени процессор может передать результаты вычислений одному из соседних процессоров, который зааем будет использовать полученные результаты как входные данные для своих вычислений. Предположим, требуется решить некоторую задачу на сети параллельных вычислений G с помощью программы Р, Если есть С недоступна, но есть другая сеть Я; мы можем имитировать7" программу для сети G программой для Я, которая решает ту же задачу. Таким образом, требуется описать способ использования программы Р, при котором сеть И может выполнять те же действия, что и G, при назначении ее процессорам тех заданий, которые назначались процессорам сети
Вспомогательные утверждения
Пусть G — [V.E) - неориентированный граф, р G_ Ф(Т/). Нумерацию р fc Ф(Ст ), определяемую по правилу p{v) = \V\- p\v) -1, v V, будем называть двойственной к нумерации (р. Очевидно. В{С\(р) = В(С,-р), Внутренней и вчіштй границами множества U С V называются множества сответстзечно. Напомним, что 8{к,(р) = {и Є V ; р{и) к}, где р Є Ф{0). Далее, если из контекста полотно, о какой нумерации идет речь, мы будем опускать символ \р: и писать S(k). Следующая лемма будет использована при построении нижней оценки ширины графа. Лемма 2Л. Для любого связного пворшунптроваипоул) .рафаС. для любой пумс-риции (р &(&) справедливы неравенства: Доказательство леммы вытекает из следующего включения [31] и аналогичного включения для внешней границы; Напомпгш некоторые определения и обозначения, введенные в первой глазе. Граф называется решеточпьш. если множество его вершин - это подмножество множества Z1 м две вершимы смежны тогда и только тогда, когда евклидово расстояние между ними равно 1. Gmji решеточный граф с множеством вершин [l.m] х [1.л]. т.п I, G(a) - графj порученный путем едзигя решеточного rpaoaG па "зехтор а Є Z2. Нетрудно проверить справедливость следующего утверждения. В самом деле, рассмотрим ограничение нижней диагональной нумерации графя G тлі множество вершин подграфа Я. Получим т.н. нумерацию рафи Н с несял /аіной нумерующей поашдоволпельпоспіь-ю 119 (обобщение традиционного понятия нумерации). По дашюи нумерации легко построить сплошную нумерующую последовательность., сохраняющую порядок нумерации вершин, при которой знаменье целевой функции не увеличится. Полученная в результате нумерация граба Я с точностью до аддитивной константы совпадет с его нижней диагональной нумерацией, откуда и вытекает требуемое. Аналогичные рассуждения применимы я к верхней диагональной нумерации. Напомним, что графы семейства Qm ll называются чрямоугольимми vtmenmaMu. Строки v, столбцы прямоугольной решетки определяются естественным образом, причем строки нумеруются снизу вверх; а столбцы - слеза направо (например, j-я строка графа С\ПтП - это множество [l./m] х {j}). Для произвольного решеточного графа j-я строка, [СЛУОЧ-иетстзешто, г-и столбец) определяется как пересечение множества его вершки с j-l\ строкой (соо і вететвенно, Ї-М столбцом) минимальной по включению прямоугольной решетки, содержащей этот граф. Пусть С - неориентированный граф, Я С G. И Є /,,.., р Є Q(G). Обозначим г ерез r(ip. Я) {( -{ г- її)) гаименычее к такое, что каждая строки (соответственно, столбец] подграфа Н содержяг хотя бы о/,ну вершину множества S(k) = S(k,ip). Когда понятно, о какой нумерации идет -)ечь; мы будем писать г(ff) (соответственно, с{Н)}. Очевидно, f(H) 1 .три и 1. и сШ) 1 при m 1. Доказательство. Докажем первое утверждение, остальные л.оклзыса- ются я Е-: алогично. При к с(Н) доказательство тривиально, так как в этом случае каждая строка подграфа Я содержит как вершины АЛЮНС- (TWA S. так ч верпины множества VH\S. откуда следует \dS П Уі-і\ п. Пусть теперь к — с{ЇЇ). В этом случае каждая строка подграфа Я кроме, может быть, той, в которой находится вершина с комепог/ к, со держит как вершины множества S. так и вершины множества VH\S. Кроме того, ьерлшка _J (к) нвл ето: единственной в своем столбце вер шиной множества 5, а г: ак как п I, то -р 1(к) Є 5,5 . Таким образом, \DS П V H\ (n — 1) + 1 = п. Утверждение 1 доказано. Следствие 2.1, В условиях лемлт 2,3, если к Є \к п(1Г\,ктвл(Н)} и т,п 1; то выполняю первенство \dS Г Ун\ mm(m,n). где ,п(Я)=от;г(Я;.с(Я)); 0Х(Я) = тах(г(Я)1 77)). Лемма 2.4. Пусть О - связный, неориетт/аровапный граф. Gi;W!i С G. и 1, Ф(0). tf(G ) - п и к t [r-(GK1..0 (GrlV./Hj]. ТЪяЛб Ли ли-fro,?o j Є l.n - Iі справедливо неравенство \\S}\ — \Sj+i\\ 1.- где Sj -пересечение множества 5 -= S{k) с j-й строкой подграфа GfaM. Доказательство. Рассуждая, как ;i лемме 2.3, можно показать, что в каждой строке граба G,JV, содержится не менее одной вершины пз 55. Предположив, [:то \\Sj\ — S _i! 1 для некоторого j Є l.n — 1". при ходим к выводу, что в одной из строк j или ] + 1 содержится 6олыт:е одного элемента из dS. Такий образом, получаем \dS\ п. следователь но. B\GAP) п по лемме 2,1. Противоречие. Лем.иа доказана.
Математические модели
В данном разделе предлагаются математические модели для задачи проектирования изделий сложной структуры. Пусть п = \V\ т - общее число элементов, из которых производится выбор [т п). р - число параметров, К С {]...,,р} - множество номероії параметров, на которые накладываются ограничения. Введем обозначения: я 0 - значение fc-ro параметра г-го элемента, і = 1, ..., m, к — 1. ....р, Ьк 0 - ограничение на разность значений но к-щ параметру, к Є К, wk 0 "вес" к-го параметра, еоответотвуюіций его относительной важмости, к — 1 p. Пусть p - размещение совокупности п элементов в вершинах графа G, т.е. р : V — {1,...,т} - инъективное отображение (напомним, что С — {V:E) - граф изделия). Множество всех таких размещений будем обозначить через Ф (С). Таким образом, ip(v) - это номер элемента, размещенного в вершине г1. Получаем следующую задачу дискретной оптимизации: v !{ч ) = Е wWc(ul - а., ,,1 - min Нетрудно заметить, что при выполнении условий т = п, р = 1, Лг = 0, и 1 = 1 и и- — і для любого г — 1,.,.,т мы получаем задачу о ширине графа. Таким образом, задача (3.1) является обобщением задачи о ширине графа. Часто при проектировании возникают дополнительные требования, связанные со спецификой области приложений, такие как симметричность изделия по некоторым параметрам (это актуально, в частности, при проектировании одежды). Заметим, что в такой постановке потребуется два набора весов, поскольку для одного и того же параметра требование равномерности может быть более жестким, чем требование симметричности, или наоборот. Для учета требования симметричности в графе изделия вводятся дополнительные ребра, соединяющие, вершины, еооі вететвующис парам симметрично расположенных позиций. Затем строятся ограничения, подобно тому, как это было сделано для соседних позиций. Для дан мої ч) варианта задачи модель модифицируется следующим образом. Пусть Еі множество ребер, соединяющих пары вершин, соответствующих соседним позициям, Е-2 множество иебер, соединяющих пары вершин, соответствующих симметрично расположенным позициям, Л ьА {1;2, ...,JJ} - множества номеров параметров, на которые накладываются ограничения для соседних и д:п симметричных позиций, соответственно. Введем обозначения: 6 0 - ограничения на разность значений по fe-му параметру для соседних позиций, к Є К]_. Ь\ 0 - ограничения на разность значений по k-ыу параметру для сим- мстричпых позиций, к Є К-2. w\.v)2 0 - веса fc-ro параметра для соседних и для симметричных позиций, соответственно, к = 1, .-...р. С учетом введенных обозначений задача запишется в виде: Данная постановка является более общей, чем (3,1), поэтому ее тоже можно рассматривать как обобщение задачи о ширине графа. г — l,....n,j = 1 т. Введем также вспомогательные переменные %k U, fc = 1; ---ЇР (эти переменные могут быть ноцелочисленными). Задачу (3.1) можно записать в виде задачи частично целочисленного линейного программирования следующим образом: Данная модель легко модифицируется при наличии требования симметричности. Предложенная модель позволяет применять для решения исследуемой задачи различные методы ЦЛП. Однако, эксперименты показали, что для реальных задач большой размерности точные алгоритмы оказываются непригодными, поскольку они не способны находить решение за приемлемое время. Поэтому естественным подходом представляется использование эвристических алгоритмов, которые могут находить достаточно хорошие приближенные решения. В следующем разделе описывается один из них - генетический алгоритм.
