Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов Батчаев Ильяс Заурович

Содержание к диссертации

Введение

ГЛАВА 1. Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов 19

1.1. Необходимые обозначения и определения 19

1.2. Постановка многокритериальной задачи о покрытии предфрактально-го графа звездами ранговых типов 21

1.3. Исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки 23

1.4. Примеры построения математических моделей на предфрактальных графах, сводящихся к покрытию звездами ранговых типов 35

1.4.1. Математическая модель системы контроля трафика в Интернете 36

1.4.2. Математическая модель сети центров МЧС РФ 43

1.5. Выводы 47

ГЛАВА 2. Полиномиальные алгоритмы построения покрытий предфрактальных графов звездами ранговых типов с оценками 48

2.1. Способы задания предфрактальных графов 48

2.2. Предварительные упрощения задачи 58

2.3. Разработка и исследование алгоритмов покрытия предфрактальных графов звездами ранговых типов 59

2.3.1. Алгоритм построения покрытий минимального веса 60

2.3.2. Алгоритм построения покрытий звездами одного рангового типа 69

2.4. «Быстрый» алгоритм построения покрытия предфрактального графа звездами ранговых типов с оценками 76

2.5. Выводы 83

ГЛАВА 3. Построение предфрактальных графов с заданными характеристиками 85

3.1. Формулировка проблемы и постановка задачи 85

3.2. Разработка алгоритмов построения предфрактальных графов с заданными характеристиками 86

3.2.1. Алгоритм построения предфрактального графа, для которого число ранговых типов звезд точного покрытия больше двух 86

3.2.2. Алгоритмы построения предфрактального графа, точное покрытие которого состоит из звезд одного рангового типа 96

3.2.3. Алгоритм построения предфрактального графа, точное покрытие которого состоит из звезд двух различных ранговых типов. 102

3.3. Выводы 105

Заключение 106

Литература 108

Приложение 118

• Исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки
• Математическая модель системы контроля трафика в Интернете
• «Быстрый» алгоритм построения покрытия предфрактального графа звездами ранговых типов с оценками
• Алгоритм построения предфрактального графа, для которого число ранговых типов звезд точного покрытия больше двух

Введение к работе

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

Для моделирования дискретных структур в большинстве случаев применяют графы. Однако, существуют объекты, состоящие из огромного числа элементов, связи которых с течением времени могут меняться. Говорят, что этим объектам присущи элементы динамического хаоса, для моделирования которого методы классической теории графов не подходят в силу своей неэффективности.

В диссертации в качестве средства моделирования динамического хаоса предлагается использовать предфрактальные и фрактальные графы в том понимании, в каком оно впервые предложено в работах В.А. Перепелицы и A.M. Кочкарова, и получило дальнейшее развитие в трудах A.M. Кочкарова и его учеников. Это объясняет важность развития математического аппарата для нахождения конкурирующих альтернатив (па-рето-оптимальных решений) в условиях многокритериальности на пред-фрактальных и фрактальных графах, а также построение графов такого типа с заданными характеристиками.

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

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

Перечислим некоторые из них:

распознавание предфрактальных и фрактальных графов;

способы их задание (представления в памяти ЭВМ); -вычисление размерности Хаусдорфа-Безиковича для фрактальных

графов;

- алгоритмические вопросы многокритериальной оптимизации;

- исследование разрешимости многокритериальных задач на предфрак
тальных графах с помощью алгоритма линейной свертки критериев;

-построение предфрактальных и фрактальных графов с заданными свойствами. Задача построения покрытия предфрактального графа звездами ранговых типов является частным случаем задачи о наименьшем покрытии (разбиении), которая формулируется следующим образом: пусть дано множество V - {н„«₂,...,«„} и семейство 3 = {5„^2,...,5_т} множеств S, с V . Необходимо отыскать подсемейство 3' = |у ,5_;j,...,5 } семейства 3 наименьшей мощности, такое, что

(JS_h = V_tS_Jk r>S_Jt = 0, для любых h,l є {1,2,...,*} [1].

Если под множеством V - {и,,и₂,...,и_п] понимать вершины заданного графа G-(y,E), а в качестве элементов семейства 3 рассматривать все-

возможные содержащиеся в нем звезды, то приходим к задаче покрытия графа звездами. Здесь под звездой понимается полный двудольный граф, одна доля которого состоит из единственной вершины [2].

Существует несколько основных способов решения данной задачи. Некоторые из них описаны в [1]. К ним относится алгоритм, использующий дерево поиска - метод, заключающийся в сведении задачи о покрытии к задаче линейного программирования вида: пусть V = {i/„i/₂,.. ,и_п} -множество вершин графа G, 3 = {AT,^,АГ,,,₂,...,АТ,,,_} - семейство всех звезд допустимых типов. Необходимо минимизировать функцию

*=*. о)

при ограничениях:

/,=1,і = 1,2,...,и,

1, если AT, _s принадлежит покрытию х О, если AT, _s не принадлежит покрытию х'

1, если и, є AT,

t =< '' О, если м, 0 AT_1S(

Здесь с_} > 0 - стоимость звезды AT, _s . При этом, если стоимость равна единице для каждой звезды, то решение задачи линейного программирования определяет покрытие, состоящее из наименьшего числа звезд. В случае взвешенного графа G, стоимость может соответствовать весу звезды, т.е. будет отыскиваться покрытие минимального веса.

В случае, когда минимизируется сразу несколько целевых функций вида (1), возникает необходимость решения многокритериальной задачи покрытия графа звездами. Следует подчеркнуть, что эта задача является NP-трудной, т.е. не существует полиномиального алгоритма, способного дать точное решение для любого графа [2,3]. В связи с этим, пути ее ис-

следования идут в трех направлениях: строятся вероятностные алгоритмы, отыскиваются полиномиально разрешимые классы графов, создаются эвристические алгоритмы с оценками. Так в [4] был осуществлен вероятностный анализ многокритериальной задачи покрытия графа звездами; в [5] построен эвристический алгоритм ее решения; в [6] обоснованы оценки эффективности векторной задачи покрытия графа звездами. Последние результаты в данной области, по всей видимости, можно отнести к работам В.А. Перепелицы, в [7] построен градиентный алгоритм для задачи покрытия графа звездами; условия полиномиальной разрешимости данной задачи разработаны в [8]; интервальная задача покрытия графа звездами, и исследование разрешимости ее в классе алгоритмов линейной свертки, рассматриваются в [9]; в [10,11] разработаны алгоритмы построения покрытий звездами и исследуется их практическое применение.

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

Предположим, что необходимо решить многокритериальную задачу, в которой системой условий или каким-либо другим способом задается множество допустимых решений X = {х} (например, множество всевозможных покрытий звездами ранговых типов). На этом множестве определяется векторная целевая функция (ВЦФ)

F(x) = (^(x),F₂(x),...,F_m(x)), где /*](*),(/ = 1,2,...,от) требуют минимизации (F_t(x)-»max всегда можно заменить на -F_k(x)->rmn). Наиболее предпочтительным является нахождение точных решений, т.е. множества всех допустимых решений х є X с минимальными значениями критериев

F_x(x) —> min, F₂(x) -> min,...,F_m(x) -> min .

В случае противоречивости критериев таких решений многокритериальной задачи не существует, т.е. пересечение f}X_t оказывается пус-

тым, где Х„(/= 1,2,...,/я) множество допустимых покрытий хеХ, на каждом из которых значение fXx) достигает минимума. В этом случае ВЦФ

при т > 2 определяет паретовское множество X с X [12-15].

Решение х₀ є X называется парето-оптимальным (по критериям F,(x),(i = 1,2,...,т)\ если оно удовлетворяет следующему условию: не существует такого элемента у є X, чтобы среди неравенств

F,(y)₀\ і = 1,2,...,

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

Множество f(x)={f(x):xz Х}, где F(x) = (F_t(x),F₂(x),...,F_m(x)) называется множеством достижимости, a F[X) - паретовская граница множества достижимости F(x). Полным множеством альтернатив (ПМА) называется минимальное по мощности множество Ґсі такое, что /фґ)= F{X) [12-15]. Как правило, «наилучшее» решение выбирается из ПМА.

Опишем наиболее распространенные методы нахождения парето-оптимальных решений многокритериальной оптимизационной задачи [16-20].

Одним из них является нахождение лексикографического [18,20,21] оптимума. Суть этого метода заключается в ранжировании критериев F^x),(/ = 1,2,...,т) по степени важности, т.е. осуществляется линейное упорядочение критериев так, что для любых двух из них можно однозначно указать, какой имеет приоритетное значение. В этом случае особое значение представляет случай, когда найденное решение является парето-оптимальным.

В данной работе этот метод применяется в большинстве алгоритмов, ибо позволяет разбить 3-х критериальную задачу на последовательность трех однокритериальных задач. Таким образом, достаточно сначала

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

Один из наиболее простых и, в то же самое время, самый эффективный метод многокритериальной оптимизации, свертка [18,22,23], основан на идее замены критериев единственной целевой функцией представимой в виде:

1=1

где F^x) - нормированное значение критерия F^x), h_t - коэффициент относительной важности /-й целевой функции, при этом

4>0,2>=1.

Нормирование функций F_t(x), необходимое для приведения их к одному измерению, осуществляется, например, согласно правилам:

^) = -^(*)или/^*) = ^, где A = max.F(x), а = rmnFix).

При использовании метода линейной свертки предполагается, что если на элементе х* є X целевая функция <т(х) достигает минимума, то

х* еХ ,т.&. является парето-оптимальным решением.

Следует отметить, что в некоторых случаях свертку осуществляют в

виде произведения P(x) = Y[^F_l^h(^x)-

1=1

Метод свертки имеет ряд достоинств: простота метода, возможность сведения противоречивой многокритериальной задачи к классической од-нокритериальной и т.д. За счет этого на основе линейной свертки базиру-

ется большинство алгоритмов многокритериальной оптимизации [17,24-29].

Тем не менее, перед его использованием необходимо рассмотреть следующие вопросы, касающиеся эффективности этого метода по отношению к конкретной задаче:

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

-проверить наличие начальных данных, при которых свертка не достигает минимума ни при каких допустимых значениях xs X, что означает невозможность нахождения некоторых решений данным методом;

- исследовать вопрос существования таких парето-оптимальных реше
ний, которые не удается найти никакой линейной сверткой критери
ев, т.е. вопрос разрешимости многокритериальной задачи с помощью
алгоритма линейной свертки критериев.

Некоторые исследования, касающиеся разрешимости многокритериальных задач с помощью алгоритма линейной свертки, предложены в [17,21,25]. По-видимому, можно считать, что наиболее общие результаты, относящиеся к рассматриваемой проблеме, представлены в [25]. Эти результаты базируются на том факте, что так называемые примитивные индивидуальные задачи являются неразрешимыми с помощью алгоритма линейной свертки критериев.

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

_{/(*)= ±Ш*))}

ГДЄ5>1.

Распространенным методом является введение метрики в пространстве целевых функций [18,30]. Если не удается найти точное решение многокритериальной задачи, то в качестве векторного оптимума х₀ берется решение, для которого вектор f(x₀) = (f,(x₀\f₂(x₀),...,F_m(x₀)) наименее удален ОТ вектора а = (а„а₂,...,а_ш), где a, = rmn F,(x\(i = 1,2,...,т).

Иными словами, в пространстве целевых функций 7^(х),(; = 1,2,...,/и)

определяется точка а, которую называют точкой «абсолютного минимума». При этом подразумевается, что расстояние от абсолютного минимума до всякой точки F(x) є R^m берется с учетом относительной важности целевых функций. Таким образом, получается функция, являющаяся улучшенным вариантом свертки

\Ъ к ^а. J

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

Также применяют численные методы построения парето-оптимальных решений [30]. При этом подходе последовательно фиксируются значения целевых функций, после чего каким-либо приемлемым методом решается задача однокритериальнои оптимизации для оставшейся целевой функции. Заметим, что для многокритериальных задач комбинаторного типа этот подход, как правило, не эффективен.

Математическими моделями многих объектов экономики, биологии, социологии, физики, строительства и планирования являются предфрак-тальные и фрактальные графы [31]. При этом решение ряда прикладных задач по отношению к этим объектам сводится к построению покрытий

соответствующих графов звездами. В связи с этим возникла необходимость исследования многокритериальной задачи покрытия предфракталь-ных графов звездами ранговых типов.

Предпосылкой возникновения предфрактальных и фрактальных графов стало введение и исследование понятия «фрактал». Это понятие было введено в 1975 году Б. Мандельбротом с целью создания математического аппарата, предназначенного для описания объектов природы, науки и техники (конечных и бесконечных), обладающих очень сложной структурой, процессов, характеризующихся хаотически изменяющимися условиями протекания [32,33].

С математической точки зрения фрактал - это, прежде всего, множество с дробной размерностью (под размерностью понимается размерность Хаусдорфа-Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая в последствии А.С. Безиковичем) [31,33-37]. Кроме этого, следует отметить одно основополагающее свойство присущее фракталам - это свойство самоподобия, т.е. любая, даже самая малая, часть фрактала, в какой-то степени, подобна целому и является как бы уменьшенной его копией. Это свойство отличает фракталы от объектов классической геометрии.

Дальнейшее изучение фракталов осуществлялось в рамках нового междисциплинарного подхода - синергетики [32,38-41], где одной из центральных задач являлось моделирование объектов и явлений, которым присущ хаос, т.е. непредсказуемость протекающих в них процессов, отсутствие пространственной регулярности, случайность, рассогласованность поведения составляющих элементов и т.д. [38,40-42] С развитием этого направления удалось выявить регулярные законы и закономерности возникновения, казалось бы, на первый взгляд, хаотичных систем, условия протекания непредсказуемых (или, по крайней мере, очень сложных) процессов и явлений, показать фрактальные структуры, лежащие в их ос-

нове. Более того, при дальнейшем изучении оказалось, что моделирование многих фрактальных объектов физики, химии, биологии и других дисциплин сводится к составлению автономных систем обыкновенных дифференциальных уравнений, зависящих от параметров [43].

Подчеркнем, что, при исследовании дискретных объектов [4-6,17,24,28,44-56], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [40,43]. Подобные объекты моделируются средствами теории графов [1,2,57,58]. При этом, получаемые модели, обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов.

Впервые термин «фрактальный граф» возник в работах [59,60] для отражения иерархии связей с учетом варьируемой разветвленности. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова A.M. и Перепелицы В.А. [31,35,37,61-63]. Разработка этой теории показала важность и широкие возможности применения предфрактальных и фрактальных графов. Справедливо утверждение: «В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф -это, в конечном счете, один из способов выявления некоторых качеств моделируемой системы. Причем по отношению ко всей исследуемой системе речь здесь идет о таких качествах, которые не выводимы прямо из свойств элементов системы и локальных взаимодействий этих элементов» [31].

На сегодняшний день, по всей видимости, наиболее серьезные результаты теории предфрактальных и фрактальных графов представлены в [31]. В этой работе предложены полиномиальные алгоритмы распознава-

ния фрактальных графов, построены модели некоторых фрактальных объектов при помощи математического аппарата данной теории. Вычислены размерности Хаусдорфа-Безиковича для некоторых типов фрактальных графов. В [37,61] приведены некоторые результаты исследований свойств графов такого типа. Проблема построения остовного дерева фрактального графа рассмотрена в [62]. Некоторые результаты исследований задачи о кликах фрактального графа предложены в [63].

Немаловажное значение играют предфрактальные графы. В действительности не так много объектов, при моделировании которых получается фрактальный граф. Поэтому для решения конкретных задач математики и физики, экономики и биологии, химии и строительства, планирования и т.д. используются предфрактальные графы, ранг которых может выступать характеристикой степени приближения строящихся моделей к реальным объектам исследования, т.е. чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих экономических, биологических, социальных, технических и т.д. задач тесно связано с необходимостью моделирования очень сложных и изменчивых во времени структур, состоящих из большого числа элементов, применение классических методов математического моделирования [1,64-67] для решения подобных проблем не всегда представляется возможным в силу их неэффективности. Применение же теории пред-фрактальных и фрактальных графов помогает решать задачи там, где бессильны традиционные подходы.

Тем не менее, на сегодняшний день теория предфрактальных и фрактальных графов имеет недостаточное развитие для эффективного использования в практических целях. Существует ряд неизученных или слабо изученных направлений. К ним относятся:

- проблема задания предфрактальных и фрактальных графов;

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

- вопросы вычисления фрактальной размерности произвольного фрак
тального графа;

-задачи моделирования объектов с элементами структурного хаоса при помощи математического аппарата данной теории;

- проблемы построения предфрактальных и фрактальных графов с за
данными свойствами.

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

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

Основными задачами исследования, определяемыми поставленной целью, являются:

- исследование разрешимости многокритериальной задачи с помощью
алгоритма линейной свертки критериев;

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

разработка нового способа задания произвольного предфрактального графа, способного адекватно отражать структуру графов этого типа;

построение и исследование полиномиальных алгоритмов построения покрытий предфрактальных графов звездами ранговых типов;

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

Методы исследования основываются на использовании математического аппарата:

теории графов;

теории предфрактальных и фрактальных графов;

комбинаторики;

математического программирования;

многокритериальной оптимизации.

Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.

В главе 1 диссертационной работы впервые рассматривается 3-х критериальная задача покрытия предфрактальных графов звездами ранговых типов. Проводится краткий анализ допустимых ее решений. Изучается возможность решения 2-х и 3-х критериальных задач о покрытии предфрактальных графов звездами ранговых типов с помощью алгоритма линейной свертки критериев. Строится и исследуется математическая модель системы контроля трафика в Интернете, которая сводится к рассматриваемой многокритериальной задаче и может содействовать более результативной борьбе с незаконной компьютерной деятельностью в глобальной сети. Кроме того, предлагается математическая фрактально-графовая модель сети центров МЧС РФ, способная повысить эффективность работы этой службы.

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

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

В главе 3 исследуется проблема построения предфрактальных графов с заданными характеристиками. Прелагаются и обосновываются полиномиальные алгоритмы ее решения.

В диссертационной работе получены следующие новые научные результаты:

доказана неразрешимость 2-х и 3-х критериальных задач построения покрытий предфрактальных графов звездами ранговых типов с помощью алгоритма линейной свертки критериев;

впервые построены и исследованы фрактально-графовые модели системы контроля трафика в Интернете и сети центров МЧС РФ, сводимые к построению покрытий предфрактальных графов звездами ранговых типов;

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

-предложен «быстрый» алгоритм построения покрытий с указанием оценок их значений критериев;

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

Основные результаты работы докладывались и обсуждались на: -II Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (г. Нальчик, 2001); -V Всероссийском симпозиуме «Математическое моделирование и

компьютерные технологии» (г. Кисловодск, 2002); -IV научно-практической конференции «Решение научно-практических и социально-экономических проблем современности» (г. Черкесск, 2002); -Международном Российско-Узбекском симпозиуме «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Эльбрус, 2003); -VI Всероссийском симпозиуме «Математическое моделирование и

компьютерные технологии» (г. Кисловодск, 2004); -научных семинарах, проводимых в НИИ Прикладной математики и автоматизации Кабардино-Балкарского научного центра РАН (г. Нальчик, 200-2003);

-научных семинарах профессорско-преподавательского состава КЧГТА (г. Черкесск, 2000-2004). Объем и структура диссертационной работы. Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников.

Работа изложена на 118 страницах, из них 1 страница рисунков, 1 страница приложения, 10 страниц списка использованных источников, содержащего 92 наименований.

Исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки

Подчеркнем, что, при исследовании дискретных объектов [4-6,17,24,28,44-56], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [40,43]. Подобные объекты моделируются средствами теории графов [1,2,57,58]. При этом, получаемые модели, обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов.

Впервые термин «фрактальный граф» возник в работах [59,60] для отражения иерархии связей с учетом варьируемой разветвленности. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова A.M. и Перепелицы В.А. [31,35,37,61-63]. Разработка этой теории показала важность и широкие возможности применения предфрактальных и фрактальных графов. Справедливо утверждение: «В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф -это, в конечном счете, один из способов выявления некоторых качеств моделируемой системы. Причем по отношению ко всей исследуемой системе речь здесь идет о таких качествах, которые не выводимы прямо из свойств элементов системы и локальных взаимодействий этих элементов» [31].

На сегодняшний день, по всей видимости, наиболее серьезные результаты теории предфрактальных и фрактальных графов представлены в [31]. В этой работе предложены полиномиальные алгоритмы распознавания фрактальных графов, построены модели некоторых фрактальных объектов при помощи математического аппарата данной теории. Вычислены размерности Хаусдорфа-Безиковича для некоторых типов фрактальных графов. В [37,61] приведены некоторые результаты исследований свойств графов такого типа. Проблема построения остовного дерева фрактального графа рассмотрена в [62]. Некоторые результаты исследований задачи о кликах фрактального графа предложены в [63].

Немаловажное значение играют предфрактальные графы. В действительности не так много объектов, при моделировании которых получается фрактальный граф. Поэтому для решения конкретных задач математики и физики, экономики и биологии, химии и строительства, планирования и т.д. используются предфрактальные графы, ранг которых может выступать характеристикой степени приближения строящихся моделей к реальным объектам исследования, т.е. чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих экономических, биологических, социальных, технических и т.д. задач тесно связано с необходимостью моделирования очень сложных и изменчивых во времени структур, состоящих из большого числа элементов, применение классических методов математического моделирования [1,64-67] для решения подобных проблем не всегда представляется возможным в силу их неэффективности. Применение же теории пред-фрактальных и фрактальных графов помогает решать задачи там, где бессильны традиционные подходы.

Тем не менее, на сегодняшний день теория предфрактальных и фрактальных графов имеет недостаточное развитие для эффективного использования в практических целях. Существует ряд неизученных или слабо изученных направлений. К ним относятся: - проблема задания предфрактальных и фрактальных графов; -алгоритмическая проблема и, в частности, проблема решения задач многокритериальной оптимизации на графах такого типа; - вопросы вычисления фрактальной размерности произвольного фрак тального графа; -задачи моделирования объектов с элементами структурного хаоса при помощи математического аппарата данной теории; - проблемы построения предфрактальных и фрактальных графов с за данными свойствами. Возможные решения некоторых из вышеперечисленных проблем предлагаются в настоящей диссертационной работе. Целью данной диссертационной работы является развитие теоретической базы, а также разработка и совершенствование методов и алгоритмов для исследования сложных систем с элементами структурного хаоса в условиях многокритериальное. Основными задачами исследования, определяемыми поставленной целью, являются: - исследование разрешимости многокритериальной задачи с помощью алгоритма линейной свертки критериев; -изучение практической значимости многокритериальной задачи покрытия предфрактальных графов звездами ранговых типов в математическом моделировании; - разработка нового способа задания произвольного предфрактального графа, способного адекватно отражать структуру графов этого типа; - построение и исследование полиномиальных алгоритмов построения покрытий предфрактальных графов звездами ранговых типов; -разработка и исследование эффективных методов построения предфрактальных графов, для которых существуют точные решения многокритериальной задачи со значениями критериев, равными наперед заданным числам. Методы исследования основываются на использовании математического аппарата: - теории графов; - теории предфрактальных и фрактальных графов; - комбинаторики; - математического программирования; - многокритериальной оптимизации. Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами. В главе 1 диссертационной работы впервые рассматривается 3-х критериальная задача покрытия предфрактальных графов звездами ранговых типов. Проводится краткий анализ допустимых ее решений. Изучается возможность решения 2-х и 3-х критериальных задач о покрытии предфрактальных графов звездами ранговых типов с помощью алгоритма линейной свертки критериев. Строится и исследуется математическая модель системы контроля трафика в Интернете, которая сводится к рассматриваемой многокритериальной задаче и может содействовать более результативной борьбе с незаконной компьютерной деятельностью в глобальной сети. Кроме того, предлагается математическая фрактально-графовая модель сети центров МЧС РФ, способная повысить эффективность работы этой службы.

Математическая модель системы контроля трафика в Интернете

Начиная с 70-х годов XX века, человечество совершило резкий прорыв в мире информационных технологий, кульминацией которого стало появление и развитие Интернета [68-72]. На сегодняшний день Интернет - это динамично развивающаяся компьютерная система, охватывающая весь земной шар. Она играет огромную роль в жизни всего человечества, по этой причине проблемы, препятствующие ее функционированию, представляют опасность и требуют своевременного разрешения. Одной из них является проблема компьютерного пиратства и терроризма [72,73].

С физической точки зрения Интернет можно рассматривать как сложную, хаотически устроенную «паутину» локальных сетей, взаимодействующих друг с другом либо посредством межсетевых соединений, либо через специальные точки доступа к сети (NAP) [68,70,71]. Частичное упорядочивание в структуру Интернета вносит ее логический аспект. Глобальная сеть, хотя и достаточно условно, разделяется на зоны (американскую, европейскую, азиатско-тихоокеанскую и т.д.), имеющие свои реестры адресов и сетевые координационные центры. Каждая зона определяется своим географическим положением и соответствует области «сгущения» сети. Между зонами существует относительно немного каналов связи по сравнению с их количеством внутри зон, но скорость передачи данных этих каналов очень высокая [71]. Дальнейшая детализация структуры Интернета достигается за счет выделения в зонах частей сети, относящихся к отдельным государствам.

На территории каждой страны, имеющей доступ к Интернету, действуют сервис-провайдеры или, просто, провайдеры (государственные, коммерческие) - компании, предоставляющие услуги Интернета различным организациям или частным пользователям. Заметим, что многие компании и организации имеют свои локальные сети, тогда, подключаясь к провайдеру, доступ к ресурсам Интернета может быть организован с любого терминала компании, т.е. оказывается подключенной вся локальная сеть.

Сервис-провайдеры имеют в различных регионах свои точки присутствия, объединенные между собой в локальные сети. Провайдеры, охватывающие своей деятельностью всю территорию государства называются национальными. Их представительства в регионах или провайдеры с меньшей областью действия называются региональными провайдерами. Некоторые организации и локальные сети (например, Ethernet) в услугах провайдеров не нуждаются, и сами организуют себе доступ к ресурсам Интернета. Для обмена трафиком провайдеры соединяются друг с другом либо через NAP, либо посредством межсетевых соединений [71].

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

Среди таких организаций следует отметить правительственные (в том числе военные) ведомства различных государств, банковские системы, крупные корпорации. На серверах их компьютерных систем содержится очень ценная и важная информация, предназначенная не для массового пользования и защищаемая от несанкционированного доступа.

Тем не менее, в последние годы попытки такого несанкционированного доступа стали частым явлением. Некоторые из них, несмотря на всевозможные системы защиты, оказываются удачными. Кража секретной информации, заражение информационных систем компьютерными вирусами, попытки установления незаконного контроля над компьютерами, может привести к серьезным экономическим и политическим последствиям в различных частях света. По этой причине во многих странах мира «взлом» серверов и несанкционированный доступ к секретной информации считается уголовным преступлением или даже террористическим актом. Для борьбы с подобными нарушениями создан отдел Интерпола, отслеживающий незаконную деятельность в сети.

В Интернете основной принцип передачи данных основывается на том, что любая подключенная к нему локальная сеть участвует не только в обмене информацией, но и одновременно является проводником информации других сетей, т.е. организация взаимодействия двух удаленных ЭВМ означает «выстраивание» цепи десятков и даже сотен компьютеров, через которые будет проходить информация на пути от источника к получателю. Заметим, что при повторном установлении соединения цепь передачи данных может оказаться другой [69,71].

Такой способ организации Интернета сильно усложняет деятельность Интерпола по выявлению компьютерных пиратов (хакеров). Это объясняется тем, что при обнаружении несанкционированного доступа цепь, по которой организуется соединение компьютера хакера с сервером, начинает прослеживаться в обратном порядке. Если при этом цепь состоит более чем из десяти ЭВМ, то определить местоположение хакера практически не представляется возможным. Предлагается новый способ выявления источников незаконной компьютерной деятельности [73]. Его идея заключается в оптимальном подборе серверов Интернета и определении для каждого из них сегмента сети. Используя этот сервер, будет осуществляться контроль проходимого через сегмент трафика. Весь трафик снабжен маршрутной информацией, тогда контроль этой информации способен ускорить поиск терминалов, с которых осуществляется компьютерное пиратство, т.е. сделать деятельность Интерпола более эффективной.

Покажем, что структуру сети Интернет можно представить пред-фрактальным графом [24,31,35,37,62,63,73,74]. Рассмотрим граф G,=( ,,), каждой вершине и, є ,(/ = 1,2,...,FJ) которого сопоставляется зона Интернета, причем две вершины соединяются ребром, если соответствующие им зоны связаны межсетевыми соединениями. В качестве веса полученных ребер берется скорость передачи данных соединений, обозначаемых этими ребрами.

«Быстрый» алгоритм построения покрытия предфрактального графа звездами ранговых типов с оценками

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

Тем не менее, во многих задачах прикладного характера требуется получить результат, не обладающий высокой степенью точности. Для разрешения подобных проблем удобно использовать специальные алгоритмы, достоинством которых является их простота и низкая трудоемкость. В данной главе предлагается алгоритм, обладающий описанными выше особенностями [80].

Пусть задан предфрактальный взвешенный (яД,)-граф GL=(vL,EL), порожденный «-вершинной затравкой Н = (fV ,Q),\W\ = n,\Q\ = q. Пусть Я, = (г1, )(/ = 1,2,...,wL_1) - новые затравки. При этом аналогичные ребра изоморфных друг другу затравок, составленных из ребер одинакового ранга, взвешиваются одинаковыми числами.

Суть алгоритма заключается в нахождении для одной новой затравки остовного дерева минимального веса [2,62,89,90] и разбиении его на звезды, т.е. выделении звезд, покрывающих каждую его вершину, а, следовательно, и всей затравки. После этого полученный для затравки результат с учетом изоморфизма, существующего между затравками, распространяется на остальные новые затравки. При этом объединение покрытий затравок образует покрытие всего предфрактального графа звездами ранговых типов.

Следует отметить, что вместо выделения остовного дерева минимального веса для каждой новой затравки можно осуществить построение леса или покрытия затравки цепями [47-49,51,56]. После чего, разбить каждую связную компоненту на звезды.

Алгоритм состоит из двух этапов. На первом этапе строится покрытие одной новой затравки. Учиты вая изоморфизм, существующий между затравками Я, =(к , )і(/ = 1,2,...,nL ), это может быть любая затравка, составленная из новых ребер. Пусть для определенности этой затравкой будет Я, = (г\ ). Далее выполняются последовательно два подэтапа. Сначала для Я, = 1у\Е}) строится остовный подграф минимального веса Т. Учитывая ее связность, данный подэтап всегда выполним, и строит связный остов [2,90]. Это хорошо известная задача, для решения которой удобно применять алгоритм Краскала [2]. Для этого строится граф Тх = Оп + ех, присоединяя к пустому графу на множестве вершин Vі ребро є, є Ех минимального веса. Если таковых окажется несколько, то для определенности берем ребро с наименьшим порядковым номером. Если граф Tj уже построен и/си-1, то строим граф TJ+l =T}+eJ+l, где eJ+\ - ребро затравки, имеющее минимальный вес, среди ребер, не входящих в Т} и не составляющих циклов с ребрами остова Т}. Для отыскания такого ребра применяется «жадный» алгоритм [2], примененный поочередно ко всем еще не использованным в покрытии ребрам, отсортированным в порядке возрастания их весов. На втором подэтапе необходимо путем удаления некоторых ребер остова Т = {у\Е]т) построить покрытие затравки звездами. С этой целью будем строить подграф дг, = (г , ), где множество Е в начале подэтапа предполагаем пустым. Сначала, просматривая поочередно вершины остова, выделяем множество U = Vх всех его висячих вершин. Таковые всегда существуют, ибо Т - \Е\) не содержит циклов. Далее для каждой вершины и GU выделяем и фиксируем инцидентное ей ребро є є Е\, при этом получаем множество Е а Е\. таких ребер. Очевиден факт, что элементы подмножества U могут быть покрыты звездами, составленными из новых ребер, взятых из множества Е с:Е}т, ибо ни какие другие новые ребра не инцидентны вершинам и eU . Некоторые из элементов Е cz Е\ могут иметь общие вершины и образовывать звезды рангового типа больше единицы. Добавляем множество выделенных ребер Е аЕ\ к подмножеству Е\, т.е. Е =Е\ Е У и те же самые вершины в подграфе Т = \у\Е\.) вместе с инцидентными им вершинами, получаем при этом подграф, порожденный множеством ребер Е\-Е . Если полученный подграф х1=( \Е1) является покрытием затравки Я, = (к , ) звездами, то второй подэтап заканчивает свою работу. Далее следует проверить существование в подграфе G(E\. - Е ) изолированных вершин м0. Если таковые существуют, то их следует покрыть добавлением к уже существующим звездам покрытия дг, = (у1,Е ) ребер, соединяющих эти вершины с центрами звезд.

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

Предположим противное, т.е. покрытия xt = (у ,Е х) и х} = yJ,Ex ) некоторых затравок Я, и Н} соответственно содержат звезды разных ранговых типов. Но тогда покрытие х, как объединение покрытий новых затравок будет ухудшено по второму критерию. Это связано с тем, что отличные друг от друга покрытия новых затравок будут увеличивать значение второго критерия покрытия х. В случае, когда покрытия всех затравок изоморфны (например х, -\ \E xj) число ранговых типов F2(x) будет меньше исходного, ибо х не будет содержать звезд изоморфных связным компонентам из х; = \yJ,EJx ). Таким образом, каждая новая затравка покрывается звездами всех допустимых ранговых типов. Предположим, что для покрытия каждой такой затравки используется а2 звезд KluKl2,...,K]ai ранговых типов. Учитывая, что KUs покрывает 5+1 вершину, имеем w = (l + l)+(2 + l)+...+(a2+l) = —а2. Всего существует nL x новых затравок, на каждую из которых приходится а2 звезд, тогда, если для покрытия предфрактального графа не используются элементы покрытия, состоящие из старых ребер, должно выполняться равенство ах - a2nL \ где L - натуральное число. Исходя из этого, требуется найти натуральное число L так, чтобы выполнялись неравенства a2nL 2 a, a2nLX, т.е. L является наименьшим числом, удовлетворяющим неравенству Z, log„a,-logna2+l. Полученное значение берем в качестве ранга предфрактального графа. В случае выполнения равенства a2nL = а, достаточно построить GL - iyL,EL) таким образом, чтобы ни одна звезда, состоящая из старых ребер, не могла улучшить покрытие х ни по одному из критериев (это возможно, когда один конец каждого старого ребра, как отмечено выше, совпадает с центральной вершиной какой-либо звезды покрытия х). В противном случае находим разность a2nL} - а,, которая показывает сколько раз необходимо уменьшать число звезд покрытия х введением звезд, составленных из старых ребер, чтобы значение первого критерия было равно а,. Предположим, что GL - (VL,EL) уже построен и Я,, Н} две затравки, составленные из новых ребер. (Как уже отмечалось, затравки составляются так, что для них существует единственное покрытие звездами.) Для каждой из них существует по две вершины, покрываемые звездой AT,, и только ей. Пусть для Я, такими вершинами будут ий,иі2 eV, а для НJ и]Х,и]2 є VJ, т.е. существуют ребра (ий,иі2)єЕ и (uJ},uj2)e EJ, принимающие участие в покрытии как звезды ЛГ,, для соответствующих затравок. При этом следует подчеркнуть, что одни концы этих ребер (например и11ги;1) будут висячими вершинами. Если эти висячие вершины соединены ребром \рл,ил)е.Еь_х/Еь_2 ранга L-1, то оно покрывает данные вершины. Если же при этом вершины ul2,uj2 смежны центрам уже существующих звезд покрытия, то эти вершины могут быть покрыты данными звездами, добавлением к ним соответствующих ребер и увеличением рангового типа на единицу. В этом случае звезды, состоящие из ребер (w,,,w,2) и (и}1,и;2) соответственно, удаляются, в результате число элементов покрытия х уменьшается на одну звезду. Подчеркнем, что в случае, когда L=2 мы имеем и новых затравок, тогда при aznL - а, — «не хватит» затравок для осуществления нужного числа замен описанным выше способом. В этом случае алгоритм заканчивает свою работу с нулевым результатом. Далее следует второй этап алгоритма, на котором строится затравка H=(W,Q). Она покрывается звездами K1A,Ku,...,KUai, причем покрытие должно быть точным и единственным. В качестве начальных значений берем W=0, )=0. Сначала строим звезду К1а2+] и нумеруем ее вершины и ребра. Нумерацию начинаем с центральной вершины: таким образом, имеем: W = fa,u2, ..,uai+2\,Q = fa,e2,..., ?в1+,}. Далее строим звезду ЛГ1й2 с центром в висячей вершине ив2+2 с наибольшим порядковым номером уже построенной части графа. Вводим нумерацию добавленных вершин и ребер согласно уже существующей, т.е. получаем следующие множества W = {м,,и2,...,мй2+2,маз+3,. ,"2«2+Л Q = V,,e2,...,еа2+1,ейг+2,...,е2а2+1}. Далее процесс продолжается аналогичным образом: строим звезду КХаг„, так, чтобы ее центром была висячая вершина с наибольшим порядковым номером, которой будет являться вершина звезды КЛаг. Процедура построения затравки продолжается тем же способом до звезды АГи. В результате остается построить последнюю звезду AT,, с центром в висячей вершине только что построенной звезды, получившей при нумерации наибольший порядковый номер. Второй этап заканчивает свою работу. На третьем этапе строим предфрактальный граф GL =(VL,EL), старые ребра которого могут, как пересекаться, так и не пересекаться, порожденный затравкой Н, полученной на втором этапе алгоритма. Построение происходит в соответствии с определением предфрак-тального графа с одним условием: на L-ш этапе построения для первых по счету 2{a2nL ] -а,) новых затравок висячие вершины, покрываемые звездами AT,, (каждая из них имеет по построению наибольший порядковый но 91 мер среди вершин затравки, которой эта вершина принадлежит) соединяются ребрами ранга L-X. Для остальных затравок аналогичные вершины не соединяются старыми ребрами.

Все остальные старые ребра строятся по правилу: один конец старого ребра есть висячая вершина новой затравки, а второй конец ребра висячей вершиной не является, т.е. его степень больше единицы.

Докажем, что такой предфрактальный граф можно построить. Для этого нужно показать, что количество не висячих вершин новых затравок не меньше числа старых ребер \EL_\. По построению каждая новая затравка является деревом и содержит а2 вершин степени выше единицы. В предфрактальном графе содержится nL x затравок, составленных из новых ребер и a2nLl не висячих вершин. В то же время граф содержит nL 2q + nL 1q + ... + nq + q = \EL_l\ старых ребер, где q - число ребер затравки.

Похожие диссертации на Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов

Многокритериальная задача покрытия предфрактальных графов простыми цепями Павлов Дмитрий Алексеевич

Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

Планирование эксперимента в задачах анализа данных типа времени жизни Карманов Виталий Сергеевич

Методы решения задач распознавания образов комбинированного типаБорисова Ирина Артемовна

Покрытие целочисленной матрицы и задача кластерного анализаИнякин Андрей Сергеевич

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

Векторная задача покрытия графа звездами и ее приложенияТебуева Фариза Биляловна

Дискретные модели и методы решения задач типа коммивояжера большой размерности: исследование, комбинированные алгоритмы, вычислительный эксперимент, примененияСигал, Израиль Хаимович

Задачи типа пересечений уровня случайным процессом и их приложение в авиации при исследовании проблем безопасности посадкиСемаков, Сергей Львович

Алгоритмы построения расписаний для цеховых задач потокового типа с цифровым буферомКононова, Полина Александровна