Содержание к диссертации
Введение
ГЛАВА I. Задача разрезания графа без ограничений 20
1.1. Постановка задачи. Основные сведения 20
1.2. Вычислительная сложность задачи 23
1.3. Исследование многогранника 26
1.4. Точный алгоритм решения задачи 32
ГЛАВА 2. Алгоритмы решения задач разрезания графа с ограничениями 44
2.1. Общие сведения. 44
2.2. Исследование эвристических алгоритмов 46
2.3. Точные методы решения задач разрезания графа с ограничениями 71
ГЛАВА 3. Константность и смежные вопросы теории задач выбора оптимального подграфа 88
3.1. Формулировка проблемы 88
3.2. Результаты для направленных графов 93
3.3. Результаты для симметричной задачи выбора опти мального подграфа 102
Литература 108
- Вычислительная сложность задачи
- Точный алгоритм решения задачи
- Точные методы решения задач разрезания графа с ограничениями
- Результаты для симметричной задачи выбора опти мального подграфа
Введение к работе
При решении многих прикладных проблем, связанных с техническим проектированием, обработкой и классификацией данных, возникают задачи следующего вида: задано некоторое множество взаимосвязанных объектов, известны показатели их попарной взаимосвязи /сходства, близости/; требуется разбить все множество объектов на несколько непересекающихся подмножеств так, чтобы минимизировать общую величину связей между различными подмножествами либо максимизировать суммарную связь объектов внутри подмножеств. Приведем примеры подобных задач:
1 Задача сегментации программы /27, 38, 71_/: задано множество программных единиц /модулей, секций, блоков/, составляющих некую программу, известны частоты совместного или последовательного выполнения каждой пары программных единиц. Требуется найти разбиение программы на сегменты /наборы программных единиц/ обеспечивающее минимальную суммарную частоту межсегментных обращений; при этом каждый из сформированных сегментов должен вмещаться в оперативную память ЭВМ.
2 Задача компоновки радиоэлектронных схем /40, ZJ : задано множество функциональных элементов, составляющих радиоэлектронную схему, для каждой пары элементов известно количество схемных соединений между ними. Требуется разбить данную схему на ограниченное число плат, так, чтобы общее число соединений между различными платами было минимальным; при этом необходимо учитывать ограничения по размерам плат.
3 Задачи классификации и кластерного анализа /з, 19, 20/, 37/ : задано множество классифицируемых объектов /наблюдений, признаков, элементов организационных, природных или технических систем/, известны показатели попарных связей между объектами например, коэффициенты корреляции/. Требуется найти разбиение заданного множества на "обозримое" число классов, максимизирующее суммарную величину связей внутри классов. В том случае, когда классифицируемым объектам соответствуют точки в некотором признаковом пространстве, классификация может основываться на значениях попарных расстояний между точками; при этом минимизируется сумма внутриклассовых расстояний. /В связи с тем, что требования к искомой классификации могут существенно изменяться в зависимости от специфики классифицируемых обьектов, при формулировке задач кластерного анализа в литературе /3, 20, 54J используются, наряду с упомянутыми и другие критерии, не характерные для традиционных постановок задач типа разрезания графа и поэтому не рассматриваемые в данной работе/.
Вычислительная сложность задачи
Задача разрезания графа без ограничений /ЗРТи / формулируется следующим образом где кУ состоит из всех возможных разбиений заданного множества А/ на непересекающиеся подмножества. Элементы заданной матрицы W могут быть положительными, отрицательными, или равными - оо /Йоследнее означает запрет на включение соответствующей пары вершин в одно подмножество/. Отметим, что при отсутствии в весовой матрице отрицательных элементов решением ЗРП/ является вырожденное разбиение Р& =l{A/J/ , при отсутствии положительных - тривиальное разбиение От ji J, { }, --,1 JJ Укажем также, что задача не нуждается в отдельном рассмотрении, ибо J.//K WjPr J-l/V wd Приведем примеры практических задач, сводящихся к ЗРГ : I/ Задача классификации с порогом существенности /Куперш тох, Миркин /297 /: пусть А/ - множество классифицируемых обьектов, Ucj -показатель взаимосвязи объектов С , У , CJ - порог существенности связи: при 6Joj 6J u взаимо связь между объектами С , J считается несущественной, при СОСІ -0) и— существенной. Задача формулируется как ЗРГ / при iJlj - &)cj" OJ . Как показано в работах /41 , 30/, такая формулировка задачи классификации по матрице связей хорошо зарекомендовала себя на практике. 2/ Задача отыскания медианы Кемени -Снелла для разбиений /Л.Б. Черный /587/:. Пусть даны ҐЇЇ разбиений р , Dzy.., рт множества А/ /налример, /Г) группировок, построенных экспертами/, А, Л , .- .j X -их характеристические матрицы, и задана некоторая метрика с/ на множестве разбиений. Требуется найти так называемое компромиссное разбиение п , такое, что: именуемое медианой Кемени - Снелла f25j. В работе [58] показано, что при и(р,р )= _ loCy-eXyh/L ( Xt) OCy) имеет место равенство где Ы. = 2- zXtj /7?/ , то есть задача нахождения /У сводится к ЗРГ и . 3/ Задача классификации по эталонам /распознавание образов с учителем Лфперштох [з, 3lJ /: в множестве /V классифицируемых объектов задан набор эталонных объектов 6j 6f ...,6 , которые заведомо должны лежать в различных подмножествах разбиения. Критерием качества классификации /разбиения/ служит сумма внутренних связей. Для того, чтобы сформулировать данную задачу как Ъ??0 , достаточно положить & -- при Для решения ЗРГи используются различные эвристические процедуры. В качестве примера приведем локально-оптимальный алгоритм из /зо7э представляющий собой комбинацию нескольких таких процедур: I/ "Объединение": начинается с тривиального разбиения рТ . На А -м шаге рассматривается разбиение р { у ]Є J » в нем выбирается пара подмножеств A/s , А , для которой: XZ, Щ = МОХ L/AL.t Щ Если эта сумма больше нуля - подмножества объеди няются, переходим к следующему шагу (А —А4"// . В ином случае переходим к следующей процедуре. 2/ "Перемещение": начинается с разбиения, полученного предыдущей процедурой, и состоит в последовательности перемещений каждой вершины из одного подмножества в другое. На каждом шаге производится перешщение, дающее наибольшее положительное приращение суммы внутренних связей. Если перемещения, увеличивающие функционал, невозможны - происходит переход к следующей процедуре.
Проверка": в полученном с помощью предыдущей процедуры разбиении р {ІУІ, J Є J J выделяются такие подмножества ft/s , что 2- ькі 0 » и "рассыпаются" на отдельные вершины. Если таких подмножеств нет - алгоритм завершает свою работу, иначе происходит возврат к процедуре "Объединение".
Несмотря на наличие разнообразных приложений ЗРГ U , для нее до сих пор не разработаны точные методы решения; мало изучена ЗРГ и в теоретическом отношении. Этот пробел частично восполняется в данной главе. В 2 устанавливается принадлежность 3FPu к классу А/Г - трудных задач, затем приводятся некоторые результаты, связанные с многогранником ЗРГ / / 3/. Точный метод типа ветвей и границ для решения данной задачи описан в 4. Там же приведены результаты вычислительного эксперимента, демонстрирующие эффективность метода.
Точный алгоритм решения задачи
В /637 показано, "что к данной задаче сводится /V/ полная задача о максимальном разрезе. I) Здесь и далее в I имеется в виду А// - полнота распознающего варианта задачи. в/ упрощенный вариант задачи классификации по матрице расстояний /в такой же формулировке записывается задача закрепления абонентов за вычислительными центрами /776/7 При /"=/6 к данной задаче сводится задача о максимальном разрезе, при /"- /? - задача раскраски графа в 3 цвета. Таким образом, рассмотренные в литературе варианты задачи разрезания графа с ограничениями эквивалентны по вычислительной сложности и являются /Vr - полными в сильном смысле. В пред положении, что это означает невозможность построе ния точных полиномиальных и псевдополиномиальных алгоритмов реше ния указанных задач. В этой связи большое значение приобретают различные эвристические алгоритмы, являющиеся практически един ственным средством решения задач большой размерности. В настоя щее время эвристические алгоритмы решения ЗРГ достаточно разра ботаны и интенсивно используются на практике. При этом, в связи с наличием весьма разнообразных приложений ЗРГ, допускается из вестный параллелизм: так, эвристический алгоритм сегментации прог рамм из Z38y, так называемые "быстрые" алгоритмы классификации /.42./, параллельные алгоритмы компоновки электронных схем /52І ос нованы на одной и той же схеме последовательного закрепления вер шин за подмножествами. В 2 выделяется несколько подобных эврис тических схем, широко использующихся на практике, исследуются их свойства и строятся гарантированные оценки поведения. Используя и развивая эвристические алгоритмы решения ЗРГ, не следует забывать и о точных методах, которые необходимы для полной оптимизации в задачах небольшой размерности, а также для экспериментальной оценки погрешности эвристических алгоритмов. Вместе с тем далеко не для всех практически важных задач разрезания графа разработаны такие методы. В 3 приведен краткий обзор су 45 ществующих точных методов решения различных вариантов ЗРГ; предложены точные алгоритмы типа ветвей и границ для двух прикладных задач: задачи сегментации программ и задачи классификации по матрице расстояний. 2. Исследование эвристических алгоритмов 2.1. Краткий обзор. В результате анализа литературы выделяются следующие наиболее употребительные эвристические схемы решения ЗРГ: I/ Последовательно-объединяющие /йО/ алгоритмы /агломератив ные алгоритмы /427/. На начальном шаге рассматривается тривиаль ное разбиение JD множества А/ на /7 одноэлементных под множеств. На очередном л -м шаге в уже построенном разбиении P=jM% JcJJ среди всех пар подмножеств, обьединение которых увеличивает сумму внутренних связей разбиения без нарушения усло вий допустимости, по некоторому правилу выбирается пара подмно жеств и производится их обьединение. Если получено допустимое разбиение, а любое дальнейшее обьединение подмножеств ухудшает функционал, либо нарушает допустимость - работа алгорит ма завершается. Пусть /4 - множество пар индексов (t,j) подмножеств A/J » обьединение которых на очередном шаге не нарушает допустимости. Приведем наиболее известные правила выбора, употребляющиеся на практике: а/ правило„ближайшего еоседа/3, 42у где dj =/770сХ[це JfeA/c , єА}% б/ правило максимальной связи /з, 42] Z/ Последовательночзакрепляющие /ЇВ/ алгоритмы /алгоритм "Размещение" параллельные алгоритмы /. Применяются обычно при фиксированном числе / подмножеств в искомом разбиении. На начальном шаге некоторым образом выбирается / вершин-эталонов 6,, #,..., 6г $ каждая из них закрепляется за одним из подмножеств. На очередном /f-м -шаге выбирается одна из еще незакрепленных /свободных/ вершин и закрепляется за наиболее "близким" к ней подмножеством. /Рассматриваются только такие варианты закрепления, которые не нарушают допустимости построенного частичного разбиения/. После того, как все вершины закреплены за подмножествами, работа алгоритма завершается. При выборе вершин-еталонов может использоваться априорная информация о типичных представителях классов-подмножеств разбиения. При ее отсутствии применим, например, следующий рекуррентный метод: Чк =MCr?{Lbfek :N\li,,L ,-.;ts ]} отражающий интуитивно представление о максимальной взаимной "непохожести" типичных представителей различных классов.
Точные методы решения задач разрезания графа с ограничениями
Поиск оптимального разбиения множества вершин осуществляется в данном алгоритме с помощью специальной процедуры ограниченного перебора допустимых сочетаний вариантов перераспределения вершин. Для отсечения бесперспективных сочетаний используется следующая нижняя оценка суммы внешних связей: определяемая для каждого варианта V перераспределения вершин подмножества /Vj на так называемом предварительном этапе алгоритма. Основным недостатком данного алгоритма является, таким образом, необходимость рассмотрения на предварительном этапе огромного количества возможных вариантов перераспределения вершин /например, при Л J , /?/"Лг=/1ъ= /О следует рассмотреть вариантов/. В работе Н.Е. Гайкова задача /3.1/ решается методом построения последовательности планов. Поиск оптимального решения производится на множестве согласованных перестановок вершин не 74 которого исходного разбиения, что в определенном смысле сближает этот алгоритм с алгоритмом Горинштейна. Однако, в отличие от последнего, алгоритм Гайкова не требует трудоемких предварительных вычислений. В методе В.К. Пучиньяна, М.Е. Штейна, П.Д. Шеина предназначенном для решения задачи Л.І - 3/, применяется ветвление по множеству внутренних ребер разбиения. С этой целью ребра нумеруются в порядке убывания весов; затем осуществляется ограниченный перебор всех наборов ребер вида где cJc - номер ребра, л номер уровня дерева вариантов, (Ji (л)& ... Л Отсечение бесперспективных вариантов производится с помощью следующей верхней оценки суммы внутренних связей: A J max Здесь Си) - вес ребра с номером / , Ітаос - максимально возможное число внутренних ребер в разбиении /с учетом ограничений на размеры подмножеств/. Данный алгоритм, как легко видеть, близок по своей идее к эвристической ПО - схеме, также предусматривающей последовательное включение ребер в число внутренних. Однако, в отличие от указанной схемы, в данном алгоритме полностью игнорируется возможность "отождествления" вершин, инцидентных внутреннему ребру, что приводит к ухудшению точности оценки и усложняет процедуру перебора. /Отметим, что указанная возможность в полной мере используется в описанном раннее точном алгоритме решения ЗРГ 0 /. В некотором смысле дополнительным к рассмотренному алгоритму является метод І.С. Бернштейна, В.В. Селянкина /46J, предназначенный для решения задачи /3.1/ с критерием минимума суммы внешних связей. Ветвление в этом алгоритме производится по мно 75 жеству внешних ребер разбиения. При этом используется следующая нижняя оценка суммы внешних связей для сформированного частичного набора внешних ребер U : &(ju)=Z Щ L м minjwst (s,t)J/}, где /L - множество путей из L в J , минующих ребра из /У, Данный алгоритм, близкий по своей идее к эвристической схе ме последовательной дихотомии, разумно применять лишь при нали чии одного резко выделяющегося по размеру подмножества в искомом разбиении. В самом деле, если /?/ /?/Й для любого 6 , то количество внешних ребер /а следовательно, и число уровней дерева ветвления/ превышает /7V/ ; на очередном л -м уров не следует рассматривать порядка альтер натив. В то же время для МВГ - ПЗ - алгоритма аналогичные показа тели равны /7 и /" соответственно. Подводя итоги приведенному краткому обзору, можно сказать что в разработанных на настоящий момент методах ветвей и границ для решения ЗРГ наиболее удачно была использована обычная схема последовательного закрепления вершин. Идеи эффективных эвристических схем последовательного объединения и последовательной дихотомии еще не получили должного отражения при разработке точных методов. Ниже описываются алгоритмы ветвей и границ для решения двух прикладных задач разрезания графа: задачи сегментации программы и задачи классификации по матрице расстояний. В обеих задачах число подмножеств в оптимальном разбиении зараннєє неизвестно. Для решения задачи сегментации программы предлагается алгоритм, основанный на схеме последовательного обьединения и близкий к алгоритму решения ЗРГ (J из 1.4; для задачи классификации по матрице расстояний - модификация МВГ - ПЗ - алгоритма, не требующая априорного знания числа подмножеств в разбиении.
При проектировании математического обеспечения ЭВМ возникает задача разбиения больших программ и программных комплексов на отдельно загружаемые в память сегменты. Количество сегментов зараннєє не фиксируется, каждый сегмент должен вмещаться в оперативную память ЁВМ или в одну ее страницу /т.н. страничная сегментация/; число межсегментных обращений, требующих "подкачки" дополнительных сегментов в память, должно быть минимальным. Пусть
VI - обьем памяти, занимаемой і -й программной единицей /командой, секцией, модулем/, С /7Л , где /7 -количество программных единиц; V - обьем оперативной памяти ЭВМ, W-матрица показателей частоты взаимодействия различных программных единиц. /В качестве таких показателей используются , средняя частота передач управления /71 У, вероятность передачи управления /387, коэффициент связности, учитывающий частоту совместного или последовательного выполнения программных единиц /277/. Тогда, в соответствии с работами /27, 38, 7ІУ, задачу сегментации программы можно сформулировать следующим образом: минимизировать межсегментные взаимодействия
Результаты для симметричной задачи выбора опти мального подграфа
В [70/ установлен следующий результат, связывающий описание всех линейных эквивалентных преобразований с описанием условий константности задачи: Утверждение I.I. /70j. Преобразование матрицы W в У является линейным эквивалентным преобразованием для Сгг, ...7 СТу/ тогда и только тогда, когда где - произвольная матрица, такая, что для любого X /ifCr , CrZj..., cry/. 2/ Аффиная оболочка целочисленного многогранника задачи. Матрицы из ПІСГІ,(jk,..., Сг ) являются точками//7 -/7/-- мерного пространства МА) квадратных матриц порядка ҐІ с нулевой диагональю. В связи с общей проблемой описания цело численного многогранника задачи /I.I/ - выпуклой оболочкиC0/7V/7 множества /7 //(( /,( ,..., (їч)- возникает следующая подпробле ма: найти размерность этого многогранника и описать аффинную обо лочку off/7 множества . Имеет место следующее очевидное утверждение, позволяющее от условий константности ЗШ/6/,Чё,— " / перейти к описанию аффинной оболочки множества/// &"#,..., Cry) и наоборот: Утверждение 1.2. Пусть Zf/7/ - параллельное of//7 линейное подпространство, /7 HfCn, О ,..., 0"у/, Тогда для конс тантности ЗВП{Gi,Gk,.-.3&l)z весовой матрицей необходи мо и достаточно, чтобы - ортогональ ное дополнение Проблема описания размерности различных дискретных множеств неоднократно рассматривалась в литературе. Так, в работах [ 5l], [61] описаны различные базисы аффинной оболочки множества пере становочных матриц и показано, что СІС/7? S» 0?"/) . Из теоремы Биркгофа о многограннике бистохастических матриц сле дует что О/Т З в точности совпадает с множеством реше ний следующей системы
Известны результаты В.И. Сарванова [50], М. Гретшеля, М. Падберга б4] о том, что аффинная оболочка О/ТО множества матриц гамильтоновых контуров совпадает с множеством матриц-решений системы /1.2/, /1.3/, имеющих нулевую диагональ. В работе М.М. Грешнева /l7j показано, что аффинная оболочка многогранника задачи о наилучшем полном /р? - вершинном подграфе совпадает с множеством решений уравнения:
Независимым от приведенных результатов путем, на основании чисто комбинаторных соображений были описаны условия константно 92 сти для задачи о назначениях /Д.А. Супруненко, Н.Н. Метельский /557/, для задачи одного коммивояжера /В.К. Леонтьев /34?, для различных модификаций задачи нескольких коммивояжеров /А.Х.Г. Риннооу Кан, К.Г. Ленстра [70/, Е.Я. Габович [97/. Данная глава посвящена описанию условий константности для произвольных задач выбора оптимального подграфа, с использованием линейно-алгебраического подхода, базирующегося на Утверждении 1.2. Мы будем изучать условия константности только для задач вида ЗВП/Сг/ Этот удобный для анализа класс задач выбора оптимального подграфа является одновременно и наиболее важным, как следует из приведенного ниже очевидного утверждения: Утверждение 1.3. Задача ЗВП (Сг/, & ,. 6"v/ с матрицей весов ]л/ является константной тогда и только тогда, когда каждая из задач ЗВП (Оч) » С ъУ с той же матрицей весов W является константной. В 2 изучаются свойства подпространств вида Мп(г\) ї на основании полученных в этом параграфе результатов описываются необходимые /а в некоторых случаях - и достаточные/ условия константности для ЗВП (d) , где Сг - направленный граф. /Напомним, что направленным называется ориентированный граф, в котором для любой дуги ґс,/} отсутствует "встреч ная" дуга (j, С/ / В 3 рассматриваются ЗВП fCr/ с симметрической матрицей весов и неориентированным графом Lr , называемые далее симметричными ЗВП (О"/ . Для задач такого вида с произвольным неориентированным графом Сг нами полностью описаны необходимые и достаточные условия константности. Из полученных результатов в качестве следствий выводятся условия константности для задачи разрезания графа с фиксированными размерами подмножеств, а также некоторых других задач оптимизации на графах. 2. Результаты для направленных графов Пусть / - некоторая подстановка. Определим в пространст ве матриц следующее линейное преобразование: где г (// - соответствующая / перестановочная матрица, . Имеет место: Утверждение 2.1. Если для любого Ye S» . Доказательство. Вершины графов Сг и /f/p поме чены числами /,,...,/7 , поэтому любая подстановка определяет некоторый подграф Сг в Л/? , изоморфный Сг . Пусть - матрица смежности вершин графа Сг . Тогда, как легко видеть, У7 есть матрица смежности графа Сг , и . Далее, пусть По определению , существуют такие числа Тогда X 2i- jrd. » гДе У " " произведение подстановок поэтому /\ также принадлежит /_,(п(Ст)/ » чт0 и требовалось доказать. Заметим, что преобразования /2.1/ определяют линейное представление симметрической группы и/л? в пространстве При этом, как следует из Утверждения 2.1, подпространства вида LJ(//(CT// - инвариантные подпространства данного представления. Для дальнейшего изложения нам понадобятся определения и свойства некоторых других инвариантных подпространств.
Похожие диссертации на Исследование и разработка алгоритмов решения некоторых комбинаторных задач типа разрезания графа
