Вестник Северо-Кавказского государственного технического университета 2011 №1 (26)

Подождите немного. Документ загружается.

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Процедура моделирования предметной области с использованием темпоральных деревьев

основывается на двух алгоритмах:

Алгоритм кластеризации сущностей предметной области и определения множества

темпоральных деревьев.

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

Задача разделения конечного множества сущностей предметной области на конечное

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

в условиях нечеткой информации. Имеет место следующая постановка задачи кластеризации.

В предметной области имеется

N сущностей, которые необходимо разделить на k кластеров, каждый

из которых будет реализован в СУБД в виде темпорального дерева. В общем случае

k неизвестно,

но справедливо

[

]

1, =kN. О сущностях известна некоторая дополнительная информация: перечень

атрибутов, оценка числа записей, взаимосвязи типа «родитель-потомок» с другими сущностями.

Предполагается, что для исследуемой предметной области построен граф взаимосвязей сущностей.

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

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

Экспертная оценка распределения сущностей.

Автоматическое разделение сущностей на основе наперед заданного критерия.

Смешанный подход на основе 1 и 2 способов.

Если выбран первый способ, то эксперт самостоятельно определяет количество

темпоральных деревьев и распределение сущностей по ним. Недостатком метода являются

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

снижение производительности выполнения отдельных запросов.

Для реализации автоматического распределения сущностей выберем в качестве критерия –

увеличение

средней производительности запросов к БД при заданных ограничениях СУБД

на физическую реализацию объектов. Будем считать, что для моделирования иерархических связей

между объектами используется модель «материализованного пути». Тогда имеют место следующие

ограничения реализации модели: максимально допустимый размер атрибута

max

l с ключами

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

(например, для MS SQL Server справедливо ограничение на размер индексируемого атрибута

в байтах

[]

900,1

max

∈l ). С учетом известных ограничений СУБД на реализацию иерархических

и индексных структур определим эмпирический

алгоритм кластеризации сущностей на основе

метода «минимального покрывающего дерева», т. о. алгоритм будет производить иерархическую

кластеризацию «сверху-вниз» и при этом искать решение в достаточной мере близкое

к оптимальному. Исходные данные алгоритма:

Кодирование ключа материализованного пути равномерное с

l байт на каждый уровень

иерархии дерева.

На основе известных оценок мощностей множеств объектов сущностей размечаются

ребра графа взаимосвязей сущностей селективностями их внешних ключей.

Вес ребра (в алгоритме «минимального покрывающего дерева») вычисляется

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

обрабатываемый кластер.

Предполагается, что исходный граф не содержит альтернативных путей между парами

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

с целью выполнения данного условия.

Реализация алгоритма:

Шаг 1. Обнуляем номер кластера:

Шаг 2. Если отсутствуют необработанные сущности, то останов, иначе номер кластера

увеличиваем на 1:

= ii . Текущее значение длины ключа материализованного пути

устанавливаем в 0: 0:

l .

Шаг 3. Из необработанных ранее сущностей выбирается такая, что содержит наименьшее

число кортежей и является узловой, т. е. дочерней для более чем 1 сущности. Если такой сущности

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

Шаг 4. Оценивается селективность по атрибутам внешних ключей узловой сущности.

Родительские сущности сортируются в порядке возрастания

соответствующей им селективности

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

атрибута внешнего ключа узловой сущности. Селективность сущности, имеющей уже

кластеризованных родителей, устанавливается равной 0 и сущность сортируется первой.

Шаг 5. Выбирается множество сущностей, являющихся предками сущности с минимальной

селективностью, включая ее саму. Мощность отобранного множества равна

X. Если у узловой

сущности отсутствуют необработанные предки, то отбираем множество из одной узловой

сущности: 1

Шаг 6. Если 0=

l или

0max

ll b l

+≤

∑

, где

b – число уровней иерархии данных в сущности

k, то из множества сущностей выбираем минимальные в количестве x, такие что

max

lbll

≤+

∑

kii

blll

:. Минимальные x сущностей включаются в кластер с номером i. Иначе переход

на шаг 2.

Шаг 7. Переходим на шаг 4.

На рисунке 1 представлен пример, иллюстрирующий кластеризацию предметной области из

7 сущностей на 3 кластера. Исходные данные для кластеризации: для каждой сущности указанно

ожидаемое число объектов; в каждой сущности реализован 1 уровень иерархии данных; показаны

отношения сущностей типа «родитель-потомок» с использованием дуг вида

, также

определяющих арность связи «1..

N»; средняя оценка селективности вычисляется как отношение

мощности множества объектов родительской сущности к дочерней; 1

l ; 3

max

=l . На первом шаге

узловой выбирается

Сущность6 и вычисляются селективности по атрибутам связей с Сущностью2,

Сущностью3 и Сущностью5. Для обработки выбирается цепочка сущностей

Сущность1->Сущность2, т. к. селективность внешнего ключа связи Сущности6 c Сущностью2

минимальна и равна

1000

. Выбранная цепочка помещается в кластер 1. Так как выбранные

сущности содержат по 1 уровню иерархии данных, то вес ребра графа связи сущностей равен 2.

Следующей в порядке сортировки селективности является цепочка

Сущность4->Сущность5,

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

равен 4, что превышает максимально допустимое значение 3

max

l . Оставшаяся родительская

Сущность3 по отношению к узловой Сущности6 помещается в кластер 2, организуя цепочку для

обработки

Сущность4->Сущность5->Сущность3. Сущность6 не может быть помещена в кластер 2

из-за ограничения 3

max

=l . На втором, заключительном шаге в качестве узловой выбирается

Сущность7 и безальтернативная цепочка Сущность6->Сущность7 помещается в кластер 3.

Рисунок 1 – Пример кластеризация предметной области из 7 сущностей

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Множество кластеров может быть сформировано либо экспертом, либо алгоритмом,

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

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

дерева является упорядоченная цепочка сущностей, объединенная в кластер. Каждая вершина

темпорального дерева обобщает собой объект типа, определенного исходной сущностью.

Реализация

алгоритма определения структуры темпорального дерева:

Шаг 1. Цепочка сущностей кластера определяет иерархию подчинения соответствующих

им данных. Каждая сущность определяет тип вершин темпорального дерева, начиная с его корня:

первая сущность – тип корня, вторая сущность – тип вершин второго уровня и т. д., последняя

сущность в цепочке – тип вершин листьев дерева. При этом каждая сущность может определять

несколько уровней

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

иерархии данных.

Шаг 2. Каждый объект сущности обобщается вершиной темпорального дерева

соответствующего уровня. Каждой вершине назначается уникальный ключ. Каждой вершине

сопоставляется множество пар «атрибут/значение», однозначно определяемые ключевым значением

вершины.

Шаг 3. Формируется множество дуг темпорального дерева одним из известных методов,

например, с

использованием модели смежных вершин, материализованного пути и т. п. Если

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

уникальный ключ, также определяющий положение вершины в дереве, и шаги 2 и 3 объединяются.

Шаг 4. Строятся индексы по ключам вершин и дуг дерева. В случае использования модели

материализованного пути строится индекс по атрибуту

соответствующего ключа.

3. Сравнительная оценка основных подходов к машинной реализации иерархического

представления информации

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

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

Эксперименты по оценке производительности операций манипулирования данными основных

подходов реализации иерархий: 1) списки смежных вершин, 2) списки достижимых вершин,

3) модель материализованного пути, 4) модель вложенных множеств; производились

на справочнике географических объектов, являющимся фрагментом базы данных Информационно-

образовательного портала

СКФО (http://live.ncstu.ru). На момент проведения экспериментов

справочник содержал 1069903 записей объектов адресов, в том числе актуальные данные до уровня

улиц включительно по состоянию на 01.01.2010 года, более детальные уровни (дома, квартиры

и т. п.) содержали не полные данные в связи с отсутствием информации о таких объектах. База

данных под управлением MS SQL Server 2008 R2 была размещена на ЭВМ: CPU Intel

Pentium

™

4 CPU 3.00GHz, RAM 2 Gb, HD 250Gb 7200rpm.

Оценка производительности транзакций производилась по двум направлениям:

производительность транзакций на выборку данных (поддеревьев и отдельных вершин);

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

перемещение поддеревьев).

На рисунках 2 – 7 показаны графики оценки производительности некоторых типов

транзакций для различных моделей реализации иерархий.

Анализ проведенных экспериментов показал, что наиболее предпочтительной моделью

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

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

данных. При этом

данная модель признана самой сбалансированной, т.е. среди основных операций

манипулирования данными отсутствуют операции с низкой производительностью. Наиболее

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

вершин (в ситуациях переполнения допустимого диапазона во фрагментах ключа

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

Результаты анализа

литературных источников и проведенных экспериментов по оценке

основных подходов к машинной реализации различных моделей представления иерархических

данных обобщены в таблице 1.

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Рисунок 2 – Статистика по выборке потомков

вершины

Рисунок 3 – Статистика по выборке предков вершины

Рисунок 4 – Статистика добавления

листовых вершин

Рисунок 5 – Статистика перемещения поддеревьев



Рисунок 6 – Статистика удаления листовых

вершин

Рисунок 7 – Статистика удаления поддерева

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Таблица 1 – Оценка основных подходов к машинной реализации различных моделей представления

иерархических данных

Оценка производительности Модель

Выборка

поддерева

потомков

Выборка

подмножества

предков

Выборка

непосредственных

предков / потомков

Добавление

данных

Перемещение

поддерева

Удаление

поддерева

Возможность

моделирования

ациклических

орграфов

Списки смежных

вершин

Низкая Низкая Очень высокая Высокая Очень высокая Низкая Существует

Списки достижимых

вершин

Высокая,

зависит от

предиката

Высокая,

зависит от

предиката

Высокая Средняя Низкая Низкая Требует

дополнительных

алгоритмов

преобразования

Материализованный

путь

Очень

высокая

Очень

высокая

Высокая Высокая Средняя Высокая Требует

дополнительных

алгоритмов

преобразования

Вложенные

множества

Высокая Средняя Средняя Низкая Очень

низкая

Высокая Требует

дополнительных

алгоритмов

преобразования

Литература и источники

1. Snodgrass, R. T. Developing Time-Oriented Database Applications in SQL / R. T. Snodgrass // R.T.S. – S. F. :

Morgan Kaufmann Publishers Inc., 1999.

2. Celko, Joe. Trees in SQL [Electronic resource] / Joe. Celko // Intelligent Enterprise Magazine. 2000. URL:

http://www.intelligententerprise.com/ 001020/celko.shtml

(access date 08.07.2010).

3. Ben-Gan, Itzik. Advanced Transact-SQL for SQL Server 2000 (Chapter 16) / Itzik Ben-Gan, Tom Moreau. – CA. :

APress ; Berkeley, 2000.

4. Tropashko, Vadim. Trees in SQL: Nested Sets and Materialized Path [Electronic resource] / V.Tropashko. –

DBAzine.com. Update date: 13.04.2005. URL: http://www.dbazine.com/oracle/or-articles/tropashko4

(access date: 08.07.2010).

5. Темпоральное дерево и его использование при концептуальном моделировании баз данных / М. И. Сугаков,

Д. К. Пархоменко, Ю. В. Гулевский, А. В. Маликов // Системы управления и информационные технологии. 2010.

№ 2(40). С. 99 – 104.

6. Wang, Fusheng. ArchIS: an XML-based approach to transaction-time temporal database systems / Fusheng Wang,

Carlo Zaniolo, Xin Zhou // VLDB. 2008. № 17(6). P. 1445 – 1463.

References

1. Snodgrass, R. T. Developing Time-Oriented Database Applications in SQL / R. T. Snodgrass // R.T.S. – S. F. :

Morgan Kaufmann Publishers Inc., 1999.

2. Celko, Joe. Trees in SQL [Electronic resource] / Joe. Celko // Intelligent Enterprise Magazine. 2000. URL:

http://www.intelligententerprise.com/ 001020/celko.shtml

(access date 08.07.2010).

3. Ben-Gan, Itzik. Advanced Transact-SQL for SQL Server 2000 (Chapter 16) / Itzik Ben-Gan, Tom Moreau. – CA. :

APress ; Berkeley, 2000.

4. Tropashko, Vadim. Trees in SQL: Nested Sets and Materialized Path [Electronic resource] / V.Tropashko. –

DBAzine.com. Update date: 13.04.2005. URL: http://www.dbazine.com/oracle/or-articles/tropashko4

(access date: 08.07.2010).

5. Temporal tree and its use at database conceptual modeling / M. I. Sugakov, D. K. Parkhomenko, Yu. V. Gulevskiy,

A. V. Malikov // Control systems and information technologies. 2010. № 2(40). P. 99 – 104.

6. Wang, Fusheng. ArchIS: an XML-based approach to transaction-time temporal database systems / Fusheng Wang,

Carlo Zaniolo, Xin Zhou // VLDB. 2008. № 17(6). P. 1445 – 1463.

УДК 621.39 (316.5)

ОСОБЕННОСТИ ЗАДАЧ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ

МНОГОКАНАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ МЕТОДАМИ ТЕОРИИ ИГР

Подопригора Н. Б., Федоренко И. В.

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

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

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

матричных бинарных игр со смешанными стратегиями.

Problems of information flows packing processes optimization and modeling in multi-channel information system are

shown. With reference to antagonistic effect of environment (system of contrast) it is offered to solve these problems in the limits

of matrix binary games theory with mixed strategies.

Ключевые слова: многоканальные информационные системы, мультиплексирование, моделирование,

оптимизация, теория игр.

Key words: multichannel information systems, multiplexing, modeling, optimization, theory of games.

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Модель любой системы, в том числе и многоканальной информационной системы (МИС),

представляет собой зависимость между выходными переменными (или показателями

эффективности

Q), характеризующими состояние системы, и входными переменными

(управляемыми параметрами

x) [1, 2]. При построении модели для наихудших условий

функционирования системы, например, при воздействии оптимизированных помех, вирусных атак

и т. д., в качестве показателя эффективности следует выбирать нижнюю гарантированную оценку

работы системы

∗

При уплотнении информационных потоков и каналов в составе МИС приходится решать три

задачи: классификация источника/получателя информации; распределение ресурса; управление

трафиком. Поэтому наиболее общей моделью мультиплексора, как средства уплотнения, является

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

статистического уплотнения можно представить как марковскую цепь с непрерывным

временем

и конечным числом состояний [3 – 5]. Известно много исследований, в которых детально рассмотрены

различные модели мультиплексоров как однолинейных систем с конечным и бесконечным числом мест

ожидания в очередях при разных предположениях о поступающих потоках ячеек. Так как ячейки имеют

фиксированную длину, то эти модели изучены при детерминированном времени обслуживания. Однако

только для

относительно простых мультиплексоров с преимущественно симметричной и однородной

структурой известны аналитические модели, причем далеко не всегда простые и к тому же

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

Преодоление подобных проблем, как правило, осуществляется в двух противоположных

направлениях: или путем использования имитационно-аналитических моделей с сохранением (и даже

наращиванием) сложности с целью обеспечения максимальной адекватности реальным условиям,

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

качественных (преимущественно граничных) оценок на основании ограниченного объема исходных

данных [6, 7]. В последнем случае оправданным является широко распространенное упрощенное

представление процесса генерации сообщений в виде пуассоновского случайного процесса

с экспоненциальным распределением интервалов времени между

очередными заявками на

обслуживание. Однако, как показано в [8], подобное распределение является наихудшим по критерию

предсказуемости в виде энтропии случайного процесса с заданным диапазоном значений случайных

интервалов времени и ограниченным математическим ожиданием.

В то же время теоретико-игровой подход к моделированию систем [9 – 11] допускает

использование и более точных моделей достоверно отслеживаемых процессов

неантагонистического взаимодействия элементов МИС (в том числе и мультиплексоров) и среды

пользователей в сочетании с моделями наихудшего антагонистического воздействия внешней

среды, называемой в дальнейшем системой противопоставления (СПП) [12, 13]. При этом возможно

использование в известных марковских моделях результатов моделирования процессов

мультиплексирования в условиях оптимизированных помех на канальном уровне, приведенных

в предыдущем подразделе.

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

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

обобщенного показателя эффективности многоканальной сети связи

∗

Q при наихудшей (для МИС)

стратегии системы постановки помех

∈M

от параметров х распределения энергетически-

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

При этом подразумеваются фиксированными и известными ресурсы МИС

R’

(распределяемых в соответствии со стратегией мультиплексирования m

) и ресурсы СПП P’

(являющихся частью характеристик множества

), а также динамические и информационные

ограничения. Полагая, что стратегия

описывается n-мерным вектором параметров y, и учитывая

зависимость расходуемых ресурсов СПП

P от используемой стратегии m

, можно представить

условие

∈M

в виде s-мерного вектора ограничений:

P(y)

≤

P’. (1)

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Обозначим f

(y) = P

(y) – P

’, l = 1, ..., s. Тогда задача моделирования процесса

мультиплексирования в наихудшей помеховой обстановке (при воздействии оптимизированной

помехи) может быть представлена в виде задачи:

(

)

() ( )

,min ,min,

mM у

Qmух Qm ух Q ух

∗

∗∗

∈

⎡⎤

==⎡⎤

⎣⎦

(2)

при условии выполнения ограничений:

(y)

≤

0, l = 1, ..., s . (3)

Запись оптимизационной задачи в виде (2) и (3) соответствует обобщенной постановке

задачи математического программирования [14], допускающей во многих прикладных случаях

интерпретацию такой задачи, как задачи распределения ресурсов [15, 16].

В дополнение и по аналогии с ресурсными ограничениями внешней антагонистической

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

описывается вектором параметров x,

и учитывая зависимость расходуемых ресурсов СПП

R от используемой стратегии, можно

представить условие

∈M

в виде r-мерного вектора ограничений:

R(x)

≤

R’. (4)

Обозначим

(x) = R

(x) – R

’, k = 1, ..., r. Тогда задача синтеза оптимальной стратегии

мультиплексирования

*, базирующаяся на основе модели (целевой функции) (2) может быть

представлена в виде задачи двусторонней оптимизации стратегий

и m

()

() () ( )

,max , maxmin,

Qxy Qmxmy Qxy

∗

∗∗

⎡⎤

⎣⎦

(5)

при условии выполнения ограничений:

(x)

≤

0 , k = 1,..., r ; f

(y)

≤

0 , l=1,..., s . (6)

Запись оптимизационной задачи в виде (4) – (6) соответствует обобщенной постановке

максиминной задачи математического программирования [14]. Вид целевой функции (5)

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

к одному из классов игровых задач, для которых в теории игр найдены эффективные методы

решения. Рассмотрим кратко элементы тех игровых задач, которые могут составить основу решения

задач

при моделировании и оптимизации МИС.

Наиболее исследованными являются методы решения игр, заданных в так называемой

«нормальной» матричной форме [17]. Задача оптимизации алгоритма мультиплексирования

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

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

МИС

x и СПП y. При этом все допустимые комбинации x и y можно пронумеровать и представить

в виде номеров чистых стратегий МИС (мультиплексирования)

i=1, ..., m и СПП (постановки помех)

j = 1, ..., n, а целевую функцию (функцию выигрыша МИС) можно представить в виде матрицы

выигрышей

q .

Использование смешанных стратегий [18, 19] в некотором смысле возвращает дискретную

постановку игровой задачи к непрерывной, поскольку смешанная стратегия первого (второго)

игрока представляет собой

m(n)-мерный вектор вещественных чисел x = {x

, ..., x

}∈X (y={y

, ...,

}∈Y) удовлетворяющих ограничениям X (Y):

≥ 0 , ..., x

≥ 0 (y

≥ 0 ,..., y

≥ 0), (7)

∑

(

∑

). (8)

В описанном выше виде под смешанными стратегиями понимаются распределения

вероятностей выбора игроками своих чистых стратегий. При этом функция выигрышей в матричной

игре с матрицей выигрышей

ij mn

Qq= представляет собой математическое ожидание выигрыша

первого игрока, которое определяется по формуле:

() .

ijij

Qx,y x y q

⋅⋅⋅

∑∑

(9)

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

Ситуация (x*, y*) в виде пары оптимальных стратегий игроков является ситуацией

равновесия, т. е. для любых других стратегий

x и y имеет место неравенство:

Q(x, y*)

≤

Q(x*, y*)

≤

Q(x*, y) . (10)

С другой стороны, можно трактовать (9) как частный случай целевой функции при

интерпретации параметров стратегий игроков

x = {x

, ..., x

} и y = {y

, ..., y

} в виде долей ресурсов,

распределяемых между

m элементами управляемого процесса со стороны МИС (распределения

времени передачи информации между каналами) и

n элементами – со стороны СПП (например,

распределение энергии постановщика помех между каналами) [20]. Подобная интерпретация

смешанных стратегий может также иметь вид физической смеси чистых стратегий, например,

в виде долей линий (каналов) МИС, работающих в одном из имеющихся режимов.

Результаты, представленные в статье, получены при выполнении НИР НК-430-П-8 врамках

реализации ФЦП «Научные

и научно-педагогические кадры инновационной России» на 2009 – 2013 гг.

Литература

1. Борисов, Ю. П. Математическое моделирование радиотехнических систем и устройств / Ю. П. Борисов,

В. В. Цветнов. – М. : Радио и связь, 1985. – 176 с.

2. Бусленко, Н. П. Моделирование сложных систем / Н. П. Бусленко. – М. : Наука, 1978. – 400 с.

3. Ершов, В. А. Мультисервисные телекоммуникационные сети / В. А. Ершов, Н. А. Кузнецов. – М. : Изд-во

МГТУ им. Н. Э. Баумана, 2003. – 432 с.

4. Колин, К. К. Об эффективности приоритетных дисциплин массового обслуживания / К. К. Колин //

Системы распределения информации. – М. : Наука, 1972. С. 45 – 54.

5. Muller-Closterman, B. Modeling and Analysis of Arrival Processes / B. Muller-Closterman, N. Uhl, S. Zaske //

Third German-Soviet seminar on flow control and integrated communication system. University of Dortmund. Institute for

Electronic Systems and Switching, 1991.

6. Иванов, П. М. Алгебраическое моделирование сложных систем / П. М. Иванов. – М. : Наука, 1996. – 272 с.

7. Советов, Б. Я. Моделирование систем / Б.

Я. Советов, С. А. Яковлев. – М. : Высшая школа, 1998. – 319 с.

8. Шеннон, К. Э. Работы по теории информации и кибернетике / К. Э. Шеннон. – М. : Изд-во иностр. лит., 1963. –

830 с.

9. Бондарева, О. Н. О теоретико-игровых моделях в экономике / О. Н. Бондарева. – Ленинград : Изд-во ЛГУ,

1974. – 312 с.

10. Горелик, В. Д

. Теоретико-игровые модели принятия решений в эколого-экономических системах /

В. Д. Горелик, А. Ф. Кононенко. – М. : Наука, 1982. – 353 с.

11. Кондратьев, А. И. Теоретико-игровые модели в задачах распознавания / А. И. Кондратьев. – М. : Наука,

1986. – 362 с.

12. Мальцев, А. Д. Сравнительный анализ помехозащищенности систем передачи информации в условиях

наихудших помех / А. Д

. Мальцев, С. М. Одоевский // Известия вузов. Радиоэлектроника. 1990. № 4. С. 79.

13. Чуднов, А. М. Теоретико-игровые задачи синтеза алгоритмов формирования и приема сигналов /

А. М. Чуднов // Проблемы передачи информации. 1991. № 3. С. 57 – 65.

14. Дегтярев, Ю. И. Исследование операций / Ю. И. Дегтярев. – М. : Высшая школа, 1986. – 320 с.

15. Берзин, Е. А. Оптимальное распределение ресурсов

и элементы синтеза систем / Е. А. Берзин. – М. : Сов.

радио, 1974. – 300 с.

16. Гурин, Л. С. Задачи и методы оптимального распределения ресурсов / Л. С. Гурин, А. С. Дымарский,

А. Д. Меркулов. – М. : Сов. радио, 1968. – 463 с.

17. Нейман, Д. Теория игр и экономическое поведение / Д. Нейман. – М. : Наука, 1970. – 707 с.

18. Крапивин, В. Ф

. Теоретико-игровые методы синтеза сложных систем в конфликтных ситуациях /

В. Ф. Крапивин. – М. : Сов. радио, 1972. – 192 с.

19. Петросян, Л. А. Теория игр / Л. А. Петросян, Н. А. Зенкевич, Е. А. Семина. – М. : Высшая школа, 1998. – 304 с.

20. Людвиг, В. А. Оптимальное управление скоростью передачи информации в нестационарных условиях /

В. А. Людвиг,

А. М. Чуднов // Изв. вузов. Радиоэлектроника. 1982. № 4. С. 83 – 84.

References

1. Borisov, Yu. P. Mathematical modeling of radio engineering systems and devices / Yu. P. Borisov, V. V. Tsvetnov. – M. :

Radio and communication, 1985. – 176 p.

2. Buslenko, N. P. Modeling of complex systems / N. P. Buslenko. – M. : Nauka, 1978. – 400 p.

3. Ershov, V. A. Multiservice telecommunication nets / V. A. Ershov, N. A. Kuznetsov. – M. : Published by

N. E. Bauman MGTU, 2003. – 432 p.

4. Kolin, K. K. On efficacy of mass service priority disciplines / K. K. Kolib // Information distribution systems. – M. :

Nauka, 1972. P. 45 – 54.

5. Muller-Closterman, B. Modeling and Analysis of Arrival Processes / B. Muller-Closterman, N. Uhl, S. Zaske //

Third German-Soviet seminar on flow control and integrated communication system. University of Dortmund. Institute for

Electronic Systems and Switching, 1991.

6. Ivanov, P. M. Algebraic modeling of complex systems / P. M. Ivanov. – M. : Nauka, 1996. – 272 p.

7. Sovetov, B. Ya. Modeling of systems / B. Ya. Sovetov, S. A. Yakovlev. – M. : Higher school, 1998. – 319 p.

8. Shennon, K. E. Works on theory of information and cybernetics / K. E. Shennon. – M. : PH of foreign literature,

1963. – 830 p.

9. Bondareva, O. N. On game-theoretical models in economy / O. N. Bondareva. – Leningrad : published by LGU,

1974. – 312 p.

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

10. Gorelik, V. D. Game-theoretical models of taking decisions in ecologo-economic systems / V. D. Gorelik,

A. F. Kononenko. – M. : Nauka, 1982. – 353 p.

11. Kondratiev, A. I. Game-theoretical models in identification tasks / A. I. Kondratiev. – M. : Nauka, 1986. – 362 p.

12. Maltsev, A. D. Comparative analysis of information transfer systems noise-immunity in the conditions of the worst

noise / A. D. Maltsev, S. M. Odoevskiy // News of HEI. Radio electronics, 1990. № 4. P. 79.

13. Chudnov, A. M. Game-theoretical tasks of algorithm synthesis of signals formation and receiving / A. M. Chudnov //

Problems of information transmission. 1991. № 3. P. 57 – 65.

14. Degtyarev, Yu. I. Study of operations / Yu. I. Degtyarev. – M. : Higher school, 1986. – 320 p.

15. Berzin, E. A. Optimal resource distribution and systems synthesis elements / E. A. Berzin. – M. : Soviet radio,

1974. – 300 p.

16. Gurin, L. S. Tasks and methods of resource optimal distribution / L. S. Gurin, A. S. Dymarskiy, A. D. Merkulov. –

M. : Soviet radio, 1986. – 463 p.

17. Neiman, D. Games theory and economic behavior / D. Neiman. – M. : Nauka, 1970. – 707 p.

18. Krapivin, V. F. Game-theoretical methods of complex systems synthesis in dispute situations / V. F. Krapivin. – M. :

Soviet radio, 1972. – 192 p.

19. Petrosyan, L. A. Games theory / L. A. Petrosyan, N. A. Zenkevich, E. A. Semina. – M. : Higher school, 1998. – 304 p.

20. Ludvig, V. A. Optimal control on information transfer rate in unsteady conditions / V. A. Ludvig, A. M. Chudnov //

News of HEI. Radio electronics. 1982. № 4. P. 83 – 84.

УДК 519.6; 519.17

АЛГОРИТМ ПОИСКА ЦЕНТРА ПРЕДФРАКТАЛЬНОГО ГРАФА,

СМЕЖНОСТЬ СТАРЫХ РЕБЕР КОТОРОГО СОХРАНЯЕТСЯ

Узденов

А. А.*, Кочкаров

Р. А.**

Карачаево-Черкесская государственная технологическая академия, г. Черкесск

Финансовый университет при Правительстве РФ, г. Москва

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

сохраняется. Впервые предлагается алгоритм поиска центра. Исследованы вопросы вычислительной сложности

алгоритма.

It is considered the problem concerning the center on pre-fractal graph, of which the contiguity of old ribs is kept. For the first

time it is suggested the center search algorithm as well as the problems of algorithm calculating complexity were studied.

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

Key words:pre-fractal graph, center, contiguity of old ribs, calculating complexity.

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

оборудования на графах. В частности, если граф представляет сеть дорог и вершины соответствуют

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

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

оптимальности может состоять в минимизации расстояния (или

времени проезда) от пункта

обслуживания до самой отдаленной вершины графа, т. е. в оптимизации «наихудшего варианта».

В более общей задаче требуется разместить несколько таких пунктов обслуживания. При этом самая

отдаленная вершина графа должна находиться, по крайней мере, от одного пункта обслуживания на

минимально возможном расстоянии. К таким задачам относятся задачи

размещения аварийных

служб. Поэтому объективным требованием здесь является минимизация наибольшего расстояния

от произвольной вершины графа до ближайшего к ней пункта обслуживания.

Рассмотрим предфрактальный граф =( , )

GVE

, смежность старых ребер которого

сохраняется. Пусть

G порожден затравкой (, )HWQ

[1].

Будем предполагать, что затравка

H является сильно связным графом, то есть каждая

вершина достижима из всякой другой вершины [2].

Алгоритм

работает на неориентированном графе. Для поиска кратчайшей цепи

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

Алгоритм

поиска центра

Алгоритм начинает свою работу с подграф-затравок L -го ранга

)( L

z ,

−

= .

На последнем шаге порождения предфрактального графа

G каждая вершина графа

−

была

замещена затравкой

H . Поскольку при порождении предфрактального графа действует правило

Вестник Северо-Кавказского государственного технического университета. 2011. № 1 (26)

сохранения смежности старых ребер, к каждой вершине

−

«привязываются» затравки одной

из своих вершин.

Рассмотрим подграф-затравку

()

z . Найдем кратчайшие цепи от «общей» вершины

()

до оставшихся (1)

n − вершин подграф-затравки

()

z . Среди кратчайших цепей найдем

максимальную и определим число

() () ()

1, 1

()max[(,)]

LLL

sx dx v

=−

, которое назовем числом разделения

вершины

()

Далее поочередно найдем числа разделения

() () ()

1, 1

()max[(,)]

LLL

ssj

sx dx v

=−

= , где

() ()

(, )0

dx x

для «общих» вершин всех подграф-затравок

-го ранга

)( L

z ,

−

= . Поиск кратчайших путей

(цепей) осуществляется с помощью известного алгоритма Дейкстры [3].

Найдем числа разделения для каждой общей вершины

(1)

−

подграф-затравок (1)L

−

-го ранга

(1)

−

= следующим образом:

111

(1) (1) (1) ()

()max[(,)()]

LLLL

ssjs

sx dx v sx

−−−

, где

(1) (1)

(, )0

dx x

−−

= . То есть находим кратчайшие цепи от общей вершины

(1)

−

до оставшихся

(1)n − вершин подграф-затравки

()

−

. Добавляем к длине кратчайшей цепи

(1) (1)

(,)

dx v

−−

соответствующее число разделения

()

sx , найденное для подграф-затравок предыдущего ранга,

и среди получившихся сумм выбираем максимальное. Сумма

( 1) ( 1) () ()

(, )()()

LL L L

ss s s

dx x sx sx

−−

так как

(1) (1)

(, )0

dx x

−−

= .

Указанным способом находим числа разделения

()

sx для общих вершин

()

подграф-

затравок

()

z ,

−

= до 2-го ранга включительно, то есть для всех , 1, ..., 2lLL

− .

На последнем шаге

2l = найдены числа разделения

(2)

()

sx ,

1,sn= для общих вершин

(2)

подграф-затравок 2-го ранга

(2)

z и одной подграф-затравки первого ранга

(1) (1)

zz= . Подграф-

затравка

(1)

z , по сути, соответствует графу

G из траектории

, , ...,

GG G. Тогда для каждой

вершины подграф-затравки

(1)

найдено число

(2)

()

sx ,

1,sn= .

Далее рассматриваем подграф-затравку

(1)

z как отдельный граф и находим для каждой

ее вершины

(1)

число разделения следующим образом:

1112

(1) (1) (1) ( 2)

1, 1

()max[(,)( )]

ssjs

sx dx v sx

=−

. Вершина

∗

, для которой число разделения

(1)

1,2,...,

() min[( )]

sx sx

∗

= минимальное, является центром

предфрактального графа

G .

Представим далее алгоритм

, где для поиска кратчайшего пути (цепи) между двумя

любыми вершинами графа используется П

РОЦЕДУРА ДЕЙКСТРЫ.

АЛГОРИТМ

ХОД: взвешенный предфрактальный граф (, )

LLL

GVE

ЫХОД:

∗

– центр предфрактального графа

G .

АГ 1. Для каждой вершины

()

подграф-затравки

-го ранга

)( L

z ,

−

= найти число

разделения

() () ()

1, 1

()max[(,)]

LLL

ssj

sx dx v

=−

= , где

() ()

(, )0

dx x

. Поиск кратчайших цепей между

вершинами осуществляется с помощью процедуры Дейкстры.

ЛЯ ВСЕХ 1, 2, ..., 2lL L=− − ВЫПОЛНИТЬ: