УДК 004.3 +519.6

Россия, МГТУ им. Н.Э. Баумана

vaovchinnikov@gmail.com

gsivanova@gmail.com

alex_wonderland@mail.ru

Введение

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

В работах [2, 3, 4, 5, 6, и др.] рассмотрен ряд методов и приёмов снижения вычислительной сложности алгоритмов на множествах и графах. Одним из наиболее эффективных методов снижения последней является сокращение времени выполнения основных операций, производимых над ультраграфами. Однако авторам не известны работы, посвящённые исследованию оптимизирующих преобразований алгоритмов операций над ультраграфами.

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

В разделе «экспериментальные исследования» даётся характеристика ультраграфа, на котором проводились исследования, Обсуждаются их результаты. Показана высокая эффективность применённых преобразований.

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

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

Обозначение операции:

H_U1(X₁,U₁) = H_U (X,U) + H_U^к(x_k, {U_k⁺, U_k^–}).

Здесь:     x_k добавляемая вершина;    U_k⁺ =Г₁x_k – множество ребер, ей инцидентных;

     U_k^– =Г₂x_k – множество ребер, которым она инцидентна.

Порядок выполнения операции:

1. Создаем множества X₁, Г₁X₁ и Г₂X₁:

X₁ = X . x_k;  Г₁X₁ = Г₁X.Г₁ x_k;   Г₂X₁ = Г₂ X.Г₂ x_k.

2. Копируем множество Uпод именем U₁:

U₁ = U.

3. Определяем множество образов ребер Г₂U₁, занося в него Г₂u_j из множества Г₂U, если ребро u_j не принадлежит U_k^–, и добавляя вершину x_k в образы тех ребер, которым она инцидентна:

4. Формируем множество прообразов ребер Г₁U₁, занося в него Г₁u_jиз множества Г₁U, если ребро u_j не принадлежит U_k⁺, и добавляя вершину x_k в образы тех ребер, которые ей инцидентны.

5. Создаем множество образов F₁X₁ вершин относительно предиката смежности F₁, занося F₁x_iиз F₁X, если вершина x_k не инцидентна ребрам, которые принадлежат образу Г₁x_iвершины x_i, и добавляя в F₁x_i вершину x_k в противном случае. Определяем вершины, смежные добавляемой, и заносим их в F₁X₁.

где

6. Формируем множество прообразов F₁^-1X₁, занося F₁^-1x_i  из F₁^-1X, если вершине x_kне инцидентны ребра прообраза Г₂x_i, и добавляя в F₁^-1x_iвершину x_kв противном случае. Определяем вершины прообраза F₁^-1x_kи заносим его в множество F₁^-1X₁.

где

7. Определяем множество образов ребер F₂U₁, копируя в него F₂u_j из F₂U, если ребро u_jне принадлежит U_k^–. В противном случае добавляем в F₂u_j не принадлежащие ему ребра множества U_k⁺.

8. Формируем множество прообразов ребер F₂^–1U₁, копируя в него F₂^–1u_j из F₂^–1U, если ребро u_j не принадлежит U_k⁺. В противном случае добавляем в F₂^–1u_j не принадлежащие ему ребра множества U_k^–.

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

– проверка условия u_j ∉ Г₂x_k требует максимум |Г₂x_k| сравнений,

– при благоприятном исходе выполняется копирование |Г₂u_j| элементов,

– количество благоприятных исходов равно |U₁| – |Г₂x_k|,

– количество противоположных исходов равно |Г₂x_k| и при каждом таком исходе происходит копирование |{Г₂u_j· x_k}| элементов. Будем считать, что при любом исходе копируется |Г₂x_k| элементов. Отсюда суммарное количество операций будет

(|Г₂x_k| + |Г₂u_j|) ´ (|U₁| – |Г₂x_k|) + |Г₂x_k| ´ |Г₂u_j|.

Оценки сложности формирования множеств аналитического представления ультраграфа приведены в таблице 1. В ней использованы обозначения n= |X| и m= |U|.

Таблица 1 – Оценки сложности формирования множеств при выполнении операции добавления вершины

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

-   в худшем O(m³) при m>n, если |Г₂x_k |, |Г₁x_k | и |F₂u_j| или |Г₂x_k|, |Г₁x_k | и |F₂^–1u_j| ограничены величиной m, и O(m²n) при n>m, если |Г₂x_k | и |Г₁x_i|  или |Г₁x_k | и |Г₂x_i| ограничены величиной m.

-   в лучшем O(m) при m>n или O(n) при n>m, если мощности образов и прообразов вершин и ребер ограничены константой.

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

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

Таблица 2 – Оптимизирующие преобразования и их вклад в снижение вычислительной сложности

2 Реализация и экспериментальные исследования

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

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

Измерения проводились для ультраграфа с мощностями множества вершин и множества ребер n = m = 1000. Множества аналитического представления ультраграфа генерировались с помощью датчика случайных чисел с использованием соотношений:

где ρ⁺(x_i) = |Г₁x_i| и ρ^-(x_i) = |Г₂x_i| – количество рёбер, инцидентных вершине x_i, и количество рёбер, которым она инцидентна, A⁺(u_j) = |Г₂u_j| и A^-(u_j) = |Г₁u_j| – количество вершин, инцидентных ребру u_j, и количество вершин, которым оно инцидентно. Значения указанных параметров менялось в диапазоне 1 ≤ ρ⁺(x_i) + ρ^-(x_i) ≤ 100 и 2 ≤ A⁺(u_j) + A^-(u_j) 1 ≤ 100.

Количество измерений для оценки времени выполнения операции в каждом случае составляло 100 повторений, результаты измерений усреднялись. При этом среднеквадратичное отклонение не превышало 7–10 % от среднего значения.

На рисунке 1 показан вклад в снижение вычислительной сложности разных видов оптимизирующих преобразований при представлении образов и прообразов вершин и рёбер ультраграфа вектором списков и различных значениях мощности множеств образов и праобразов вершин и ребер (один, десять и пятьдесят процентов от n=m=1000). Оценка выигрыша от оптимизации произведена в процентах с использованием соотношения:

[(t^неопт – t^оптi) / t^неопт] 100%

где t^неопт – время выполнения операции без применения оптимизирующих преобразований, t^оптi – время выполнения операции с применением i-го оптимизирующего преобразования.

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

Как видно из данных, представленных на рисунке 1, наибольший эффект дает применение оптимизирующего преобразования 1-го вида, что можно объяснить исключением большого количества операций копирования элементов множеств во всех пунктах алгоритма. Суммарный выигрыш от применения описанных выше оптимизирующих преобразований составил в ряде случаев от 53 до 87 % от исходного времени выполнения операции добавления вершины в ультраграф. Больший вклад третьего оптимизирующего преобразования по сравнению с вторым объясняется тем, что как правило, |F₂u_j | > |Г₁x_k| и |F₂^-1u_j| > |Г₂x_k| в пределе в |Г₂u_j| раз.

Эффективность и возможность применения использованных для оценки оптимизирующих преобразований напрямую зависит от выбранной структуры представления данных. Так, например, при матричном представлении ультраграфа невозможно применить преобразование 1, а преобразования 2 и 3 сводятся к попарному сравнению элементов строк таблиц истинности соответствующих двуместных и одноместных предикатов. Например, при определении Г₁x_i  Г₂x_k выполняется попарное сравнение элементов i-ой строки матрицы истинности двуместного предиката Г₁(X, U) – «вершинам множества Xинцидентны рёбра множества U» с элементами характеристического вектора одноместного предиката Г₂x_k(U) «рёбра множества U, которым инцидентна вершина x_k».

На рисунке 2 показаны значения времени выполнения операции добавления вершины для матричного и аналитического представления ультраграфа при различных значениях мощности множеств образов и прообразов вершин и рёбер (1 % и 10 % от n = m = 1000).

Рисунок 2 – Зависимость времени выполнения операции добавления вершины к ультраграфу от структуры данных и связности ультраграфа

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

Заключение

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

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

Список литературы

1. Овчинников В.А. Математические модели объектов задач структурного синтеза // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 3. Режим доступа: http://technomag.edu.ru/doc/115712.html (дата обращения 25.01.2013).

2. Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Вильямс, 2001. 384 с.

3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: пер. с англ. М.: Мир, 1981. 368 с.

4. Новиков Ф. А. Дискретная математика для программистов. СПб: Питер, 2001. 304 c.

5. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с.

6. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука. Гл. ред. физ.-мат. лит., 1988. 336 с.

7 Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем. Часть 2 // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 11. Режим доступа: http://technomag.edu.ru/doc/133223.html (дата обращения 25.01.2013).

8. Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем. Часть 3 // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2009. № 12. Режим доступа: http://technomag.edu.ru/doc/134335.html (дата обращения 25.01.2013).

9. Овчинников В.А. Операции над упорядоченными множествами // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2011. № 6. Режим доступа: http://technomag.edu.ru/doc/188322.html (дата обращения 25.01.2013).

10. Овчинников В.А., Иванова Г. С. Оценка эффективности применения операций над упорядоченными множествами // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2011. № 10. Режим доступа:  http://technomag.edu.ru/doc/239406.html (дата обращения 25.01.2013).

11. Иванова Г.С., Пасечников К.А. Синтез оптимальных структур данных для решения задач на графах // Вестник МГТУ имени Н.Э. Баумана. Сер. Приборостроение. 2008.  № 4 (73).  C. 29-38.