Исследование и разработка алгоритмов решения некоторых комбинаторных задач типа разрезания графа тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Гильбурд, Михаил Марксович

• Гильбурд, Михаил Марксович
• кандидат физико-математических наук
• 1985

Оглавление диссертации кандидат физико-математических наук Гильбурд, Михаил Марксович

ВВЕДЕНИЕ.

ГЛАВА I. ЗАДАЧА РАЗРЕЗАНИЯ ГРАФА БЕЗ ОГРАНИЧЕНИЙ.

§ I.I. Постановка задачи. Основные сведения.

§ 1.2. Вычислительная сложность задачи.

§ 1.3. Исследование многогранника.

§ 1.4. Точный алгоритм решения задачи.

ГЛАВА 2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ РАЗРЕЗАНИЯ ГРАФА С

ОГРАНИЧЕНИЯМИ.

§ 2.1. Общие сведения.

§ 2.2. Исследование эвристических алгоритмов.

§ 2.3. Точные методы^ решения задач разрезания графа с ограничениями.

ГЛАВА 3. КОНСТАНТНОСТЬ И СМЕЖНЫЕ ВОПРОСЫ ТЕОРИИ ЗАДАЧ

ВЫБОРА ОПТИМАЛЬНОГО ПОДГРАФА.

§ 3.1. Формулировка проблемы.

§ 3.2. Результаты для направленных графов.

§ 3.3. Результаты для симметричной задачи выбора оптимального подграфа.

ЗАКЛШЕНИЕ.

Введение диссертации (часть автореферата) на тему «Исследование и разработка алгоритмов решения некоторых комбинаторных задач типа разрезания графа»

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

I/ Задача сегментации программы /27, 38, 7lJ: задано множество программных единиц /модулей, секций, блоков/, составляющих некую программу, известны частоты совместного или последовательного выполнения каждой пары программных единиц. Требуется найти разбиение программы на еегмвнты /наборы программных единиц/ обеспечивающее минимальную суммарную частоту межсегментных обращений; при этом каждый из сформированных сегментов должен вмещаться в оперативную память ЭВМ. но множество функциональных элементов, составляющих радиоэлектронную схему, для каждой пары элементов известно количество схемных соединений между ниш. Требуется разбить данную схему на ограниченное число плат, так, чтобы общее число соединений между различными платами было минимальным; при этом необходимо учитывать ограничения по размерам плат.

3/ Задачи классификации и кластерного анализа /з, 19, 2о/, ЗтУ : задано множество классифицируемых объектов /наблюдений, признаков, элементов организационных, природных или технических систем/, известны показатели попарных связей между объектами

2/ Задача компоновки радиоэлектронных схем заданапример, коэффициенты корреляции/. Требуется найти разбиение заданного множества на "обозримое" число классов, максимизирующее суммарную величину связей внутри классов. В том случае, когда классифицируемым объектам соответствуют точки в некотором признаковом пространстве, классификация может основываться на значениях попарных расстояний между точками; при этом минимизируется сумма внутриклассовых расстояний. /В связи с тем, что требования к искомой классификации могут существенно изменяться в зависимости от специфики классифицируемых обьектов, при формулировке задач кластерного анализа в литературе /з, 20 , 54J используются, наряду с упомянутыми и другие критерии, не характерные для традиционных постановок задач типа разрезания графа и поэтов не рассматриваемые в данной работе/.

Задачи, аналогичные перечисленным, возникают также при проектировании организационных структур /4, 4sJ и сети ВЦ коллективного пользования Ы, при обработке экспертных данных Ы и т.п. В математической постановке все эти задачи формулируются как частные случаи следующей общей задачи:

ЗАДАЧА РАЗРЕЗАНИЯ ГРАФА /ЗРГ/Ч Дан взвешенный граф (jr с множеством вершин и матрицей весов ребер л/~ (ц) . Веса ребер могут быть положительными, отрицательными, равными - схэ ; при отсутствии ребра (t,j) в графе полагаем Ь^ . Каждое разбиение р множества

А/ на непересекающиеся подмножества М, N* №(р) характеризуется функционалом суммы внутренних связей:

IW. y.p^U^ у--' С>Я*У отражающим степень автономности подмножеств в разбиении.

I) В иностранной литературе употребляется термин "задача разбиения графа" (Graph part с t to/76/?£ рг0ё/?ет).

Требуется найти в некотором множестве допустимых разбиений разбиение р* с наибольшим значением функционала:

1Ш, W,p*) =maoc(I(N, Up) -ре <£} /ол/

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

EM.W.pi-ti

J <f " / <р

Однако, в связи с тем, что для любого р€справедливо равенство : да Р)+ш w.P) =ш'> где vJlj/fl - сумма весов ребер графа Сг , задача поиска разбиения JD* с минимальной суммой внешних связей:

ЕМ, IV, р») = тш{ЕШ. У.рУр е <%} эквивалентна задаче /ОЛ А

Если веса ребер интерпретируются как расстояния между точками в признаковом пространстве, то задача классификации по критерию миницума суммы внутриклассовых расстояний формулируется следующим образом: mir/flf/V, W, р)-р « и сводится к /ОЛ/ после замены знаков всех весов ребер на противоположные.

Ребро {^j) назовем внутренним в разбиениир , если инцидентные ему вершины принадлежат одному и тому же подмножеству разбиения; в ином случае ребро имэнуется внешним. Матрицу

У~Х(р) , в которой = / , если ребро (t,j) - внутреннее в р , <JCij~ ^ , .если - внешнее, назовем характеристической матрицей разбиения. Пусть - множество Ф характеристических матриц разбиений из . Тогда задачу разрезания графа можно записать как частный случай общей задачи максимизации линейного функционала на дискретном множестве:

W*t(W.X):XeX(%)} где (W,X) J^-Zj- Щ/ - скалярное произведение векторов-матриц.

Таким образом, ЗРГ является типичной задачей дискретной оптимизации. В настоящее время теория и практика решения таких задач интенсивно развиваются. Каждая из известных задач дискретной оптимизации: задача коммивояжера, задача о ранце, задача размещения и т.п. - обладает существенной специ^кой, однако в научной литературе уже сформировался общий взгляд на основные направления исследований, наиболее важные при изучении конкретной задачи. Таковыми являются:

I/ Определение вычислительной сложности задачи в смысле Кука - Карпа - Левина

24, 32J. Основные результаты полученные в этой области, изложены в монографии М. Гэри, Д.С. Джонсона [18].

2/ Разработка точных методов решения: для решения /1//^ -полных задач обычно применяются конкретизации общих вычислительных схем, таких, как метод ветвей и границ /Левд, Дойг [&9], Литтл, Мурти и др.

Ы /, последовательный анализ вариантов /B.C. Михалевич /, аддитивный алгоритм /д. Балаш Ы/, метод последовательности планов /В, к. Емзличев Ы /. Теоретическое анализу эффективности точных методов посвящены работы Ю.Ю. Финкелыптейна, В.П. Гришухина, А. А. Фридмана.

3/ Разработка и анализ поведения эвристических алгоритмов: актуальность данного направления связана с практической невозможностью точного решения /VP - полных задач большой размерности. Весьма универсальные эвристические схемы решения задач дискретного программирования описаны и изучены Ю.И. Журавлевым /локальные алгоритмы ы Й.В. Сергиенко /алгоритм вектора спада Ы /, С.В. Яблонским /покоординатный алгоритм Ы /. Различные подходы к анализу поведения эвристических алгоритмов изложены в работах M. Гэри, Д. Джонсона, С. Сахни, Б. Корте, М.М. Ковалева, В.А. Перепелицы, В.К. Леонтьева.

4/ Исследование целочисленного многогранника задачи: важность данного направления исследований обуславливается возможностью пришнения методов линейного программирования или специфических методов отсечения к решению задач дискретной оптимизации. Изучению целочисленных многогранников конкретных задач посвящены работы Дж. Эдмондса, М. Гретшеля, М. Падберга, В.А. Трубина, В.Н. Шевченко, А.В. Карзанова; основные результаты, полученные в этом направлении, изложены в монографии В.А. Емеличева, М.М. Ковалева, М.К. Кравцова Ы.

Анализ состояния изученности задачи разрезания графа в рамках указанных направлений позволяет сделать следующие выводы: у а/ не для всех практически важных вариантов ЗРГ определена их вычислительная сложность и построены точные алгоритмы решения; б/ решение ЗРГ осуществляется в основном эвристическими мз-тодами, не подвергавшимися еще теоретическое анализу; в/ практически не изучен целочисленный многогранник ЗРГ.

Целью предлагаемой диссертации является дальнейшее исследование ЗРГ как задачи дискретной оптимизации, направленное на ликвидацию указанных пробелов.

В первой главе диссертации рассматривается один из наиболее просто формулирующихся и одновременно практически важных вариантов ЗРГ - задача разрезания графа без ограничений тал{K/V, W,p) 'Р eJj где J - совокупность всех разбиений множества А/ . В § I главы I приводятся практические задачи, сводящиеся к данной постановке: задача классификации с порогом существенности /В,А. Купе ршт ох, Б. Г. Миркин /29/ /, построение медианы Кемэни - Смелла для разбиений Д.Б. Черный

Ы /, задача распознавания /классификации/ по эталонам Л*.Л. Куперштох Ы /\ описывается предложенный в работе /зо7 локально-оптимальный алгоритм решения ЗРГ. В месте с тем отмечается недостаточная теоретическая изученность ЗРГ^, отсутствие точных методов решения.

Обозначим "распознающий" вариант ЗРvO, в котором для некоторого фиксированного-5Z требуется найти разбиение ^р , такое, что K/\/,W,p)1li2 , через . в § 2 главы i показано теорема 1.2.1/, что зрг 0~£t ~ АР- полная в сильном смысле. Из теоремы вытекают следствия о NP — трудно сти ЗРГ О и об отсутствии для нее вполне полиномиальной приближенной схемы.

В § 3 главы I изучается многогранник ЗРГ^ . Известна следующая формулировка ЗРГ 0 в терминах булевского линейного программирования: h п mox^l^^uijocij /0.2/

У

OCij « сXjt , оХй =/ C,J= /,/7 /0.3/

Ту * f+OCcj /(/0.4/

Г? у 7 V "" /0.5/ оГо - целое /0.6/

Легко видеть, что множество решений системы /0.3/ - /0.6/ совпадает с множеством характеристических матриц всех разбиений

Х(Л

Выпуклую оболочку этого множества Jr ~ C&/7vX(^назовем многогранником ЗРГ О ; через Л обозначим многогранник релаксированной задачи /0.2/ - /0.5/. Для произвольного множества и вершины АеШ L} - звездой назовем /7 - вершинный граф с множеством ребер f (hji) • L 6LJ ; через Лобозначим его матрицу смежности. Доказано, что при ILI^^S матрица ~js~JI(/( Ь) есть вершина в м.

Охарактеризованы грани М , отсекающие нецелочисленные вершины такого типа.

УТВЕРЖДЕНИЕ 1.3.2. Любой /*/, L} - звезде можно поставить в соответствие неравенство: У

L JCAi < 1+ zZ.^ и} О* /0.7/ отсекающее вершину £ J(k\L) в м и определяющее bП~1') ее вершину г JllnyL)^ грань многогранника

М /здесь /77 ~ Далее изучаются свойства многогранников <d/t , получаемых из

JJ с помощью отсечений ввда /0.7/ при /ич ; опровергается гипотеза: ^JJ =JJt при некотором £ . Более того, на основании результата Р. Карпа, К. Пападимитриу М с учетом Рmm ПОЛНОТЫ опровергается возможность обозримого описания множества граней многогранника М*.

В параграфе 4 главы I предлагается точный метод типа ветвей и границ для решения ЗРГ 0 , основанный на схеме последовательного объединения подмножеств в разбиении, начиная с травиального разбиения множества А/ на /7 одноэлементных подмножеств. В ходе разработки метода решалась проблема построения верхних оценок для функционала суммы внутренних связей, представляющая и самостоятельный интерес. Очевидной верхней оценкой для

ЛЛ/М/у) является сумма

S М положительных весов ребер графа С- . В данной работе нами строится семейство оценок, более точных, чем ■S1W) . Пусть

4 =Z maafщ,,цк, 0], dj'Г (maacf 1М--^1б(п-г), щ 4 -c£jp(n-8

Матрицу назовем замыканием матрицы к/ Показано, что величина T(W) =][(W) +S ftV^Jявляется верхней оценкой суммы внутренних связей, причем и равенство достигается на весьма специальном классе матриц. Более того , справедлива

Теорема 1.4Л. Цусть В/,В*,.,3s - последовательность двадратных матриц порядка /7 , в которой Bi^'Bi-y . Тогда для любого У величина

-izm+m) является верхней оценкой суммы внутренних связей тмр) причем

IiMW^IJ/VMh. <IMW)-W)

Метод решения ЗРГ (J , использующий верхнюю оценку

TfW), реализован на языке ФОРТРАН 17 ВС ЭВМ и апробирован на реальных данных. Программа включена в ППП ДИСПР0-3, разработанный в ИК АН УССР и предназначенный для решения общих и специальных задач дискретного программирования.

Вторая глава диссертации посвящена методам решения ЗРГ с ограничениями. В § I приведены основные известные результаты о вычислительной сложности задач этого класса, в § 2 главы I изучаются некоторые практически важные классы эвристических алгоритмов решения ЗРГ. При этом применяется комбинированный подход, сочетающий определение "хороших" в смысле кластерного анализа свойств алгоритмов с построением оценок наихудшего поведения. Рассматриваются следующие алгоритмы:

I/ Последовательно-объединяющие /ПО/ алгоритмы /агломерационные алгоритмы

На начальном шаге множество /I/ рассматривается как набор из /7 одноэлементных подмножеств. На каждом последующем шаге в уже построенном разбиении уО j €У J по определенном правилу выбирается пара подмножеств Ж и Ai и производится их объединение. Если получено допустимое разбиение, а дальнейшее объединение подмножеств приводит к ухудшению функционала, либо к нарушению допустимости - работа алгоритма завершается.

2/ Последовательно-дихотомические /Щ/ алгоритмы /дивизииные алгоритмы [а£.] /: на начальном шаге рассматривается вырожденное разбиение с единственным подмножеством, совпадающим с А/. На каждом последующем шаге производится выбор некоторого подмножества A/s в уже построенном разбиении и его дихотомия - разбиение на две части A/s и A/s . Если получено допустимое разбиение, дальнейшая дихотомия которого либо ухудшает функционал, либо нарушает допустимость - работа алгоритма завершается.

3/ Обшнно-итерационные /СМ/ алгоритмы [zl : задано некоторое исходное разбиение. На каждом шаге /итерации/ алгоритма производится попарный обмен вершинами из различных подмножеств, приводящий к увеличению суммы внутренних связей. Если дальнейшее увеличение функционала за счет обмена вершин невозможно - работа алгоритма завершается.

Пусть щ!ЦМН/МН)) - средний вес внутренних связей в подмножестве bfkJ(/7s/7t) - средний вес связей подмножеств

ОТ /здесь и далее г/с

ОПРЕДЕЛЕНИЕ П.2.1. Разбиение называется отделимым, если существует такое число /порог отделимости/,

ЧТО ff/Vs, МЫ для любых 6, S, teJ .

Отделимое разбиение компактно в среднем в смысле Ы. каждое его подмножество - кластер в смысле /зо/ .Вводится еще один ослабленный вариант свойства отделимости:

ОПРЕДЕЛЕНИЕ П.2.2. Разбиение Р= {Щназывается отделимым в среднем, если средний вес его внешних ребер не превышает среднего веса внутренних ребер

1МКр)> ЕШМ4 jt ipv > tpr

Здесь Jj(p)число внутренних /внешних/ ребер в разбиении р . Алгоритм последовательного объединения, в котором выбор пары

МЛ на каждом шаге производится с соблюдением условия:

Ws ош т, утмм)*ш, назовем П01 - /соответственно П02 -/ алгоритмом.

Алгоритм последовательной дихотомии, в котором правило выбора подмножества М и метод дихотомии обеспечивают на каждом шаге выполнение условия: назовем ГЩ1 - алгоритмом.

В диссертации приведены примеры практических алгоритмов из указанных классов. Доказано, что на каждом шаге своей работы П01 - алгоритм порождает отделимое разбиение /Георема П.2.1/, П02 и ЦЦ1 - алгоритмы - отделимые в среднем разбиения /Георемы П.2.2, П.2.3/. Для СМ - алгоритмов установлена отделимость в среднем результирующего разбиения в случае равномощности подмножеств исходного разбиения /Георема П.2.4/. На основании этих результатов построены оценки наихудшего поведения П01 -, П02 -, 1Щ1 - и Ш - алгоритмов для конкретных вариантов ЭРГ.

Независимым от предьщущего изложения путем построены оценки наихудшего поведения для еще одного класса алгоритмов последовательного объединения /ПСЗ/, в котором на каждом шаге выполняется условие: «

I ,ш ЖФ^пфш^Мр) где И//УК, М / / ЪУй - суммарный вес связей подмножеств А/ к/ £€A/s к€А/*

Vs,/vt • Отметим, что к данному классу принадлежит известный алгоритм "максимальной связи" Ы.

В заключительной части § 2 устанавливается, что свойства и оценки для П02 -, ПОЗ - и 1Щ1 - алгоритмов решения ЗРГ естественным образом вытекают из более общих результатов для следующей задачи максимизации линейной формы на множестве /0,1/ -векторов: дано множество Д С ($,1} и весовой вектор C=(e,,Cs,. .Найти где (c,Jc)=Z.

Ос <ЭСс - скалярное произведение. Введем на множестве /77 -мерных векторов естественное упорядочение: ET^J/ тогда и только тогда, когда eXi //с при С - /,/77 . Пусть

- некоторое множество, включающее в себя Д , flf*") .w нулевой вектор и и единичный вектор / . Будем говорить, что вектор у покрывает оХ в D /запись/^^«Z*/, если У><х и не существует D , для которого^>^"^г. Алгоритм, генерирующий последовательность векторов такую, что , <Х*€ ${/(= т, ос покрывает сЗГ* в D , и *ХГ€ Д - эвристическое решение /0.8/, назовем алгоритмом подьема в D .

Пусть JD'. DxD~*ft\ - симметричная вещественная функция на множестве пар векторов из D , интерпретируемая как расстояние /хотя и не являющаяся, вообще говоря, метрикой/. Алгоритм подьема в D назовем j3 - разумным, если на каждом его шаге выполняется неравенство:

Для таких алгоритмов в диссертации предложена схема получения оценок вида: (С/у - некоторая константа/. В частности, если JJ - метрика, то имеет место следующая оценка /Георема П. 2.5/ ,1 у с, а7 ^ yjo^j^pf Cl /0-9/

Алгоритм, генерирующий последовательность , такую, что JC*€ D(A покрывает а:**' в Z? , и <Xfe/\ , назовем алгоритмом спуска в D . Определен J) - разумный алгоритм спуска, в котором на каждом шаге выполняется условие: и доказана справедливость оценки /0.9/ для полученного с его помощью решения /Теорема П.2.б/. Показано, что для некоторого класса множеств D JD - разумный алгоритм подьема есть обобщение традиционного жадного алгоритма на "системах независимости"; при этом оценка /0.9/ и известная оценка Хаусмана - Корте Ы взаимно несводимы, и, таким образом, дополняют друг друга. Как уже отмечалось, ЗРГ есть частный случай задачи /0.8/. При этом, как показано в § 2, ПО - алгоритмы есть алгоритмы подьема в ДЦ - алгоритмы есть алгоритмы спуска в хф. а теоремы П.2.2-3 есть следствия теорем П.2.5-6. СЦенка для ПС8 - алгоритма получена путем непосредственного применения предложенной общей схемы.

В § 3 главы: < П цредлагаются точные методы типа ветвей и границ для решения двух прикладных задач типа разрезания графа: задачи сегментации программы и задачи классификации по матрице расстояний /обе задачи

А/Р

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

Задача сегментации программы формулируется следующим образом /27, 71, 387 :

M/?£fMW/>)

Здесь W - матрица частот взаимодействия программных единиц, - обьем памяти, занимаемой I -й единицей, V -общий обьем оперативной памяти ЭВМ.

Метод решения данной задачи основан на схеме последовательного объединения подмножеств, уже использовавшейся при решении ЗРГ0 . Верхние оценки суммы внутренних связей определяются путем релаксации целочисленной линейной постановки данной задачи, которая может быть получена из соответствующей постановки ЗРГ добавлением ограничений:

2l viactj ^1/ /,/7 ; /оло/

Так, путем внесения ограничений /ОЛО/ с множителями Лаг-ранжа

Л* в функцию цели и отбрасывания ограничений транзитивности /0.4/ строится следующая оценка

I, Щ Wl=/m/?{5 ШЛМ1-1 -Ас

Здесь ы(Х)у =2Jlj ^ Ш для подсчета могут использоваться методы негладкой оптимизации

В результате рассмотрения релаксированной задачи /0.2/, /0.3/, /0.5/, /ОЛО/получается более простая оценка где

IMW-iL^ s>

Yc ~махZf. щ осу при ограничениях ^ п f тру "

О ^ еГу < / , ОС с с = / у = /,/9

Предложенный алгоритм реализован в виде программы на языке ФОРТРАН 1У ЕС ЭВМ; проведен вычислительный эксперимент на случайно сгенерированных данных.

Задача классификации по матрице расстояний формулируется следующим образом /з, 377:

ШлЩМ. к//?) +F(r(pd ■ г(р) }

Здесь W - матрица расстояний; - сумма расстояний между точками внутри классов, (') - возрастающая функция, выполняющая роль штрафа за увеличение числа подмножеств.

Данная задача рассматривалась в работе И.М. Макарова, В.З. Ямпольского /зт/, где для определения ее оптимума предлагалось решать feax jyp - трудных задач вида: min{W, У,p)'-r(phr} при Г~ frtjojc. Но /^«лг может существенно превышать число подмножеств в оптимальном для исходной задачи разбиении, поэтому такой подход является чрезвычайно трудоемким. В диссертации предложен алгоритм непосредственного решения рассматриваемой задачи, не требующий априорного знания числа подмножеств.

Идея алгоритма такова: на начальном шаге выбирается некоторая вершина I, и закрепляется за подмножеством А/* . На очередном Ji -м шаге выбирается незакрепленная вершина 6Л и определяются верхние и нижние оценки вариантов ее закрепления за одним из непустых подмножеств A/j (j~ У,/*) , либо /при ^ /snох / за еще пустым подмножеством Выбирается вариант с наименьшим значением нижней оценки, верхние оценки используются для модификации рекорда и отсечения бесперспективных вариантов, и процесс ветвления продолжается.

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

Предложенный алгоритм реализован на языке ФОРТРАН 1У ЕС ЭВМ. Программа апробирована на ряде тестовых примеров и включена в ППП ДИСПРО - 3.

В третьей главе рассматриваются некоторые взаимосвязанные вопросы теории следующей общей задачи, частными случаями которой являются ЗРГ, задача коммивояжера и многие другие задачи оптимизации на графах:

ВЫБОР ОПТИМАЛЬНОГО ПОДГРАФА. Дан полный взвешенный ориентированный граф Кп с матрицей весов ребер U/~ f , задан некоторый граф & или набор графов trv . Выбрать в к: подграф, изоморфный Lr или одноэдг из графов &f, Qg , . 7 Gi > с максимальным суммарным весом ребер.

Пусть /соответственно ^jr*, , GJ/ - множество матриц смежности подграфов, изоморфных Сг /соответственно одноыу из графов G,,Сга,Gr* /. Тогда данная задача, именуемая далее

ЗВП (&) или ЗВП (Сг*, Gk, ., Gv), формируется как частный случай /0.8/:

77C/a:f(W,X)/X € M(Gr, Ge,., GJf /V\/1 ///)

Данная задача называется константной, если IVJ7A)~(w,j) для любых

Любое решение константной задачи является оптимальным, однако для доказательства оптимальности в методе ветвей и границ может потребоваться полный перебор. К описанию условий константности сводятся также некоторые вопросы общей теории задач оптимизации на графах. Так, рассматривая эквивалентные преобразования весовой матрицы W в |д/ , при которых оС для любого XefJ(G,,G*> оС и J3 - некоторые константы/, Ленстра и Ринноу Кан Ы показали, что VJ1а/~*~\л/ , где W - матрица константной задачи, (W,X/ot для ляИ$ого X ^//CG^ - Csv) . Далее, существует достаточно очевидная связь между условиями константности и описанием аффинной оболочки ее многогранника: ортогональность весовой матрицы к указанной Аффинной оболочке является необходимым и достаточным условием константности задачи. /Утверждение Ш.1.2/. Все это объясняет интерес к изучению условий константности конкретных оптимизационных задач.

В работах Д.А. Супруненко /бб/, В.К. Леонтьева

Б. Я.

Габовича

Ы, А.Х.Г. Ринноу Кан, Дж.К. Ленстры Ы описаны условия константности для задачи о назначениях, задач одного и нескольких коммивояжеров, а также некоторых других подобных задач. В предлагаемой диссертации изучаются условия константности задач вида ЗВП (Сг) . Отметим, что полученные результаты служат базой для описания условий константности ЗВП (Gv) , так как последняя является константной тогда и только тогда,когда каждая из задач ЗВП (CrJ , ЗВп/бУ , ЗВП а константна.

В § 2 главы Ш рассматривается ЗВП (О , где Gr «. направленный /строго ориентированный/ граф. Устанавливаются некоторые вспомогательные результаты из линейной алгебры. На их основании с учетом связи между условиями константности и аффинной оболочкой многогранника доказано /Георема Ш.2.2/, что для любого направленного графа, за исключением графов специального вида из константности ЗВП (Сг) следует существование векторов ^ = (о(.гу d„) и j таких» 470 Щ = di +J3; при любых 6. Установлено, что указанное разложение элементов матрицы W является необходимым и достаточным условием константности ЗВП (Сг) тогда и только тогда, когда Сг регулярный граф, не являющийся турниром /Георема Ш.2.3/. Данный результат обобщает известные результаты для задач оптимизации на подстановках.

В § 3 рассматривается симметричная ЗВП (С) , в которой граф Сг - неориентированный, матрица ]// - симметрическая. Доказана:

Теорема Ш.3.1. Для константности симметричной ЭВП (Сг) необходимо и достаточно, чтобы весовая матрица задачи W удовлетворяла следующим условиям: а/ если Сг - звезда или ее дополнение, то для некоторой в константы 7 t

Щ /7 б/ если Сг - регулярный граф, то ЪГ^ где

Л)

- некоторый вектор; в/ в остальных случаях - равенства всех элементов матрицы V/ На основании данной теоремы получены следствия для симметричной задачи одного и нескольких коммивояжеров, некоторых вариантов ЗРГ и других известных задач оптимизации на графах.

Основные результаты диссертации опубликованы в работах /и - 15, 5б7.

При ссылках внутри диссертации принята двойная нумерация параграфов /глава - параграф/, тройная нумерация разделов /глава - параграф - раздел/ и теорем /глава - параграф - номер теоремы/. Последнее относится также к леммам, утверждениям и определениям. Ссылки внутри главы даются без указания номера последней.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Гильбурд, Михаил Марксович

106 ЗАКЛЮЧЕНИЕ

Сформулируем в краткой форме основные выводы и результаты, полученные в данной работе: графа без ограничений.

2/ Описан новый класс граней максимальной размерности целочисленного многогранника задачи разрезания графа без ограничений; получения обозримого описания всех граней максимальной размерности этого многогранника.

3/ Построен точный алгоритм решения задачи разрезания графа без ограничений, основанный на эффективной схеме последовательного объединения подмножеств и использующий нетривиальные верхние оценки функционала. Программа, реализующая указанный алгоритм, включена в ППП ДИСПРО-3.

4/ Выделены классы практически важных эвристических алгоритмов решения задач разрезания графа, обладающих "хорошими" с содержательной точки зрения свойствами. Для указанных классов алгоритмов построены оценки наихудшего поведения; описана весьма универсальная схема получения оценок такого вида для произвольных линейных задач оптимизации на множестве /0,1/ - векторов.

5/ Построены точные алгоритмы решения двух прикладных задач типа разрезания графа: задачи сегментации программы и задачи классификации по матрице расстояний. Программа, реализующая алгоритм решения последней задачи, включена в ППП ДИСПРО-З.

6/ На основании линейно-алгебраического подхода, использующего соответствие между аффинной оболочкой целочисленного многогранника задачи и условиями ее константности, описаны условия константности для широкого класса задач выбора оптимального под

I/ Доказана сильная /Vr - трудность задачи разрезания доказана невозможность /в предположении, что графа, включающего в себя задачу о назначениях, задачи одного и нескольких коммивояжеров, симметричные варианты задачи коммивояжера, а также задачу разрезания графа с фиксированными размерами подмножеств.

Список литературы диссертационного исследования кандидат физико-математических наук Гильбурд, Михаил Марксович, 1985 год

1. Абрайтис Л.Б. Алгоритм для определения максимально связанных наборов элементов. - Автоматика и вычислительная техника, 1970, № 5, с. 40-47.

2. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В. А. Автоматизация проектирования ЭВМ. М.: Советское радио, 1978. - 269 с.3* Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика, 1974. - 240 с.

3. Базилевич Л.А. Моделирование организационных структур. Ленинград: Изд-во ЛГУ, 1978. - 159 с.

4. Балаш Э. Аддитивный алгоритм для решения задач линейного программирования с 0-1 переменными. В кн.: Кибернетический сборник. - М.: Мир, 1969, вып. 6, с. 24-54.

5. Берштейн Л.С., Селянкин В.В. О минимальном разрезании графов со взвешенными ребрами. Электронная техника. Сер. 9. АСУ, 1976, вып. 4 /20/, с. 96-105.

6. Воронин А.Б., Першин О.Ю. Разбиение сети на минимально связные части. Автоматика и телемеханика, 1984, № 4, с. 128-138.

7. Визинг В. Г. Значения целевого функционала в задачах очередности, мажорируемые средним значением.-Кибернетика, 1973, № 5,с. 76-78.

8. Габович Е.Я. Константные задачи дискретного программирования на множестве подстановок. Кибернетика, 1976, № 5, с. 128-134.

9. Гайков Н.Е. Разрезание графа на подграфы с фиксированным числом вершин. Известия АН БССР. Серия физико-математических наук, 1977, № 2, с. 21-30.

10. Гильбурд М.М. Об условиях константности одного класса задач дискретного программирования. В кн.: Системное моделирование экономических процессов и АСУ. - Киев: Изд-во ИЭ АН УССР,1979, с. 68-71.

11. Гильбурд М.М. Об условиях константности одного класса задач дискретного программирования. Редакция журнала "Известия АН СССР. Техническая кибернетика". М., 1980. - 15 с. /Статья депонирована в ВИНИТИ 24 марта 1980 г., № IIII-80 Деп./.

12. Гильбурд М.М., Кухар Р.Б. Об одной задаче разрезания, возникающей при техническом проектировании. Автоматика и телемеханика, 1982, № 3, с. 106-112.

13. Гильбурд М.М. Об эвристических методах решения задачи разбиения множества взаимосвязанных обьектов. Автоматика и телемеханика, 1984, № I, с. I07-113.

14. Горинштейн JI.JI. О разрезании графов. Известия АН GCCP. Техническая кибернетика, 1969, № I, с. 23-32.

15. Грешнев С.Н. Многогранник задачи о № вершинном подграфе полного графа. - Журнал вычислительной математики и математической физики, 1984, т. 24, № 5, с. 790-793.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

17. Дюран В., Оделл П. Кластерный анализ. М.: Статистика, 1977. - 127 с.

18. Елисеева И.И., Рукавишнников В.О. Группировка, корреляция, распознавание образов. М.: Статистика, 1977. - 143 с.

19. Емеличев В.А. К задачам дискретной оптимизации. Доклады АН СССР, т. 192, 1970, № 5, с. II3I-II33.

20. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многранники, графы, оптимизация. М.: Наука, 1981. - 344 с.

21. Журавлев Ю.И. Локальные алгоритмы вычисления информации. I. -Кибернетика, 1965, №1, с. 12-19.

22. Карп P.M., Сводимость комбинаторных задач. В кн.: Кибернетический сборник. - М.: Мир, 1975, с. 16-38.

23. Кемени ДД., Снелл Дж. Кибернетическое моделирование. М.: Советское радио, 1972. - 192 с.

24. Ковалев М.М. Метод частичных порядков. Доклады АН БССР, 1980, т. 24, № 2, с. 69-75.

25. Коган Я. А., Файнштейн И. А., Шейнман М.В. Исследование и оптимизация систем программного обеспечения. Автоматика и вычислительная техника, 1976, № 2, с. 55-63.

26. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 482 с.

27. Куперштох В.Л., Миркин Б. Г. Об одной задаче классификации. -В кн.: Математические методы в экономике. Новосибирск: Наука, 1968, с. 59-70.

28. Куперштох В.Л., Миркин Б.Г., Трофимов В.А. Оумма внутренних связей как показатель качества классификации. Автоматика и телемеханика, 1976, № 3, с. I33-I4I.

29. Куперштох В. Л, Применение теории потоков в сетях для задач классификации. В кн.: Проблемы анализа дискретной информации. Ч. I, Новосибирск, изд. ИЭ и ОПП СО АН СССР, 1975,с. 46-66.

30. Левин А.А. Универсальные задачи перебора. Проблемы передачи информации, 1973, 9, № 3, с. II5-II6.

31. Леонтьев В.К. Дискретные экстремальные задачи. В кн.:^тоги науки и техники, сер. Теория Вероятностей. Математическая статистика. Теоретическая кибернетика,т. 16 /Йтоги науки и те^ники/. -М.: ВИНИТИ, 1979, с. 39-101.

32. Леонтьев В.К. Устойчивость задачи коммивояжера. Журнал вычислительной математики и математической физики, 1975, т. 15, № 5, с. 1298-1300.

33. Литтл Дж., Мурти К.Г., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере. Экономико-математические методы, 1965, № I, с. 94-107.

34. Лумельский В.Я. Группировка параметров на основе квадратной матрицы связи. Автоматика и телемеханика, 1970, № I, с. 133143.

35. Макаров И.М., Ямпольский В.З. Алгоритм решения одной задачи классификации. В кн.: Математические методы исследования и оптимизации систем. Киев, ИК АН УССР, 1971, с. 23-29.

36. Максимзнко А.В., Щерс А.Л. Алгоритм сегментации машинных программ. Автоматика и вычислительная техника, 1976, № 5, с. 5260.

37. Мацевко Н.С., Нудельман М.С. Модель объединения предприятий для обслуживания их в кустовых ВЦ. Управляющие системы и машины, 1977, № 3, с. 4-И.

38. Методы разбиения схем РЭА на конструктивно законченные части. /Под ред. К.К. Морозова. М.: Советское радио, 1978. - 136 с.

39. Миркин Б.Г., Вальтух К.К., Павлов В.А., Трофимов В.А. 0 применении методов качественного анализа данных к исследованию динамики народного хозяйства. В кн.: Прикладные народнохозяйственные модели. - Новосибирск: Наука, 1981, с. 5-15.

40. Миркин Б.Г. Анализ качественных признаков и структур. М.: Статистика, 1980. - 319 с.

41. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. 1,2.- Кибернетика, 1965, № I, с. 45-55, № 2, с. 85-89.

42. Петренко А.И., Тетельбаум А.Я. Приведение задач конструкторского проектирования электронных устройств к бивалентному программированию. Кибернетика, 1976, № 3, с. 64-69.

43. Пучиньян В.К., Шеин П.Д., Штейн М.Е. Задача оптимального разбиения графа и компоновка устройств ЦВМ. В кн.: Системы распределения ресурсов на графах. - М.: Изд-во ВЦ АН СССР, 1970, с. II8-I25.

44. Розин Б.Б. Применение методов многомерной классификации при анализе результатов экспертного опроса. В кн.: Статистические методы анализа экспертных оценок. - М.: Наука, 1977,с. 83-95.

45. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. - 468 с.

46. Рубинштейн М.И. Задача синтеза иерархических систем управления. -В кн.: Согласованное управление. -М.: Наука, 1975,с. 78-81.

47. Рыжков А.П. Алгоритм разбиения графа на минимально связные подграфы. Известия АН СССР, сер. Техническая кибернетика, 1975, № 6, с. 122-128.

48. Сарванов В.И. 0 многогранниках, связанных с оптимизацией на подстановках. Минск, 1977. 36 с. /АН БССР, Институт математики, препринт 7/23/.

49. Сачков В.Н. Комбинаторные методы дискретной математики. М.: Наука, 1977. - 320 с.

50. Селютин-В.А. Машинное конструирование электронных устройств. М.: Советское радио, 1977. - 384 с.

51. Сергиенко И.В., Лебедева Т.Г,, Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наукова думка, 1980. - 273 с.

52. Сергиенко И.В., Каспшицкая М.Ф. Некоторые вычислительные аспекты задачи кластеризации. Кибернетика, 1983, № 5, с. 1-5.

53. Супруненко Д.А., Метельский Н.Н. Задача о назначениях и минимизация суммы линейных форм на симметрической группе. Кибернетика, 1973, № 3, с. 64-69.

54. Трубин В. А. Гильбурд М.М., Дерюгин В.Н., Чумаков Б.М., тарифов Ф.А. Теоретическое и экспериментальное исследование некоторых комбинаторных задач» Киев, 1984. 46 с. /АН УССР, Ордена Ленина Институт Кибернетики, препринт 84-14.

55. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

56. Черный Л.Б. 0 связи метода пространства разбиений с известными методами анализа данных. В кн.: Вопросы анализа сложных систем. - Новосибирск: Наука, 1974, с. 84-89.

57. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 200 с.

58. Grot she/ ft, Pach^e/yM Llneare Charec/ertsle-ranger? von Trare/йп^ Safesman Рго//еп7ет?.~

59. Z Oper. Res., Jt, W7, £1, A/°-1fp

60. Rarp R.M., Pap a ctim /пеа С A fa Rineor charocfenzaRo/psof с (7/7?/с no torla/ eptcmza/бол preJ/ems. SI J/1 У оагт?а/ of Cmputing, uR .

61. M.Roontz W. О /ranch ат?с/ towc/c/ustea/7f o/pm/hm

62. ГОСУ~ .РСТВЕННЬШ ФОНД АЛГОРИТМОВ II ГШШ'ЛММ

63. СКТБ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ИНСТИТУТА КИБЕРНЕТИКИ АН УССР

64. УКРАИНСКИЙ РЕСПУБЛИКАНСКИЙ ФОНД АЛГОРИТМОВ И ПРОГРАММ1. УкрРФАП .252207, г. Киев-207, проспект 40-летия Октября, 142/144, тел. 66-13-47

65. Институт кибернетики имени В.М.Глушкова АН УССР-i-от—-198.г.11. СПРАВКА

66. Представленное Вами программное средство /с реализованнымв. нем алгоритмом/ "Пакет прикладных программ для решения на

67. Согааоно п.27 Положения о Государственном фонде алгоритмов « программ, указанная работа приравнивается к опубликованной.1. Руководитель УкрРФАП1. С.А*Дорожки»

68. ИК АН УССР. 3ак.443. Тир. 150.1984.