Содержание к диссертации
Введение
ГЛАВА 1. Многокритериальная задача покрытия предфрактальных графов простыми цепями 21
1.1. Фрактальные и предфрактальные графы 21
1.2. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К1) 26
1.3. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К2) 29
Выводы 34
ГЛАВА 2. Алгоритмы с оценками построения покрытий простыми цепями на предфрактальном графе 35
2.1. Разработка и исследование полиномиальных алгоритмов построения покрытия К, 35
2.1.1. Алгоритмы а1 построения покрытия L -ранговыми цепями длины один 35
2.1.2. Алгоритмы а2 построения покрытия L-ранговыми цепями длины два 49
2.1.3. Алгоритмы а3 построения покрытия L-ранговыми цепями длины три 54
2.2. Разработка и исследование полиномиальных алгоритмов построения покрытия К2 58
2.2.1. Алгоритм построения остовного дерева минимального веса
2.2.2. Алгоритм выделения наибольших максимальных цепей 67
Выводы 79
ГЛАВА 3. Распознавание предфрактального дерева с затравкой простая цепь 81
3.1. Алгоритм распознавания предфрактального графа с затравкой цепь длины один (ребро) 82
3.2. Алгоритм распознавания предфрактального графа с затравкой простая цепь длины (ребер) 90
Выводы 98
Заключение 99
Литература 100
Приложение 111
- Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К1)
- Алгоритмы а1 построения покрытия L -ранговыми цепями длины один
- Разработка и исследование полиномиальных алгоритмов построения покрытия К2
- Алгоритм распознавания предфрактального графа с затравкой простая цепь длины (ребер)
Введение к работе
Задачи о покрытиях графов представляют большой интерес как сами по себе, так и в связи с многочисленными приложениями. Список таких задач практически неисчерпаем, и в качестве примера достаточно отметить такие важные как в теоретическом, так и в практическом отношении задачи, как: задачи о составлении расписаний, задачи о гамильтоновых циклах и цепях и тесно связанная с ними задача коммивояжера.
В этом обширном и быстро развивающемся направлении теории графов важное место занимают задачи о покрытиях графов цепями и циклами. Характерной особенностью этого класса задач, во многом объясняющей проявляемый к ним интерес, является то, что наряду с известными содержательными интерпретациями, задачи этого класса наиболее естественно возникают из задач, связанных с организацией транспорта, а также при создании системы автоматизированного проектирования электронно-вычислительной аппаратуры (САПР ЭВ А) [1].
В настоящее время существует большое количество решенных задач о покрытии графов цепями. Перечислим наиболее интересные результаты по ним.
Задача покрытия п-вершинного графа /-вершинными цепями в одно-критериальной постановке решена в [2] для частного случая, когда граф покрывается двухвершинными цепями. К настоящему времени для построения
такого покрытия известен алгоритм с трудоемкостью порядка п элементарных операций [3]. В работе [4] предложены эвристические алгоритмы решения однокритериальных задач покрытия графов, в случае, когда на длины цепей наложены ограничения сверху. Предлагаемый в работе [5] алгоритм
трудоемкости 0(п~) решает частный случай с гарантированным относитель-
ным уклонением, не превосходящем —. Что касается эффективно разрешимых классов задач покрытия графов гамильтоновыми цепями, то наиболее полно эти результаты представлены в [6]. Задача покрытия кратчайшими пересекающимися цепями достаточно подробно исследована в [7], где рассматривается оценка числа цепей в зависимости от типов графов. Но эта задача не исследовалась в оптимизационной постановке, и не имеет конкретного алгоритма построения покрытия для любого графа. В общем случае однокрите-риальная постановка задачи покрытия графа цепями содержит, как частные случаи, NP-трудные задачи [8]: покрытие графа А:-вершинными цепями, в частности, задача нахождения на графе гамильтоновой цепи минимального веса [8]. К последней задаче примыкает задача о гамильтоновых циклах и тесно связанная с ней задача коммивояжера [9-16].
Причем в целом, исследования по задачам покрытия графа носят фрагментарный характер и касаются в основном случая однокритериальных постановок. Покрытие графов цепями в многокритериальной постановке достаточно глубоко исследовались Кочкаровым A.M., Перепелицой В.А. и др. в работах [17-29]. В этих работах рассматривается проблема многокритериаль-ности и предлагается вероятностный анализ алгоритмов [30,31], позволяющих доказывать теоремы о поведении алгоритмов в среднем и асимптотическом поведении.
Однако многие из этих задач моделируемых на графах, состоят из большого числа элементов, причем им присущи свойства фракталов: самоподобие, дробная фрактальная размерность, масштабная инвариантность, а также признаки динамического хаоса в траекториях моделируемого процесса [32-35]. Как только задачи становятся большой размерности, они становятся трудно решаемыми в смысле вычислений, поэтому для моделирования таких задач классические методы теории графов оказываются неэффективными.
Причем, если исследуемая система состоит из большого числа взаимодействующих между собой частей и поведение системы существенно зависит от структуры связей между этими частями, то необходимо учитывать это взаимодействие при построении модели. Таким моделям (объектам) присущ особый вид хаоса, связанный с невозможностью (или сложностью) точного описания всех существующих связей в каждый момент времени. Такой хаос мы будем называть структурным. Системы, в которых наблюдается структурный хаос, хорошо поддаются описанию в терминах фрактальной геометрии.
Оказалось, что фрактальные графы являются подходящим математическим объектом для моделирования структуры сложных систем со структурным хаосом, а размерность таких графов является параметром, обуславливающим поведение системы, что подтверждает важность исследования, как самих фрактальных графов, так и их размерности. И в качестве средства моделирования структурного хаоса предлагается использовать фрактальный граф.
Также заметим, что весьма многочисленный список экстремальных задач [36-40] на графах представляет собой класс TVP-трудных задач с точки зрения дискретной оптимизации. Здесь уместно отметить, что, например, известная задача нахождения (распознавания) гамильтонова цикла становится полиномиально разрешимой на канонических предфрактальных графах с полной затравкой Н = (W,Q) в случае, когда старые ребра не пересекаются.
Аналогичные утверждения справедливы и для других задач из этого списка. Снижение трудоемкости экстремальных задач на предфрактальных графах обусловлено тем, что на этих графах для некоторых задач, наряду со свойством самоподобия, появляется свойство наследственности.
Информация о наличии свойства предфрактальности данного графа является также весьма ценной. Отметим хотя бы такой актуальный вопрос, как
сжатие исходной информации, относящейся к описанию моделируемого объекта. Следует отметить также, что на предфрактальных графах удобно строить и реализовывать параллельные алгоритмы. Таким образом, исследования по фрактальным графам является, несомненно, актуальными.
Предпосылкой возникновения фрактальных и предфрактальных графов, явилось понятие «фрактала». Оно было введено в обращение французским математиком Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, в физике ценность подобных идей была осознана лишь в 70-е годы нашего столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла замечательная книга Б.Мандельброта «Фрактальная геометрия природы» [41]. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаус-дорфа - Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая впоследствии АС. Безиковичем) [32,42-44]. Основой новой геометрии является идея самоподобия [33,41,42]. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда са-моподобны, но тривиальным образом: все кривые являются локально прямыми, а прямая всегда самоподобна. Фрактальная же кривая, в идеале, на любых, даже самых маленьких масштабах не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной [45-47].
Дальнейшее изучение фракталов осуществлялось в рамках нового междисциплинарного подхода - синергетики [45,48-50], где одной из центральных задач являлось моделирование объектов и явлений, которым присущ хаос, т.е. непредсказуемость протекающих в них процессов, отсутствие пространственной регулярности, случайность, рассогласованность поведения составляющих элементов и т.п. С развитием этого направления удалось выявить регулярные законы и закономерности возникновения, казалось бы, на первый взгляд, хаотичных систем, условие протекания непредсказуемых (или, по крайней мере, очень сложных) процессов и явлений, показать фрактальные структуры, лежащие в их основе. Более того, при дальнейшем изучении оказалось, что моделирование многих фрактальных объектов физики, химии, биологии и других дисциплин сводится к составлению автономных систем обыкновенных дифференциальных уравнений, зависящих от параметров [47].
При исследовании дискретных объектов [17-31,36-40,51-54], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [45-47]. Подобные объекты моделируются средствами теории графов [10-16,55-60]. При этом, получаемые модели обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов.
Впервые понятие «фрактальный граф» было введено в работе [33] Мелроузом. Однако используемый Мелроузом и другими авторами иерархический фрактальный граф обладает тем недостатком, что введен с узкой целью, а именно для отражения иерархии связи с учетом варьируемой разветв-ленности [61]. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова A.M. и Перепелицы В.А. [43,44,62-72]. В [62,66,67-71] приведены некоторые результаты исследования свойств фрактальных графов. Некоторые модели на предфрактальных графах по-
строены в [44,64,67,72]. Построению остовных деревьев на фрактальных графах посвящена работа [63]. Результаты исследований задачи о кликах фрактального графа предложены в [65].
Появление фрактальных (предфрактальных) графов является логически закономерным следствием стремления возможно более адекватно моделировать реальные технические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. При этом получение бесконечного фрактального графа из конечного предфрактального графа означает (в терминологии [34,35]) превращение феноменологической модели в асимптотическую. В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф [44,62-72] - это в конечном счете один из способов выявления некоторых качеств моделируемой системы. Поэтому для решения конкретных задач математики, физики, экономики, биологии, строительства, планирования и т.д. используются предфрактальные графы, ранг которых может выступать характеристикой степени приближения строящихся моделей к реальным объектам исследования. При этом, чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих задач экономики, техники, строительства, планирования и т.п. тесно связано с необходимостью моделирования очень сложных и изменчивых во времени структур, состоящих из большого числа элементов, применение классических методов теории графов не всегда представляется возможным в силу своей неэффективности. Применение же теории предфрактальных и фрактальных графов помогает решать задачи, там, где бессильны традиционные подходы.
В диссертационной работе в качестве средства моделирования сложных структур будут использованы фрактальные и предфрактальные графы в
том понимании, в каком оно впервые предложено в работах В.А. Перепелицы и А.М.Кочкарова.
В настоящее время исследования фрактальных и предфрактальных графов ведется в 3-х направлениях:
распознавание фрактальных графов;
вычисление размерности фрактальных графов;
оптимизационные задачи на фрактальных графах.
В направлении 1 исследования получили свою разработку в работах Кочкарова A.M. Представленными в [44] результатами осуществлено выделение и конструктивное обоснование полиномиально разрешимого [8] класса задач распознавания свойства предфрактальности графов, полученных в процессе моделирования специфических объектов дискретной природы.
В работах [43,44] вычислены размерности Хаусдорфа- Безиковича для некоторых типов фрактальных графов.
В направлении 3 исследования проводятся Кочкаровым A.M. и его учениками.
К сожалению, в настоящее время в направлении 3 данная область научных исследований не располагает развитой математической теорией, которая позволила бы эффективно разрешать подобные проблемы.
В диссертации задача покрытия предфрактальных графов простыми цепями рассматривается в многокритериальной постановке [38-40,73-77]. Что позволяет оценить покрытие не одним, а несколькими критериями, которые в силу своей разнородности невозможно адекватно представить в виде одной интегральной целевой функции.
При формулировке многокритериальной задачи оптимизации, как и в классических постановках однокритериальной оптимизации, с помощью системы ограничений или другим способом задается множество X = {х} допус-
тимых решений (альтернатив, вариантов, планов и т.п.), на котором определены целевые функции Fk (х), к = \,т .
При решении многокритериальной задачи требуется по возможности отыскать такое х є X, на котором некоторая часть целевых функций достигала бы минимума, а оставшаяся часть - максимума. Так как критерий Fk (х) —> max всегда можно заменить на - Fk(x) —> min , то в дальнейшем условимся считать, что в многокритериальной задачи оптимизации все целевые функции минимизируются:
FY(x) -»min , F2(x) -> min , ..., Fm(x) —» min ,{m>2).
Многокритериальная задача оказывается разрешимой в вышеуказан-
ном смысле, если будет не пустым пересечение f>\Xk , где Xк - множество
к=\
всех решений х є X, на каждом из которых значение функции Fk(x) достигает минимума.
Проблема многокритериальной оптимизации возникает тогда, когда
f]Xk - 0. В этом случае, какое бы фиксированное х{) є X мы ни взяли в ка-
А-=1
честве искомого решения задачи, найдется другое решение х, є X, на котором значение хотя бы одной целевой функции Fk(xx) меньше, чем Fk(xa). Таким образом, предложить универсальное правило (алгоритм) выбора одного «наилучшего» решения не представляется возможны. Поэтому вопрос определения так называемого векторного оптимума относится к компетенции лица, принимающего решения (ЛПР).
В этих условиях решить многокритериальную задачу - значит найти не одно решение, а множество так называемых Парето-оптимальных решений. Элемент х{) є X называется Парето-оптимальным решением (по критериям
F{(x), ..., F]n(x)), если он удовлетворяет следующему условию: не существует такого элемента у є X, чтобы среди неравенств
Fk(y)
было хотя бы одно строгое.
Иными словами, Парето-оптимальное решение является векторно-неулучшаемым, т.е. его нельзя улучшить ни по одному из критериев, не ухудшив какой-либо другой. Паретовское множество, т.е. множество всех Парето-оптимальных решений многокритериальной задачи оптимизации будем обозначать через X, а его минимальное по мощности подмножество X , удовлетворяющее неравенству:
F(X()) = F(X),rnQ
F(X) = {(F,(x),F2(x)„..,Fm(x)) :хєХ}
будем называть полным решением.
В отечественной и зарубежной литературе [38-40,76,77] можно найти описание различных подходов к решению многокритериальной задачи оптимизации. Зачастую в этих публикациях рассматриваются одновременно две проблемы, которые мы разделяем: нахождение Парето-оптимальных решений и выбор из них наиболее целесообразного решения, называемого векторным оптимумом.
Рассмотрим наиболее распространенные методы нахождения векторного оптимума.
I. Свертка [38,54,73]. При этом подходе искомым векторным оптимумом объявляется такое решение, на котором достигает минимума единственная функция - свертка исходных целевых функций. Чаще всего она определяется в виде суммы:
S(x) = ZhkFk"(x),
А-=1
где Fk(x)- нормированное значение функции Fk(x), hk- коэффициент отно-
сительной важности к-ой. целевой функции, hk > 0, ^hk = 1.
Нормирование функций Fk (х), необходимо для приведения их к одному измерению, осуществляется, например, согласно правилам:
Fk" (х) = -L Fk (х) или F (х) = АФ-,
ак Ак - ак
где Ак = max Fk (х), ак = min Fk (х).
хеХ хеХ
Иногда свертку определяют в виде произведения Р{х) = Y\ Fk (х). Та-
к=\
кая форма свертки наиболее приемлема для постановок типа задач надежности, в которых функции Fk(x) означают вероятность отказов или вероятность безотказной работы.
Подробный анализ многокритериальных задач с помощью сверки наряду с ее привлекательными свойствами (простота, возможность сведений противоречивой многокритериальной постановки к классической однокрите-риальной задаче и др.) выявил ряд существенных недостатков. Основные из них следующие:
Возможны случаи, когда свертка принимает одно и то же значение для большинства Парето-оптимальных решений. Иначе говоря, свертка не всегда правильно отражает относительную важность тех или иных критериев, которая задается путем присвоения различных значений коэффициентов относительной важности.
Существуют такие наборы целевых функций F{(x), ..., Fm(x), что свертка не достигает минимума ни при каких значениях х є X . Это означает, что некоторые интересные для ЛПР решения в принципе нельзя найти с помощью свертки.
Этих недостатков удается в некоторой степени избежать, если вместо линейной свертки S(x) использовать функцию следующего вида:
т -
f\x) = [Z(hkFkn{x)YY,
к=\ где S > 1 .
II. Нахождение лексико-графического [38,78] оптимума.
При этом подходе необходимым условием получения приемлемого решения многокритериальной задачи является ранжирование (линейное упорядочивание) критериев Fk(x), к = \,т, по важности. Для ранжирования по важности критериев наиболее изученным является случай, когда искомое решение является лексико-графическим Парето-оптимальным решением [38,78]. Поиск лексико-графического Парето-оптимального решения осуществляется по правилу: добивайся улучшения по более важному критерию за счет любых потерь по всем остальным менее важным критериям. Это правило, в частности, означает, что для любой пары упорядоченных критериев Fk(x) и F/(x) один из них в «бесконечное число раз» важнее другого.
III. Введение метрики в пространстве целевых функций [38].
Естественно, что в случае, когда все минимумы min Fk(x) = ак , к = \,т
достигаются при одном и том же значении х0, многокритериальная задача решена однозначно. В общем случае этого, конечно же, ожидать нельзя, и тогда напрашивается такое определение векторного оптимума xQ, для которого вектор F0 (х()) = (Fj (л:()), F2 (- ),, Fm (х())) наименее удален от вектора
Иными словами, в пространстве целевых функций Fk(x), к-\,т, определяют точку а, которую называют точкой «абсолютного минимума». При этом подразумевают, что расстояние от абсолютного минимума до всякой
точки F(x) є Rm берется с учетом относительной важности целевых функ-
ций Fk (х). Таким образом, получается функция, являющаяся улучшенным вариантом свертки
Очевидно, что при этом подходе все числа ак должны быть положительными.
Заметим, что оптимуму, на котором достигается минимум функции /(х), в значительно меньшей степени присущи перечисленные выше недостатки свертки [38].
IV. Численные методы построения Парето-оптимальных решений [79].
При этом подходе последовательно фиксируются значения целевых функций, после чего каким-либо приемлемым методом решается задача од-нокритериальной оптимизации для оставшейся целевой функции Fk (х). Заметим, что для многокритериальных задач комбинаторного типа этот подход, как правило, оказывается не эффективным.
Следует отметить, что наибольшие успехи в решении многокритериальных задач (в смысле нахождения Паретовского множества) достигнуты для классов многокритериальных задач линейного программирования. При этом построение Паретовского множества осуществляется путем прямого обобщения симплекс-метода линейного программирования на многокритериальный случай. Указание на многочисленные публикации по этой теме в иностранных источниках можно найти в [77].
Область дискретной векторной оптимизации еще мала изучена. Основанный на методе построения последовательности планов подход к решению дискретных многокритериальных задач изложен в книге [80], алгоритмы, использующие идеи «просеивания» решений, предложены в [81,82]. Методы решения многокритериальных задач с булевыми переменными излагаются в работах [73,83-86]. Отметим также работу [87], посвященную многокритери-
альной задачи теории расписаний, и работу [88], в которой исследуется полиматричная задача коммивояжера.
Все известные точные методы, предложенные для решения дискретных многокритериальных задач в общем случае (т>2), имеют экспоненциальную трудоемкость, поскольку включают в себя по необходимости целенаправленный перебор решений х є X.
Исходя из выше сказанного, можно сделать заключение, что нецелесообразно ставить вопрос о создании достаточно точных методов, которые бы оказались эффективными для решения многокритериальных задач. Необходимо сознательно идти по пути разбиения общей постановки многокритериальной задачи на более узкие классы и, пользуясь их спецификой, разрабатывать для них эффективные алгоритмы или, что более перспективно, алгоритмы с оценками [38,89]. Именно разработке и построению таких алгоритмов с оценками относятся результаты, полученные в настоящей диссертационной работе.
На данный момент теория предфрактальных и фрактальных графов не имеет достаточного развития для эффективного использования в практических целях. Существует ряд неизученных или слабо изученных направлений. К ним относятся:
проблема распознавания фрактальных и предфрактальных графов;
алгоритмическая проблема решения задач многокритериальной оптимизации на фрактальных и предфрактальных графах;
проблема вычисления фрактальной размерности произвольного фрактального графа;
проблема компактного задания предфрактального и фрактального графа;
проблема построения предфрактальных и фрактальных графов с заданными свойствами.
В настоящей работе решается ряд обозначенных выше проблем.
Целью диссертационной работы является развитие теоретической базы, а также разработка и совершенствование методов и алгоритмов исследования сложных систем с элементами структурного хаоса в условиях многокритериальное. Исследование проблемы распознавания предфрактальных графов. Разработка алгоритмов распознавания предфрактальности графов.
Основными задачами исследования, определяемыми поставленной целью, являются:
изучение практической значимости многокритериальной задачи покрытия предфрактальных графов простыми цепями в математическом моделировании;
задачи моделирования объектов с элементами структурного хаоса при помощи математического аппарата теории предфрактальных и фрактальных графов;
разработка полиномиальных алгоритмов с оценками построения покрытий простыми цепями на предфрактальных графах;
построение полиномиальных алгоритмов распознавания свойств предфрактальности графов.
Методы исследования основываются на использовании математического аппарата:
теории графов;
теории предфрактальных и фрактальных графов;
комбинаторики;
- многокритериальной оптимизации.
Перейдем к изложению содержания диссертации.
В первой главе диссертации дано индуктивное определение предфрак-тального и фрактального графа. Определены некоторые свойства предфрак-тального графа, необходимые для описания результатов работы.
Впервые рассматривается четырехкритериальная постановка задачи о покрытии пред фрактального графа простыми непересекающимися цепями
(покрытие вида Kj). Строится математическая модель корпоративной сети с распределенной вычислительной системой, которая может содействовать эффективной организации вычислительного процесса.
Впервые рассматривается пятикритериальная постановка задачи о покрытии предфрактального графа простыми пересекающимися цепями (покрытие вида К2). Строится и исследуется математическая модель транспортной системы в больших масштабах, которая сводится к рассматриваемой многокритериальной задаче и может содействовать более эффективной организации транспортной системы, состоящей из большого числа элементов. Для каждого приведенного критерия обосновывается конкретная содержательная интерпретация в понятиях транспортных систем.
Вторая глава посвящена построению алгоритмов с оценками покрытия простыми цепями двух типов, а именно непересекающимися и пересекающимися простыми цепями. Для покрытия простыми непересекающимися цепями - типа Kj, рассматриваются и обосновываются алгоритмы построения покрытия L - ранговыми цепями длины один (одно ребро), L - ранговыми цепями длины два (два ребра) и L - ранговыми цепями длины три (три ребра). Все приведенные алгоритмы являются полиномиальными и основаны на алгоритме выделения совершенного паросочетания минимального веса, предложенного Эдмонсом [10,11], который представлен в алгоритмах в виде процедуры. Причем каждый из рассмотренных алгоритмов строит парето-оптимальное решение многокритериальной задачи, а также даются и обосновываются оценки значений критериев для построенных решений.
Для покрытия простыми пересекающимися цепями - типа К2, разработаны и обоснованы два алгоритма построения покрытия. Первый алгоритм выделяет покрытие минимального веса, являющееся парето-оптимальным решением рассматриваемой многокритериальной задачи. Даются оценки значений критериев для покрытий, полученных с его помощью. Причем этот ал-
горитм является полиномиальным. Второй алгоритм также является полиномиальным и выделяет покрытие, состоящее из максимальных простых цепей. Для него даются оценки значений критериев для покрытий, полученных с его помощью.
В третьей главе впервые рассматриваются алгоритмы распознавания предфрактальных графов, порожденных затравкой являющей простой цепью, а именно цепью длины один (одно ребро) и произвольной длины. Все приведенные в главе 3 алгоритмы являются полиномиальными. Для них доказаны и вычислены оценки их трудоемкости.
В диссертационной работе получены следующие новые научные результаты.
- впервые поставлена и исследована многокритериальная задача по
крытия предфрактального графа простыми непересекающимися
цепями;
впервые поставлена и исследована многокритериальная задача покрытия предфрактального графа простыми пересекающимися цепями;
построена и исследована модель крупномасштабной транспортной системы, сводимая к многокритериальной задачи покрытия предфрактальных графов пересекающимися простыми цепями;
разработаны и обоснованы новые полиномиальные алгоритмы с оценками отыскания некоторых парето-оптимальных решений для изучаемых задач;
построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь;
впервые построены полиномиальные алгоритмы распознавания предфрактальных графов порожденных затравкой, являющейся простой цепью.
По теме диссертационной работы опубликовано 12 печатных работ.
Основные результаты работы докладывались и обсуждались на:
IV Научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (г.Черкесск, 2002);
XVI Международной научной конференции «Математические методы в технике и технологиях» (г.Санкт-Петербург, 2003);
XVII Международной научной конференции «Математические методы в технике и технологиях» (г.Кострома, 2004);
VI Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г.Кисловодск, 2004);
Научных семинарах профессорско-преподавательского состава КЧГТА (г.Черкесск, 2001-2004).
Объем и структура диссертационной работы. Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников.
Работа изложена на 112 страницах, из них 2 страницы рисунков, 1 страница приложения, 11 страниц списка использованных источников, содержащего 104 наименований.
Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К1)
В настоящее время деятельность крупных организаций, в функции которых входит учет, анализ информации и в соответствии с ней принятие определенного решения, не мыслима без обработки ее на ЭВМ. Если же приходится работать с огромным объемом информации, то необходимо использование распределенных вычислительных систем [90], входящих в функции корпоративной сети, состоящей из большого количества ЭВМ, соединенных линиями связи.
Примером таких организаций имеющих корпоративную сеть с распределенной вычислительной системой, является центральный пункт управления полетами, транспортом, военные ведомства, финансовые биржи и т. д. Структура корпоративной сети большинства из них состоит из множества секций, где каждая секция представляет собой совокупность ЭВМ соединенных между собой линиями связи. Роль секций в решении задачи заключается в том, что они выполняют обработку информации на некотором этапе. Далее, секции объединяются в отделы, которые анализируют информацию переданную по линиям связи с секций. В свою очередь, ведомства состоят из отделов и работают с информацией переданной им последними. Подобным образом, соединяются подразделения всей организации входящей в корпоративную сеть и т. д. Пока на некотором этапе определенная структура, содержащая под контролем всю корпоративную сеть, проанализировав информацию, примет определенное решение.
От корпоративной сети с распределенной вычислительной системой при решении определенной задачи требуется: надежность, быстрое и качественное принятие решения. Причем каждая ЭВМ входящая в сеть должна участвовать в решении общей задачи, ибо несет в себе определенную функцию.
Рассмотрим топологию сети в виде графовой модели [9-16,55-60]. Вершинам графа будут соответствовать отдельные ЭВМ. А ребрам, в свою очередь, соответствовать линии связи соединяющих перечисленные ЭВМ. Моделью такого рода иерархии с «большим» числом составных частей является предфрактальный граф, в общем случае порожденный множеством затравок.
Ниже предложено формальное описание этой задачи в терминах теории графов [9-16,55-60] и многокритериальной дискретной оптимизации [38,40,74,80,89]. Покрытие предфрактального графа простыми непересекающимися цепями, есть распределение задачи по элементам сети.
Рассмотрим взвешенный предфрактальный граф GL =(VL,HL) порожденный затравкой H = (W,Q), у которой ж = и, (2 = 7- Под весом ребер соединяющих некоторые вершины u,weV, будем понимать степень отказа (сбоев) в линии связи между ними. Причем у ребер L-ro ранга, весам будет соответствовать самая минимальная степень отказа (секции не зависят от других структур).
Под цепью предфрактального графа Gf понимаем простую цепь С [55], а количество ребер в ней называем длиной цепи и обозначаем len(C). Простую цепь, ребра которой имеют одинаковый ранг /, будем называть /-ранговой цепью и обозначать С . Покрытием вида К] графа GL будем называть подграф у = (VL,EV), Ev с EL, состоящий из множества простых цепей, где каждая вершина инцидентна ребрам только одной цепи из у. Это означает, что покрытие у состоит из компонент, каждая из которых является простой цепью. Всевозможные покрытия {у} предфрактального графа GL образуют множество допустимых решений Y = Y(GL) = {у} (МДР).
Критерий (1.6) направлен на сокращение времени обработки информации в корпоративной сети с распределенной вычислительной системой.
При равномерном распределении задачи между элементами сети, все будут задействованы в решении задачи одинаково, что позволит не перегружать отдельные ЭВМ, именно на это направлен критерий (1.7).
Важной и значимой на практике является задача организации сети пассажирского транспорта [7,91-93]. В качестве модели карты дорог какого-либо населенного пункта, района или города разумно использовать граф [55]. Вершины такого графа могут соответствовать, к примеру, перекресткам, промышленным объектам или даже остановкам в жилых кварталах. А ребра, в свою очередь, соответствовать отрезкам дорог соединяющих перечисленные узлы транспортной системы.
В более широком рассмотрении, карта дорог отдельно взятого региона состоит из "редко" связанных дорогами между собой схем транспортных сетей районов и городов этого региона. Далее, карта дорог федерального округа состоит из карт дорог регионов. Подобным образом, соединяются и карты дорог всего государства из карт дорог ее округов и т.д. Моделью такого рода самоподобной [35,41] карты дорог с "большим" числом составных частей является предфрактальный граф, в общем случае порожденный множеством затравок.
Как в случае, когда в качестве модели схемы дорог используется "обычный" граф, так и в случае, когда используется предфрактальный граф, при рассмотрении сетей пассажирского транспорта естественным образом возникает задача построения системы транспортных маршрутов некоторого специального вида, позволяющей попасть из любого узла транспортной системы в любой другой при ограничениях налагаемых на время, длину пути, число пересадок и т.д.
Алгоритмы а1 построения покрытия L -ранговыми цепями длины один
На вход алгоритма Эдмондса подается произвольный взвешенный граф О = (У,/і), а на выходе получается совершенное паросочетание минимального веса. Для удобства формулировки алгоритма опишем задачу нахождения совершенного паросочетания максимального веса (ЗМП). В свою очередь этот алгоритм будет основан на алгоритме для задачи нахождения наибольшего совершенного паросочетания (ЗНСП). Замена каждого веса на отрицательный позволит решать задачу нахождения совершенного паросочетания минимального веса. Приведенные ниже при формулировке алгоритма Эд-монса теоремы будут описаны без доказательства. Доказательство этих теорем можно найти в [10,14]. Представим далее некоторые определения, необходимые для описания алгоритма.
Если дано паросочетание М , то вершина, не являющаяся конечной вершиной никакого ребра из М , будет называться экспонированной вершиной. Альтернирующая относительно М цепь - это простая цепь, ребра которой попеременно лежат или не лежат в паросочетании М . Аугментальная относительно М цепь - это такая альтернирующая цепь, начальная и конечная вершины которой экспонированы. Основная относящаяся к паросочетаниям теорема звучит следующим образом. ТЕОРЕМА 2.1. Паросочетание М будет наибольшим паросочетаиием тогда и только тогда, когда в G не существует никакой аугментальной относительно М цепи. Альтернирующим деревом относительно данного паросочетания М называется дерево Т, для которого (а) одна вершина, называемая корнем дерева Г, является экспонированной; (б) все начинающиеся в корне цепи являются альтернирующими; (в) все максимальные цепи, начинающиеся в корне дерева Т, содержат чет ное число ребер. Разобьем все вершины дерева на два класса: Ф - класс внешних вершин, / - класс внутренних вершин. Корень дерева отнесем к классу Ф. Вершины вдоль любой цепи, начинающейся в корне, будут поочередно отнесены к классам Фи/. Таким образом, если вершина расположена в "конце" цепи с нечетным числом ребер, начинающейся в корне, то эта вершина будет отнесена к /, а если она лежит в "конце" цепи с четным числом ребер, начинающейся в корне, то будет отнесена к Ф. Аугментальное дерево - это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует ребро от какой-нибудь внешней вершины дерева v0, до некоторой экспонированной вершины ve, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины v0 и далее - по ребру (v0, ve), будет тогда аугментальной цепью.
Цветком по отношению к паросочетанию М называется аугментальная цепь, начальная и конечная экспонированные вершины которой совпадают, т.е. эта цепь является циклом, так как число ребер этой цепи нечетно.
В алгоритмах для ЗМП и ЗНПС, описанных ниже, цветки срезают для того, чтобы получить более простой новый граф. Срезание цветка В состоит в замене всех вершин цветка В (скажем, VB) одной новой псевдовершиной vh. Ребро (yh, vk) добавляется всегда, когда существует ребро из некоторой вершины v, є Vв к другой вершине vk & Ув. В упрощенном графе, полученном после срезания, вершина vb и другие псевдовершины, соответствующие ранее срезанным цветкам, могут в свою очередь образовывать новый цветок, который опять срезается, и т.д. .Последний цветок В(), не содержащийся ни в каких других цветках, называется крайним цветком. Обоснование процесса срезания цветков основано на теореме 2.2, приводимой ниже.
Цветущее дерево - это альтернирующее дерево относительно данного паросочетания, для которого существует ребро (V {),VQ), соединяющее две внешние вершины дерева: v0 и v"}. Если Р - множество ребер цепи, начинающейся в корне альтернирующего дерева и кончающейся в v0 , а Р" - соответствующее множество для VQ, ТО множество ребер [P l JP"-P f P"] вместе с ребром (V0,VQ) образует цветок.
Когда цветок В срезан, получающаяся псевдовершина считается внешней вершиной. Всякая вершина из В может быть по желанию отнесена к внутренним или к внешним вершинам, так как если вершина принадлежит В, то она является концевой и в цепях с четным, и в цепях с нечетным числом ребер, начинающихся в корне дерева (в зависимости от маршрута, по которому проходят эти цепи до прихода в первую вершину цветка). Но когда псевдовершина, получающаяся после срезания цветка, помечается как "внешняя", структура остающегося альтернирующего дерева все еще будет корректной - как это вытекает из определения альтернирующего дерева. Таким образом, после срезания цветка альтернирующее дерево в получившемся графе сохраняется.
Венгерское дерево - это такое альтернирующее дерево в графе, что каждое ребро графа, имеющее внешнюю вершину дерева в качестве концевой, имеет другой концевой вершиной внутреннюю вершину этого дерева. Важность венгерских деревьев для ЗМП объясняется следующим их свойством.
ТЕОРЕМА 2.2. Пусть Н - венгерское дерево в графе G = (V, Е) и G() = (V - Vн ) -порожденный подграф графа G, "исключающий" из G множество вершин Vu дерева Н. Если М и- паросочетание в дереве И и М ; -наибольшее паросочетание в G0, то множество ребер М н KJM G является наибольшим паросочетанием в G.
Разработка и исследование полиномиальных алгоритмов построения покрытия К2
Построим алгоритм а2 покрытия цепями длины два (два ребра) на взвешенном предфрактальном («,/,)-графе GL =(VL,EL) порожденном затравкой Н = (JV,Q), у которой Ж = я, \Q\ = q, где п кратно трем, т.е. алгоритм а2 строит покрытие у2 = (V,Ey ) простыми цепями длины два ребра.
Основная идея алгоритма заключается в том, что каждая подграф затравка z[L\ s = \,nL 1 рассматривается как отдельно взятый граф. Последовательно на каждой из п подграф-затравке производится поиск покрытий простыми цепями длины два Ms. Поиск покрытия на отдельно взятой подграф-затравке осуществляется с помощью процедуры Выделения покрытия [95-97] цепями длины два в основе которой лежит алгоритм Эдмондса, описанный ранее. Осуществив поиск покрытий простыми цепями длины два на подграф-затравках, мы получим покрытие у2 = (V,EV простыми цепями длины два ребра предфрактального графа GL, после чего алгоритм а2 заканчивает свою работу. Предложим краткое описание процедуры Выделения покрытия цепями длины два для целостного понимания алгоритма а2. На взвешенном графе G = {V, Е) производится поиск совершенного паросочетания минимального веса Мх используя описанный ранее алгоритм Эдмондса. Далее среди элементов совершенного паросочетания минимального веса Мх, выделяется элемент rrij еМ}, jeJ с максимальным весом. Далее, рассматривая у концевых вершин выбранного элемента rrij инцидентные ребра графа G, выбираем и выделяем те из них, которые имеют минимальный вес (у каждой концевой вершины покрытия их может быть несколько). Выделенные ребра уже соединяют два элемента покрытия m rrij еМь / є / и образует в отдельности друг от друга цепи с3. Далее, рассматриваем в отдельности каждую из этих цепей и выбираем среди них ту, которая имеет минимальный вес. У вы-бранной минимальной цепи с3 сравниваем и выбираем из двух ребер принадлежащих покрытию Мх то, которое имеет минимальный вес, а ребро по крытия М] с максимальным весом исключаем из цепи с3, запоминая и окрашивая конечную вершину исключенного ребра, принадлежащего Мх. В результате этой операции мы выделили цепь длины два. Далее описанная операция применяется многократно, до тех пор пока не будет покрыт весь граф G цепями длины два. Вход: взвешенный предфрактальный граф GL ={VL,EL). ВЫХОД: покрытие уг = (V,E ) простыми цепями длины два. ІІІАГІ. Последовательно для каждой затравки zK/ , s = \,n найти покрытие Мs простыми цепями длины два, используя процедуру ПЦДД. ШАГ 2. На выходе шага 1 получаем s = \,п покрытий Ms, для каждой затравки z . Объединяя эти покрытия Мs получим покрытие У г = (Уі Еу,) предфрактального графа GL . Выход: покрытие М простыми цепями длины два. Л ТЕОРЕМА 2.7. Если существует покрытие, то алгоритм а2 выделяет покрытие у2 =(V,EV ) цепями длины два (два ребра) на пред фрактальном (п,Ь) -графе GL=(VL,EL), порожденного п-вершинной затравкой И = (W,Q), где п кратно трем. ДОКАЗАТЕЛЬСТВО. Поиск цепей длины два на подграф-затравках осуществляется с помощью процедуры выделения покрытия цепями длины два, основанной на алгоритме Эдмондса. На последнем шаге L построения предфрактального графа GL все вершины замещаются затравкой H-{W,Q), тогда каждая вершина L-oro ранга принадлежит какой-либо подграф-затравке z), ). Таким образом в результате выделения покрытия на подграф-затравке, будут покрыты все вершины принадлежащие этой затравке. Поэтому алгоритм а2 работает только с подграф-затравками L-oro ран Выделим на подграф-затравке L-oro ранга z\ покрытие Мх. В результате покрытие Мх выделило п вершин. Далее выделим на второй затравке L-oro ранга z2 покрытие М2. Покрытие М2 выделило еще п вершин. Это покрытие никак не повлияло на Мх, так как подграф-затравки z[ и z2 ) являются отдельными не связанными между собой подграфами. Тогда, после выделения покрытия М L_, на последней подграф-затравке z(L_,, будет покрыто п 1-п = п вершин. Получим, что покрыто п все множество вершин GL = (VL,EL): \VL\ - nL . На затравках z). выделялись покрытия Мs, s = \,п , то есть вершины предфрактального графа покрывались цепями длины два. Таким образом, полученное покрытие является покрытием у2 =(V,Ey ) предфрактального графа GL. -4 ТЕОРЕМА 2.8. Вычислительная сложность алгоритма а2 покрытия цепями длины два (два ребра) на предфракталъном (n,L)-графе GL={VL,EL), порожденного затравкой Н = (1,0), где V\-п, \VL\ = N = nL, равна Q(N -In1). ДОКАЗАТЕЛЬСТВО. Алгоритм а2 представляет собой, по существу многократное выполнение шага 1, т.е. поиск покрытия длины два ребра для каждой подграф-затравки, а их п . Для каждой затравки выполняются следующие действия. Сначала производится поиск совершенного паросочетания минимального веса, что требует выполнения 0(п ) операций на каждой подграф-затравке, столько операций выполняет алгоритм Эдмондса. Далее просматриваются все ребра паросочетания и находится наибольшее, т.е. выполняется — операций. Далее просматриваются все смежные ребра для каждого ребра паросочетания, если затравка полный граф для каждой вершины будет просмотрено (п-Y) ребер, в сумме будет выполнено —-2(/7-1) = я(я-1) операций. Затем для каждого элемента покрытия цепями два ребра будет 2я просмотрено по две цепи длины три ребра, что составит — операции. Таким образом получим — + п(п-\)-\ = п + — + п = п + —, ко торые не превосходит п3 Тогда количество операций на затравке будет рав- няться п + п = 2п . Тогда вычислительная сложность алгоритма а2 на всем предфракталь ном графе равна 0(п -2п ) = 0(п -2п ) = Q(N-2n ). Таким образом, вы числительная сложность алгоритма а2 равна 0(N -2п ) .
Алгоритм распознавания предфрактального графа с затравкой простая цепь длины (ребер)
Цель применения алгоритма ух к данному (2Д,)-дереву D состоит в том, чтобы преобразовать D в (2,1-1)-дерево Dx. Применительно к D работа /j состоит из К этапов, пронумерованных индексом к \,2,...,К; К L -1. В свою очередь, всякий этап (кроме последнего) состоит из подэтапов, пронумерованных индексами пк =\,2,...,тк, где величина тк есть число висячих или квазивисячих цепей в дереве, которое представлено на вход алгоритма ух к началу реализации этапа к. Каждый очередной подэтап реализуется на очередной висячей или квазивисячей цепи и состоит из шагов s=\,2,...,d, где d - длина, т.е. число ребер в этой цепи. На каждом из этих шагов рассматривается очередное ребро указанной цепи; это ребро преобразуется в дугу (т.е. ориентированное ребро), и при этом полученная дуга окрашивается или остается неокрашенной в зависимости от того, не окрашивалось или окрашивалось ребро (дуга) на предыдущем шаге.
Пусть M=M(D) - множество всех О-цепей данного (2,А)-дерева D={V,E). Можно считать очевидным следующее Утверждение 3.1. Для всякого (2,L)-depeea D его множество M(D) определяется однозначно. Через Мк будем обозначать подмножество всех тех О-цепей, на которых реализуются подэтапы этапа к, т. е. Мк - это (исходная) информация, которая составляет вход этапа к; \JM к = М . Отличительная особенность этапа к=\ состоит в том, что подмножество М\ состоит из всех висячих цепей дерева D. Для всякого к 2 подмножество Ми сМ состоит только из квазивисячих цепей. Работа этапа к=\ состоит из тї =\М1\ подэтапов, пронумерованных индексом л"! =\,2,...,т1. На подэтапе пх рассматривается я- ая по порядку висячая цепь, ребрам которой придается односторонняя ориентация в направлении от висячей вершины этой цепи. Далее дуги (т.е. ориентированные ребра) я -й висячей цепи нумеруются в направлении принятой ориентации индексами 1,2,3,..., после чего нечетные дуги окрашиваются, а четные остаются неокрашенными. В результате работы подэтапа пх висячая цепь преобразуется в висячий путь с чередующимися окрашенными дугами. Пусть осуществлено к этапов, в результате которых в данном дереве D оказывается непустым множеством неориентированных ребер. Тогда в работе алгоритма ух следует переход к этапу (к+\). В начале этапа к-\ формируется множество Мк+\ квазивисячих цепей дерева, являющегося результатом преобразования предыдущего этапа. Началом каждой такой цепи является узловая вершина, инцидентная ориентированным дугам, а также одному и только одному неориентированному ребру. Эти цепи нумеруются индексом 7гк+х=\,2,...,тк+х, тк+1=\Мк+1\. Работа подэтапа кк+1 начинается с ориентации ребер /гА+]-й цепи в направлении от ее начала, в результате чего ребра этой цепи превращаются в дуги. Завершается подэтап 7гк+1 раскраской дуг л-А.+1-й согласно следующему правиу. Если начальная дуга цепи пересекается только и только неокрашенными дугами, то эта дуга окрашивается, равно как и окрашиваются все нечетные дуги этой, по аналогии с этапом к=\ на завершающей стадии всякого подэтапа тгк+1, когда окрашиваются все нечетные дуги, а четные остаются неокрашенными. Если же начальная вершина як+\-н цепи инцидентна окрашенной дуге, то все нечетные дуги цепи лк+1 остаются неокрашенными, а все четные - окрашиваются. Результат работы этапа к называем недопустимым (допустимым), если и на выходе этого этапа получаем дерево, в котором пересекается (не пересекается), хотя бы одна пара (всякая пара) окрашенных дуг. Алгоритм ух заканчивает свою работу безрезультатно в случае получения недопустимого результата по завершении какого-либо его этапа. Пусть к данному дереву D применен алгоритм ух, поэтапная работа которого на каждом этапе к завершается допустимым результатом. Последнее означает, что по окончании этапа К получаем дерево Д в котором каждое ребро имеет определенную ориентацию. Определенная часть его дуг окрашена, причем никакая пара окрашенных дуг не пересекается. В этом случае к каждой окрашенной дуге применяется операция стягивания, в результате чего получаем дерево, которое обозначается символом Д. Далее в дереве Д снимается ориентация его дуг, т.е. каждая дуга преобразуется в ребро. К дереву Д с безориентированными дугами применяется алгоритм ух, поэтапная работа которого может завершиться безрезультатно в случае получения недопустимого результата. В случае допустимого результата в дереве Д на завершающем этапе стягиваются окрашенные дуги, в результате чего после обратного преобразования дуг в ребра получаем дерево, которое обозначаем через D2. Заметим теперь, что если данное дерево D={V,E) является "распознаваемым", то число его вершин определяется, по необходимости, равенством \V\ = 2L, где L - целое положительное число. Если данное дерево D является предфрактальным (2, //)-деревом, то результативное (L-1)-кратное применение алгоритма порождает последовательность деревьев где DL_\ представляет собой 2-вершинное дерево, состоящее из одного ребра, т.е. из одной затравки. По своему определению последовательность (3.1) представляет собой траекторию порождения предфрактального (2,)-графа. Таким образом, распознавание свойства предфрактальности данного дерева D сводится к построению последовательности G\,G2,...,GR с помощью алгоритма ух. Очевидно, что для вычислительной сложности т{у-[) этого алгоритма справедлива следующая верхняя оценка: T(yx) 0(N L) = 0(N\ogN),rj&\V\=N.
