Многокритериальная задача покрытия предфрактальных графов простыми цепями тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Павлов, Дмитрий Алексеевич

• Павлов, Дмитрий Алексеевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Павлов, Дмитрий Алексеевич

ВВЕДЕНИЕ.

ГЛАВА 1. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА ПОКРЫТИЯ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ ПРОСТЫМИ ЦЕПЯМИ.

1.1. Фрактальные и предфрактальные графы.

1.2. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К^.

1.3. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К2).

Выводы.

ГЛАВА 2. АЛГОРИТМЫ С ОЦЕНКАМИ ПОСТРОЕНИЯ ПОКРЫТИЙ ПРОСТЫМИ ЦЕПЯМИ НА ПРЕДФРАКТАЛЬНОМ ГРАФЕ.

2.1. Разработка и исследование полиномиальных алгоритмов построения покрытия К,.

2.1.1. Алгоритмы а} построения покрытия ¿-ранговыми цепями длины один.

2.1.2. Алгоритмы а2 построения покрытия ¿-ранговыми цепями длины два.

2.1.3. Алгоритмы а3 построения покрытия ¿-ранговыми цепями длины три.

2.2. Разработка и исследование полиномиальных алгоритмов построения покрытия К2.

2.2.1. Алгоритм /?! построения остовного дерева минимального веса.

2.2.2. Алгоритм /?2 выделения наибольших максимальных цепей.

Выводы.

ГЛАВА 3. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ДЕРЕВА С ЗАТРАВКОЙ ПРОСТАЯ ЦЕПЬ.

3.1. Алгоритм распознавания предфрактального графа с затравкой цепь длины один (ребро).

3.2. Алгоритм распознавания предфрактального графа с затравкой простая цепь длины g (g ребер).

Выводы.

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

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

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

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

Задача покрытия п -вершинного графа / -вершинными цепями в одно-критериальной постановке решена в [2] для частного случая, когда граф покрывается двухвершинными цепями. К настоящему времени для построения такого покрытия известен алгоритм с трудоемкостью порядка пъ элементарных операций [3]. В работе [4] предложены эвристические алгоритмы решения однокритериальных задач покрытия графов, в случае, когда на длины цепей наложены ограничения сверху. Предлагаемый в работе [5] алгоритм трудоемкости 0(п~) решает частный случай с гарантированным относительным уклонением, не превосходящем —. Что касается эффективно разрешимых классов задач покрытия графов гамильтоновыми цепями, то наиболее полно эти результаты представлены в [6]. Задача покрытия кратчайшими пересекающимися цепями достаточно подробно исследована в [7], где рассматривается оценка числа цепей в зависимости от типов графов. Но эта задача не исследовалась в оптимизационной постановке, и не имеет конкретного алгоритма построения покрытия для любого графа. В общем случае однокрите-риальная постановка задачи покрытия графа цепями содержит, как частные случаи, NP-трудные задачи [8]: покрытие графа А:-вершинными цепями, в частности, задача нахождения на графе гамильтоновой цепи минимального веса [8]. К последней задаче примыкает задача о гамильтоновых циклах и тесно связанная с ней задача коммивояжера [9-16].

Причем в целом, исследования по задачам покрытия графа носят фрагментарный характер и касаются в основном случая однокритериальных постановок. Покрытие графов цепями в многокритериальной постановке достаточно глубоко исследовались Кочкаровым A.M., Перепелиной В.А. и др. в работах [17-29]. В этих работах рассматривается проблема многокритериальное™ и предлагается вероятностный анализ алгоритмов [30,31], позволяющих доказывать теоремы о поведении алгоритмов в среднем и асимптотическом поведении.

Однако многие из этих задач моделируемых на графах, состоят из большого числа элементов, причем им присущи свойства фракталов: самоподобие, дробная фрактальная размерность, масштабная инвариантность, а также признаки динамического хаоса в траекториях моделируемого процесса [32-35]. Как только задачи становятся большой размерности, они становятся трудно решаемыми в смысле вычислений, поэтому для моделирования таких задач классические методы теории графов оказываются неэффективными.

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

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

Также заметим, что весьма многочисленный список экстремальных задач [36-40] на графах представляет собой класс /^/"-трудных задач с точки зрения дискретной оптимизации. Здесь уместно отметить, что, например, известная задача нахождения (распознавания) гамильтонова цикла становится полиномиально разрешимой на канонических предфрактальных графах с полной затравкой Я = (Ж,0 в случае, когда старые ребра не пересекаются. Аналогичные утверждения справедливы и для других задач из этого списка. Снижение трудоемкости экстремальных задач на предфрактальных графах обусловлено тем, что на этих графах для некоторых задач, наряду со свойством самоподобия, появляется свойство наследственности.

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

Предпосылкой возникновения фрактальных и предфрактальных графов, явилось понятие «фрактала». Оно было введено в обращение французским математиком Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, в физике ценность подобных идей была осознана лишь в 70-е годы нашего столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла замечательная книга Б.Мандельброта «Фрактальная геометрия природы» [41]. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаус-дорфа - Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая впоследствии A.C. Безиковичем) [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. распознавание фрактальных графов;

2. вычисление размерности фрактальных графов;

3. оптимизационные задачи на фрактальных графах.

В направлении 1 исследования получили свою разработку в работах Кочкарова A.M. Представленными в [44] результатами осуществлено выделение и конструктивное обоснование полиномиально разрешимого [8] класса задач распознавания свойства предфрактальности графов, полученных в процессе моделирования специфических объектов дискретной природы.

В работах [43,44] вычислены размерности Хаусдорфа- Безиковича для некоторых типов фрактальных графов.

В направлении 3 исследования проводятся Кочкаровым A.M. и его учениками.

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

В диссертации задача покрытия предфрактальных графов простыми цепями рассматривается в многокритериальной постановке [38-40,73-77]. Что позволяет оценить покрытие не одним, а несколькими критериями, которые в силу своей разнородности невозможно адекватно представить в виде одной интегральной целевой функции.

При формулировке многокритериальной задачи оптимизации, как и в классических постановках однокритериальной оптимизации, с помощью системы ограничений или другим способом задается множество X = {jc} допустимых решений (альтернатив, вариантов, планов и т.п.), на котором определены целевые функции Fk (х), к = \,т .

При решении многокритериальной задачи требуется по возможности отыскать такое iel, на котором некоторая часть целевых функций достигала бы минимума, а оставшаяся часть - максимума. Так как критерий Fk (х) —» max всегда можно заменить на - Fk(x) —» min , то в дальнейшем условимся считать, что в многокритериальной задачи оптимизации все целевые функции минимизируются:

Fj(x) -» min , F2(x) min , ., Fm(x) —» min ,{m> 2). Многокритериальная задача оказывается разрешимой в вышеуказант ном смысле, если будет не пустым пересечение [>\Хк , где Xк - множество к= 1 всех решений х е X, на каждом из которых значение функции Fk(x) достигает минимума.

Проблема многокритериальной оптимизации возникает тогда, когда т

Хк - 0. В этом случае, какое бы фиксированное х() е X мы ни взяли в ка

А-1 честве искомого решения задачи, найдется другое решение х, е X, на котором значение хотя бы одной целевой функции Fk(xx) меньше, чем Fk{x()). Таким образом, предложить универсальное правило (алгоритм) выбора одного «наилучшего» решения не представляется возможны. Поэтому вопрос определения так называемого векторного оптимума относится к компетенции лица, принимающего решения (ЛПР).

В этих условиях решить многокритериальную задачу - значит найти не одно решение, а множество так называемых Парето-оптимальных решений. Элемент х0 е X называется Парето-оптимальным решением (по критериям

Fl(x), ., Р]п(х)), если он удовлетворяет следующему условию: не существует такого элемента у е X, чтобы среди неравенств

Ь\{у)<Рк{х),к = \^п было хотя бы одно строгое.

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

У(Х()) = Г(Х),гд.е

Ь\Х) = №(х),Р2(х),.,Рт(х)) \ х е X} будем называть полным решением.

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

Рассмотрим наиболее распространенные методы нахождения векторного оптимума.

I. Свертка [38,54,73]. При этом подходе искомым векторным оптимумом объявляется такое решение, на котором достигает минимума единственная функция - свертка исходных целевых функций. Чаще всего она определяется в виде суммы: т к=\ где Fk(x)~ нормированное значение функции Fk(x), hk- коэффициент относи сительной важности к-ой целевой функции, hk > 0, ^h.k = 1. к=1

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

Fk" {х) = -L Fk {х) или Fk" {х) = -th^L t ak Ak - ak где Ak = max Fk (x), ak = min Fk (x). xeX xeX m

Иногда свертку определяют в виде произведения Р{х) = ]~J Fk (x). Так=1 кая форма свертки наиболее приемлема для постановок типа задач надежности, в которых функции Fk(x) означают вероятность отказов или вероятность безотказной работы.

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

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

2) Существуют такие наборы целевых функций F{(x), ., Fm{x), что свертка не достигает минимума ни при каких значениях х е X . Это означает, что некоторые интересные для ЛПР решения в принципе нельзя найти с помощью свертки.

Этих недостатков удается в некоторой степени избежать, если вместо линейной свертки 3(х) использовать функцию следующего вида: 1 т к=1 где s > 1.

II. Нахождение лексико-графического [38,78] оптимума.

При этом подходе необходимым условием получения приемлемого решения многокритериальной задачи является ранжирование (линейное упорядочивание) критериев Fk(x), к = \,т, по важности. Для ранжирования по важности критериев наиболее изученным является случай, когда искомое решение является лексико-графическим Парето-оптимальным решением [38,78]. Поиск лексико-графического Парето-оптимального решения осуществляется по правилу: добивайся улучшения по более важному критерию за счет любых потерь по всем остальным менее важным критериям. Это правило, в частности, означает, что для любой пары упорядоченных критериев Fk(x) и F/(x) один из них в «бесконечное число раз» важнее другого.

III. Введение метрики в пространстве целевых функций [38].

Естественно, что в случае, когда все минимумы min Fk(x) = ак , к = \,т достигаются при одном и том же значении х0, многокритериальная задача решена однозначно. В общем случае этого, конечно же, ожидать нельзя, и тогда напрашивается такое определение векторного оптимума х0, для которого вектор F0 (х0) = (/*j ), F2 (х0 ),., Fm (x0 )) наименее удален от вектора a = (al,a2,.iam).

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

Очевидно, что при этом подходе все числа ак должны быть положительными.

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

IV. Численные методы построения Парето-оптимальных решений [79].

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

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

Область дискретной векторной оптимизации еще мала изучена. Основанный на методе построения последовательности планов подход к решению дискретных многокритериальных задач изложен в книге [80], алгоритмы, использующие идеи «просеивания» решений, предложены в [81,82]. Методы решения многокритериальных задач с булевыми переменными излагаются в работах [73,83-86]. Отметим также работу [87], посвященную многокритериальной задачи теории расписаний, и работу [88], в которой исследуется полиматричная задача коммивояжера.

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

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

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

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

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

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

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

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

В настоящей работе решается ряд обозначенных выше проблем.

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

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

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

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

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

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

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

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

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

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

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

Перейдем к изложению содержания диссертации.

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

Впервые рассматривается четырехкритериальная постановка задачи о покрытии пред фрактального графа простыми непересекающимися цепями покрытие вида КД Строится математическая модель корпоративной сети с распределенной вычислительной системой, которая может содействовать эффективной организации вычислительного процесса.

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

Вторая глава посвящена построению алгоритмов с оценками покрытия простыми цепями двух типов, а именно непересекающимися и пересекающимися простыми цепями. Для покрытия простыми непересекающимися цепями - типа рассматриваются и обосновываются алгоритмы построения покрытия Ь - ранговыми цепями длины один (одно ребро), Ь - ранговыми цепями длины два (два ребра) и Ь - ранговыми цепями длины три (три ребра). Все приведенные алгоритмы являются полиномиальными и основаны на алгоритме выделения совершенного паросочетания минимального веса, предложенного Эдмонсом [10,11], который представлен в алгоритмах в виде процедуры. Причем каждый из рассмотренных алгоритмов строит парето-оптимальное решение многокритериальной задачи, а также даются и обосновываются оценки значений критериев для построенных решений.

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

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

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

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

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

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

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

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

По теме диссертационной работы опубликовано 12 печатных работ.

Основные результаты работы докладывались и обсуждались на:

- IV Научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (г.Черкесск, 2002);

- XVI Международной научной конференции «Математические методы в технике и технологиях» (г.Санкт-Петербург, 2003);

- XVII Международной научной конференции «Математические методы в технике и технологиях» (г.Кострома, 2004);

- VI Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г.Кисловодск, 2004);

- Научных семинарах профессорско-преподавательского состава КЧГТА (г.Черкесск, 2001-2004).

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

Заключение диссертации по теме «Теоретические основы информатики», Павлов, Дмитрий Алексеевич

Выводы

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

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

ЗАКЛЮЧЕНИЕ

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

При этом получены следующие новые научные результаты:

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

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

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

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

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

1. Мелихов А.H., Берштейя J1.С. Курейчик В.М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974.

2. Geojfrion A. Solving bicriterion mathematical programs. Oper. Res., 1967, V. 15, №1, p.39-54.

3. Карзапов A.B. Экономные реализации алгоритмов Эдмонса нахождения паросочетания максимальной мощности и максимального веса / Исследования по дискретной оптимизации. -М.: Наука, 1976, С.306-327.

4. Лихолат H.A. Об одной задаче оптимального покрытия графа / Исследование операций и АСУ. Киев: Вища школа, 1978, вып.II, С.117-121.

5. Сердюков А.И. К задаче о покрытии //Управляемые системы. -Новосибирск, 1975, Вып. 14. С.24-32.

6. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной математики // Изв. АН СССР. Техническая кибернетика, №6, 1982, С.25-46.

7. Юшмалов C.B. Маршруты в графах и связанные с ними множества вершин: Дисс. канд. физ.-мат.наук: 01.01.09/ Моск. гос. ун-т. М. 1982, С.102.

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

9. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы матроиды, алгоритмы. -Ижевск: НИЦ "РХД", 2001.

10. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.11 .Берж К. Теория графов и ее применения. М.: Иностр. лит., 1962.

11. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.

12. ХЪ.Оре О. Теория графов. М.: Наука. Гл. ред. физ.-мат. лит., 1980.

13. Свами М, Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

14. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

15. Харари Ф. Теория графов.-М.Мир, 1973.17 .Кочкаров A.M. Многокритериальная задача покрытия графа цепями заданной длины. В сб. Математические вопросы исследования операций.-Минск:НИИ ЭМП. 1982,- С.42-49.

16. Кочкаров A.M. Двукритериальная задача покрытия графа цепями. IX Межреспубликанская конференция молодых ученых "Совершенствование метода планирования и повышения эффективности общественного производства". Тез. докл.- Минск: 1982.-С.144.

17. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. //"Вест.Белорус, ун-та", сер.1, физ. мат. и мех., Минск, 1982., Деп. в ВИНИТИ, 30.06.82г. №3387-82, С.1-17.

18. Кочкаров A.M., Мартынова С.А., Перепелица В.А. Экспериментальный анализ приближенных алгоритмов покрытия графа цепями. Минск, 1983г. деп. в Бел.НИИНТИ, 02.08.83, №752 Бе-Д 83.-С. 1-11.

19. Кочкаров A.M. Асимптотический подход к многокритериальной задаче покрытия графа цепями //Доклады АН БССР, 1983 Т. ХХУ,№ 10.-С.911-913.

20. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. Математические методы в исследовании операций. Тез. докл. Международной конференции НРБ, София, 1983.-С.42-43.

21. Кочкаров A.M., Перепелица В.А. Статистическая эффективность алгоритмов для полиматричных задач покрытия графа цепями. Республиканский семинар по дискретной оптимизации. Тез. докл. 1985.-Киев.-С.88-90.

22. ЗЗ.Мелроуз Дж. Иерархические фрактальные графы и блуждания на них . В сб. Фракталы в физике М.: Мир, 1988.-С.519-523.

23. М.Турбин А.Ф., Працевитый Н.В. Фрактальные множества. Функции, распределения.-Киев:Наук. думка, 1992.

24. Федер Е. Фракталы. -М.: Мир, 1991.

25. Емеличев В.А., Перепелица В.А., Козырев В.А. Обзор некоторых проблем дискретной многокритериальной оптимизации. // Труды сем. по дискретной математике и ее прилож. -М.: МГУ,1989.-С.13-17.

26. Перепелица В.А. Об одном классе многокритериальных задач на графах и гиперграфах //Кибернетика.-1984.-№4.-С.62-67.

27. Перепелица В.А., Мамедов A.A. Исследование сложности разрешимости векторных задач на графах. Черкесск: КЧТИ, 1995.

28. Перепелица В.А., Сергиенко И.В. Полиномиальные и NP-полные многокритериальные задачи перечисления альтернатив. В сб. Теор. и прогр. реализ. мет. дискр. оптимиз.-Киев.ИК АН СССР, 1989.-С.58-69.

29. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. -Киев: Наук, думка, 1988.41 .Манделъброт Б. Фрактальная геометрия природы. М.: ИКИ, 2002.

30. А2.Божокип C.B., Паршин Д.А. Фракталы и мультифракталы. Ижевск: НИЦ «РХД», 2001.

31. АЪ .Кочкаров A.M., Перепелица В.А., Сергеева Л.Н. Фрактальные графы и их размерность. Черкесск ,1996г. Деп. в ВИНИТИ, № 3284-В96, С. 1-34.

32. Кочкаров A.M. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО.-1998.

33. Курдюмов С.П., Малинецкий P.P., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В кн. Новое в синергетике. Загадки мира неравновесных структур.-М.:Наука, 1996 -С.95-164 .

34. Малинецкий Г.Г., Попов А.Б. Нелинейность. Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур.-М.:Наука, 1996.-С.95-164.

35. AI .Шустер Г. Детерминированный хаос. Введение.-М.:Мир, 1998.

36. Гласс А., Мэки М. От часов к хаосу: Ритмы жизни. -М.: Мир, 1991.

37. Евин ИЛ. Синергетика искусства. -М.: 1993.

38. Haken И. Synergetics, Springer, 1997.51 .Кочкаров A.M., Перепелица В.А. Оценки сложности многокритериальных транспортных задач. Республиканский семинар по дискретной оптимизации. Тез. докл. Киев, ИК АН СССР, 1985. С.88-89.

39. Кочкаров A.M., Перепелица В.А. К оценкам сложности нахождения множеств альтернатив для многокритериальных задач об остовных деревьях. Всесоюзная конференция "Проблемы теоретической кибернетики". Тез. докл. 4.1-Горький: ГГУ, 1988,- С. 178-179.

40. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.-М.:Наука, 1990.

41. Ope О. Графы и их применение. М.: Мир, 1965.51 .Зыков A.A. Основы теории графов. М.: Наука. Гл. ред. физ.-мат. лит., 1987.

42. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука. Гл. ред. физ.-мат. лит., 1985.

43. Tamm У. Теория графов. М.: Мир, 1988.

44. Кочкаров A.M., Перепелица В.А. О гамильтоновости фрактальных графов. Международная конференция "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики". Тез. докл.- Нальчик, НИИ ПМиА КБНЦ РАН, 1996. -С.52-53.

45. Кочкаров A.M., Перепелица В. А. Метрические характеристики фрактального и предфрактального графа. Сб. РАН САО,-1999.

46. Кочкаров A.M., Перепелица В.А. Число внутренней устойчивости предфрактального и фрактального графа. // РАН САО.-1999.

47. А.Ковалев М.М. Дискретная оптимизация. Минск: Изд-во БГУ, 1977.

48. Костевич А .С, Лапко А.А. Теория игр. Исследование операций.-Минск; "Высшая школа". 1982.

49. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач. //Дискретная математика.-1994, вып.1.-С.З-33.77 .Подия овский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.

50. Вентцелъ Е.С. Исследование операций: задачи, принципы, методология. -М.: Наука, 1980.

51. Моисеев Н.Н. Математические задачи системного анализа. -М.:Наука, 1979.

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

53. Комлик В.И., Курелинков В.И., Ромашкина Н.В. Об одном алгоритме построения множества неулучшаемых планов.// Авоматизир. системы план, расчетов в республ. плановых органах, 1977, вып.9, С.18-21.

54. Buckley Т. Atoll decompositions of graphs "The Graphs Theory", 1982, 6, № 3, p.362-390.8Ь.Dinkelbach W. On nonlinear fractional programming. Manag. Sc. 3, 1967.

55. Козакова М.Ф. Нахождение оптимумов Парето в полиметрической задаче коммивояжера. В кн.: Математические методы решения экономических задач. -М.: Наука, 1974, №5, с.55-61.

56. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации.// Проблемы кибернетики, -1975. вып. 31, С.35-42.

57. Павлов Д.А., Кочкаров P.A., Узденов A.A. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах. Препринт. РАН CAO. Нижний Архыз. 2004 -С. 1 -16.

58. Павлов ДА. Многокритериальная задача покрытия фрактальных и предфрактальных графов простыми цепями. Черкесск, КЧГТА, 2004, Деп. в ВИНИТИ, №1248-В2004. С. 1-12.

59. Павлов Д.А. Полиномиальный алгоритм нахождения максимального паросочетания на предфрактальных графах// Сб. трудов XVII Международ, науч. конф. «Математические методы в технике и технологиях». Кострома: КГТУ, 2004. -С.140-141.

60. Павлов ДА. Двухкритериальная задача покрытия предфрактального графа цепями длины г (т = 1,2,3)// Сб. трудов IV научно-практическойконференции «Решение научно-технических и социальноэкономических проблем современности». Черкесск, 2002. -С.31-33.

61. Павлов Д.А., Кочкаров А.А. Алгоритмы решения многокритериальной задачи покрытия предфрактальных графов пересекающимися простыми цепями. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-27.

62. Павлов Д.А. Оценка покрытия предфрактального графа кратчайшими простыми цепями// VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004. С. 15-17.

63. Павлов Д.А., Салпагаров С.И. Многокритериальная задача выделения маршрутов на предфрактальном графе// Известия ТРТУ. Таганрог: ТРТУ, 2004,

64. Павлов Д.А. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах// Сб. трудов XVI Международ, науч. конф. «Математические методы в технике и технологиях». Санкт-Петербург: СПГТИ, 2003. -С. 186-187.

65. Павлов Д.А., Узденов А.А. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой полный «-вершинный граф. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-9.

66. Кочкаров A.M. Алгоритмические вопросы теории фрактальных графов: Дисс. док.физ.-мат. наук: 05.13.16. Черкесск: КЧТИ, 1998.

67. Смирнов Б. М. Фрактальные кластеры //Успехи физических наук,-1986. -Т.149, вып. 2.-С. 177-213.