close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 519.711
АЛГОРИТМ ГЕНЕРАЦИИ ТУРНИРНЫХ ГРАФОВ
НА ОСНОВЕ МУЛЬТИЭВРИСТИЧЕСКОГО ПОДХОДА
© 2013
Е.Ф. Сайфуллина, аспирант
Тольяттинский государственный университет, Тольятти (Россия)
Ключевые слова: графы; турниры; случайная генерация; мультэвристический подход.
Аннотация: В статье рассматривается алгоритм случайной генерации графов турниров на основе мультиэвристического подхода (незавершенный метод ветвей и границ). Приводятся результаты вычислительных экспериментов для построения турнирных графов с различным числом вершин.
ВВЕДЕНИЕ
Турнир – это направленный полный граф. В турнире
состязаний данный состав игроков или команд ведет
такую игру, правилами которой запрещен ничейный
исход. Каждый игрок встречается с каждым другим
игроком по одному разу и точно один из них одерживает победу. Игроки изображаются вершинами, и для каждой пары вершин дуга идет от победителя к побежденному; так строится турнир [1].
В 1953 году H.G. Landau [2] доказал теорему, описывающую необходимое и достаточное условие того,
что заданная последовательность натуральных чисел
является последовательностью исходящих вершин графа турнира.
Теорема. Последовательность натуральных чисел
{s1 , s2 ,...,sn } , такая что 0  s1  s2  ...  sn , является последовательностью исходящих степеней графа
турнира, в том и только том случае, если
k
 si  Bk ,
i 1
1  k  n, с равенством при k  n , Bk – биноминальный коэффициент из к по 2, т.е. n(n  1) .
2
РАССМАТРИВАЕМЫЙ ПОДХОД К СЛУЧАЙНОЙ ГЕНЕРАЦИИ ГРАФОВ
В работе описывается подход к случайной генерации таких графов на основе заданной последовательности исходящих степеней. Решение этой задачи было выполнено с использованием мультиэвристического подхода (МЭП) к задачам дискретной оптимизации
[3, 4]. Приведём краткое описание решения (схему
алгоритма).
Описание каждой подзадачи включает уже выбранные дуги графа, каждая из которых является также элементом множества выбранных разделяющих элементов;
также описание подзадачи включает множество дуг,
являющихся табуированными разделяющими элементами. Стартовая задача алгоритма – два пустых множества рёбер в качестве выбранных и разделяющих элементов. На каждом шаге алгоритма (рис. 1) новый разделяющий элемент выбирается на основе алгоритма,
описанного на рис. 1.
Итак, мы фактически описали схему реализации
любого алгоритма случайной генерации графа в виде
метода ветвей и границ; согласно [5], этот алгоритм
мы в данном случае можем назвать незавершённым –
поскольку поиск всех подходящих решений нами
не производится. Далее приведём более подробное
описание алгоритма.
Вектор науки ТГУ. 2013. № 4
Вход: d=(d1,…dn) – последовательность исходящих
степеней, где di – исходящая степень i-й вершины,
i  (1,...,n) , удовлетворяющая условиям теоремы Ландау.
1. TaskList – пустой список подзадач.
2. Инициализируем стартовую подзадачу предполагаемой последовательностью исходящих вершин d:
(а) пустым списком списков запрещённых вершин
Forbidden; (б) пустым множеством рёбер E. После
этого добавляем стартовую подзадачу в TaskList.
3. Если в первой лежащей в TaskList подзадаче для d
все элементы равны 0, то завершаем алгоритм
с множеством E этой подзадачи на выходе. Если же
TaskList при этом пустой, то завершаем алгоритм
с пустым множеством на выходе.
4. Для первой лежащей в TaskList подзадачи на основе
её списка d выберем последнюю вершину i , которой соответствует наибольшая исходящая степень.
5. Выберем вершину j из списка возможных вершин,
таких что j  Forbidden [i] и не существует дуги
из вершины i в j, c вероятностью, пропорциональной
исходящей степени вершины j , т.е. dj (как уже было
отмечено, di – исходящая степень i-й вершины).
6. Если выбрать вершины на предыдущем шаге
не удалось, то удаляем данную подзадачу из списка
TaskList и переходим к шагу 3.
7. Заменяем текущую подзадачу на 2 новые подзадачи.
Левую подзадачу получаем, добавив вершину j
в Forbidden [i]. Для формирования правой подзадачи
добавляем в E дугу из вершины i в j; при этом
уменьшаем dj на 1. В списке TaskList левая подзадача заменяет текущую подзадачу, а правая подзадача
добавляется в начало списка.
8. Переходим к шагу 3.
Выход: множество рёбер E.
Итак, разработанный автором алгоритм генерации
графов турниров с заданными последовательностями
исходящих степеней основан на мультиэвристическом
подходе к решению задач дискретной оптимизации.
Причём важно отметить, что в данном случае этот подход был применён не для получения какого-либо оптимального решения или классификации образов (один
из примеров практического применения последнего
подхода приведён в [6]), а для случайной генерации.
РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА
Для проведения вычислительного эксперимента были взяты последовательности исходящих степеней,
представленные на сайте [5] для n=7, n=8, n=9. Для каждого n представлен файл, каждая строка в котором
27
Е.Ф. Сайфуллина «Алгоритм генерации турнирных графов…»
Все возможные графы
с уже полученными ограничениями
Выбираем вершину
i с наибольшей исходящей степенью и случайным образом
n
выбираем вершину j с вероятностью P  d j , где N  d

i
N
i 1
ЛЕВАЯ ПОДЗАДАЧА:
Запрещаем добавление дуг {i, j} и { j, i}
ПРАВАЯ ПОДЗАДАЧА:
1. Добавляем дугу {i, j}
2. Уменьшаем исходящую степень для вершины i на 1
Рис. 1. Схема предлагаемого алгоритма.
представляет собой одну из возможных последовательностей исходящих степеней турнира. Для проведения
были взяты первые 10 последовательностей (первые 10
строк в файле). Все эти последовательности, как несложно убедиться, удовлетворяют необходимому и
достаточному условию, описанному в теореме 1. Для
каждой из этих последовательностей описанным алгоритмом был сгенерирован граф. Результаты вычислений представлены в табл. 1, табл. 2, табл. 3.
Таблица 1. Результаты вычислительного
эксперимента для n=7
Турнир
1
2
3
4
5
6
7
8
9
10
Последовательность исходящих степеней
Время построения
графа (ms)
[6, 5, 4, 3, 2, 1, 0]
[6, 5, 4, 3, 1, 1, 1]
[6, 5, 4, 2, 2, 2, 0]
[6, 5, 4, 2, 2, 1, 1]
[6, 5, 3, 3, 3, 1, 0]
[6, 5, 3, 3, 2, 2, 0]
[6, 5, 3, 3, 2, 1, 1]
[6, 5, 3, 2, 2, 2, 1]
[6, 5, 2, 2, 2, 2, 2]
[6, 4, 4, 4, 2, 1, 0]
62
16
47
16
16
16
31
16
19
15
Таблица 2. Результаты вычислительного
эксперимента для n=8
Турнир
Последовательность исходящих степеней
Время построения
графа (ms)
1
2
3
4
5
6
7
8
9
10
[7, 6, 5, 4, 3, 2, 1, 0]
[7, 6, 5, 4, 3, 1, 1, 1]
[7, 6, 5, 4, 2, 2, 2, 0]
[7, 6, 5, 4, 2, 2, 1, 1]
[7, 6, 5, 3, 3, 3, 1, 0]
[7, 6, 5, 3, 3, 2, 2, 0]
[7, 6, 5, 3, 3, 2, 1, 1]
[7, 6, 5, 3, 2, 2, 2, 1]
[7, 6, 5, 2, 2, 2, 2, 2]
[7, 6, 4, 4, 4, 2, 1, 0]
219
594
1093
16
219
16
922
609
719
3709
28
Таблица 3. Результаты вычислительного
эксперимента для n=9
Турнир
Последовательность исходящих степеней
Время построения
графа (ms)
1
2
3
4
5
6
7
8
9
10
[8, 7, 6, 5, 4, 3, 2, 1, 0]
[8, 7, 6, 5, 4, 3, 1, 1, 1]
[8, 7, 6, 5, 4, 2, 2, 2, 0]
[8, 7, 6, 5, 4, 2, 2, 1, 1]
[8, 7, 6, 5, 3, 3, 3, 1, 0]
[8, 7, 6, 5, 3, 3, 2, 2, 0]
[8, 7, 6, 5, 3, 3, 2, 1, 1]
[8, 7, 6, 5, 3, 2, 2, 2, 1]
[8, 7, 6, 5, 2, 2, 2, 2, 2]
[8, 7, 6, 4, 4, 4, 2, 1, 0]
25828
2547
15593
16
102219
41468
16
21594
15
63
ЗАКЛЮЧЕНИЕ
В качестве продолжения работ по данной тематике
предполагается совместить результаты данной публикации с результатами предыдущих работ автора [7, 8].
Работа частично поддержана региональным грантом РФФИ №13-01-97003.
СПИСОК ЛИТЕРАТУРЫ
1. Харари Ф. Теория графов. – М.: Мир, 1973 . –
С. 241.
2. Landau H.G. On dominance relations and the structure
of animal societies. II. The condition for a score sequence, Bull. Math. Biophys. 15 (1953), P. 143–148.
3. Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis.
2006. Vol. 42, No 3, P. 335–341.
4. Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems //
В сборнике: Proceedings 8th International Conference
on Enterprise Information Systems, ICEIS 2006.
Paphos, 2006. P. 360–364.
5. Сайт «Tables of tournament score sequences»
(http://homepages.vub.ac.be/~faplastr/Tournam
ents.html)
Вектор науки ТГУ. 2013. № 4
Е.Ф. Сайфуллина «Алгоритм генерации турнирных графов…»
6. Ханова А.А., Шубина О.В. Алгоритм формирования
и оценки реализации сбалансированной системы
показателей предприятия // Известия высших учебных заведений. Северо-Кавказский регион. Серия:
Технические науки. – 2011. – № 2 (160). –
С. 145–148. Мельников Б.Ф., Сайфуллина Е.Ф.,
Применение мультиэвристического подхода для
случайной генерации графа с заданным вектором
степеней, Известия высших учебных заведений. Поволжский регион. Технические науки, 2013,
№ 3 (27). – С. 69–82.
7. Мельникова Е.А.,
Сайфуллина Е.Ф.
Подход
к проверке изоморфизма с помощью построения
инвариантов. – Вектор науки Тольяттинского Государственного Университета, 2013. – № 1 (23). –
С. 113–120.
AN ALGORITHM FOR GENERATING TOURNAMENT GRAPHS BASED
ON MULTIHEURISTIC APPROACH
© 2013
E.F. Sayfullina, postgraduate student
Togliatti State University, Togliatti (Russia)
Keywords: graphs; tournaments; random generation; multiheuristic approach.
Annotation: The article deals with the algorithm for generation of tournament graphs based on multiheuristic approach
(uncompleted branch and bound method). It presents the results of computational experiments for building of tournament
graphs with different number of vertices.
Вектор науки ТГУ. 2013. № 4
29
Документ
Категория
Без категории
Просмотров
4
Размер файла
915 Кб
Теги
турнирных, алгоритм, подход, основы, генерации, графов, мультиэвристического
1/--страниц
Пожаловаться на содержимое документа