Алгоритмы нескольких махов

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 04.08.2016
Размер файла 1,4 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Некоторые сведения из теории графов

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

2.1 Алгоритм поиска в ширину (BFS)

2.2 Поиск в ширину с дополнительной сортировкой (MNS)

2.3 Лексикографический поиск в ширину (LBFS)

2.4 Алгоритм LBFS+

2.5 Алгоритм "трех махов" для распознавания единичных интервальных графов

2.6 Алгоритм LBFS*

2.7 Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов

3. Программные модули проекта

3.1 Представление графа в памяти ЭВМ

3.2 Программа задания единичного интервального графа

3.3 Программа задания интервального графа

3.4 Программа задания случайных графов Эрдёша - Реньи

3.5 Программа добавления/удаления ребер графа

3.6 Программа распознавания единичного интервального графа

3.7 Программа распознавания единичного или интервального графа

3.8 Подпрограмма изменения последовательности вершин графа

4. Результаты численных экспериментов

4.1 Тестирование алгоритма четырех махов

4.2 Исследования временных затрат алгоритмов

Заключение

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

Введение

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

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

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

Рис.1 - Пример интервального графа

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

Единичные интервальные графы -- граф пересечений интервалов одинаковой длины.

Применение интервальных графов:

Графы интервалов рассматривались для построения моделей в биологии [1]

- при построения модели ДНК - участки ДНК, за которые отвечают разные гены, могут пересекаться;

в археологии[1]

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

для транспортных потоков[1]

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

И т.д.

В работе [2] D. G. Corneil был предложен трехмаховый (трехпроходный) алгоритм для распознавания единичных интервальных графов. Вершины графа упорядочиваются с помощью лексикографического поиска в ширину [3] в некоторую последовательность. Полученный порядок вершин проверяется на соответствие совершенному порядку исключения вершин [4] и делается вывод о том, является ли граф единичным интервальным. Для распознавания интервальных графов были предложены различные многомаховые алгоритмы, например в работе [5] предложен шестимаховый алгоритм, а в работе [6] четырехмаховый. В некоторых случаях алгоритм с сортировкой [7] может быть более эффективным, чем лексикографический поиск в ширину.

Задачи данной работы:

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

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

Реализовать алгоритмы в виде компьютерной программы.

Провести тестовые расчеты на графах (на корректность алгоритмов и на время работы алгоритмов).

интервальный граф лексикографический компьютерный

1. Некоторые сведения из теории графов

Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6].

Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это непустое множество вершин или узлов, а E -- множество пар (в случае неориентированного графа -- неупорядоченных) вершин, называемых рёбрами.

Вершины и рёбра графа называются также элементами графа, число вершин в графе |V| -- порядком, число рёбер |E| -- размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e={u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

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

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

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

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

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

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

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

Теорема 1. Граф интервальный тогда и только тогда, когда он хордален и не содержит астероидальных троек [10].

Четыре вершины графа порождают клешню с центром в вершине , если - три попарно несмежных соседа вершины .

Теорема 2. Интервальный граф является единичным интервальным тогда и только тогда, когда он не содержит порождённых клешней [11].

Единичный интервальный граф -- граф пересечений интервалов одинаковой длины.

Пусть граф с вершинами и порядок (последовательность) вершин . Порядок называется I-порядком графа, если для всех и , выполняется для всех . Порядок называется UI-порядком графа если для всех .

Теорема 3. Граф интервальный тогда и только тогда, когда у него имеется I-порядок [12].

Теорема 4. Граф единичный интервальный тогда и только тогда, когда у него имеется UI-порядок [13].

Примеры некоторых различных типов графов:

Хордальный, не являющийся интервальным. (bdf астероидальная тройка - есть пути соединяющие каждую пару, не проходящие через закрытое множество соседей, Рис.2).

Рис.2

Интервальный, не являющийся единичным интервальным (клешня, попарно несмежные соседи - не соединяются ребрами, Рис.3).

Рис.3

Единичный интервальный (самый простой пример, Рис.4)

Рис.4

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

Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке полученной последовательности вершин на условия UI или I порядка. В зависимости от типа графа используемые алгоритмы требуют различных дополнительных условий упорядочивания вершин графа.

2.1 Алгоритм поиска в ширину (BFS)

Данный алгоритм (англ. Breadth-First Search - BFS) позволяет упорядочить вершины графа в некоторую последовательность подмножеств. Суть алгоритма поиска в ширину в том, что начиная с заданной вершины, по очереди рассматриваем ее соседей, потом рассматриваем соседей ее соседей и т.д. (Рис.5)

Рис.5 - Порядок обхода вершин графа при алгоритме BFS: e [f d] [a b c]

Начиная с заданной вершины (первое подмножество с одной вершиной - вершина e) выбираются соседи данной вершины (второе подмножество - вершины f и d), затем соседи соседей (третье подмножество - вершины a,b,c) и так далее. В итоге все вершины образуют некоторую упорядоченную последовательность подмножеств. Следует отметить, что в каждом подмножестве вершины не упорядочены.

2.2 Поиск в ширину с дополнительной сортировкой (MNS)

Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных подмножествах алгоритма BFS (Рис.6). Для этого на этапе поиска соседей для каждой найденной вершины в новом подмножестве также суммируется число рёбер из текущего подмножества вершин. Сортируя вершины подмножества по данному параметру, получаем упорядоченную последовательность вершин в подмножестве.

Рис.6 - Порядок обхода вершин графа при алгоритме MNS: e [f d] b [a c]

На Рис.6 для третьего подмножества (a b c) вершина b имеет вес 2, а вершины a и c вес 1. Следует отметить, что вершины с одинаковым весом не упорядочены (например, вершины d и f и вершины a и c на Рис.4). Алгоритм MNS используется для распознавания единичных интервальных графов.

2.3 Лексикографический поиск в ширину (LBFS)

Данный алгоритм (англ. Lexicographic Breadth-First Search - LBFS) [3] позволяет еще дополнительно упорядочить вершины в найденных подмножествах алгоритмов, описанных выше. Схема работы алгоритма приведена на Рис.7.

Рис.7 - Порядок обхода вершин графа при алгоритме LBFS: e f d b a c

Сначала каждой вершине присваивается пустая лексикографическая метка. Первой выбирается заданная вершина e. Ей присваивается порядковый номер 6 (число вершин графа) и она исключается из дальнейшего рассмотрения. Соседям f и d присваивается лексикографическая метка 6. Далее выбирается вершина с наибольшей лексикографической меткой - таких вершин две: f и d. Пусть при произвольном выборе берется вершина f (порядковый номер 5). Алгоритм повторяется: соседям выбранной вершины f добавляется лексикографическая метка 5. Вершина d, уже имеющая метку 6 получает метку 65. Далее однозначно выбирается вершина d с лексикографически наибольшей меткой. И также однозначно вершины b a c.

Алгоритм LBFS позволяет получить упорядоченную последовательность вершин в отличие от последовательностей множеств вершин предыдущих алгоритмов. Однако, на некоторых этапах выполняется произвольный выбор вершин с наибольшими лексикографическими метками, что приводит к неоднозначностям: приведенный выше пример дает последовательность e f d b a c, но если на этапе случайной выборки из вершин f и d выбрать вершину d, то получится другой результат LBFS: e d f b c a. При конструировании многомаховых алгоритмов эта особенность алгоритма LBFS учитывается и не влияет на получаемый результат. Иногда результат работы алгоритма LBFS записывается в следующем виде, учитывающем случайные выборки: e [f d] b a c или e [d f] b c a. Выражения в квадратных скобках показывают, что выбор порядка вершин случаен.

Последовательность действий алгоритма LBFS записывается следующим образом [15]:

Инициализируется последовательность множеств У, состоящая из одного множества со всеми вершинами графа.

Инициализируется выходная пустая последовательность вершин.

Пока У не пустое:

Найти и удалить вершину v из первого множества в У

Если первое множество пустое - удалить его

Добавить v в выходную последовательность

Для каждого ребра v-w, такого что w содержится в множестве S в У:

Если множество S еще не заменялось при обработке v, то создать новое пустое множество T и расположить его перед S, иначе взять множество T перед S.

Переместить w из S в T и, если S станет пустым, удалить S из У.

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

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

На Рис.8 приведен интервальный граф с 22 вершинами.

Рис.8 - Интервальный граф из работы [5].

Начиная с вершины 20 алгоритм LBFS может получить следующий порядок вершин: 20 [8 [2 4] 21] [16 [15 [9 12 ]] 13 [11 14] 17 10 18 7 19 6] 5 3 1 22. У вершины 20 имеется 4 соседа с номерами 2, 4, 8 и 21. Последовательность множеств У: (2 4 8 21)(1 3 5-7 9-19 22). Из первого множества произвольно выбирается вершина 8. Ее соседи: 2, 4, 6, 7, 9-20. Новое У: (2 4)(21)(6 7 9-19)(1 3 5 22). Произвольно выбирается вершина 2. Новое У: (4)(21)(6 7 9-19)(1 3 5)(22). Далее однозначно выбираются вершины 4, а затем 21. В итоге для данного графа необходимо сделать всего 6 произвольных выборов вершин, остальные выбираются однозначно.

Для графа на Рис.7 последовательность множеств У на каждом этапе будет следующей: (a b c d e f), (d f)(a b c), (d)(a b)(c), (b)(a)(c).

2.4 Алгоритм LBFS+

Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан на случайных выборках, что не позволяет за один раз (проход, мах) получить искомые I или UI порядок вершин. Необходимы многомаховые алгоритмы. В этом случае последующие проходы могут использовать информацию с предыдущих этапов. Алгоритм LBFS+ [2] при необходимости выбора из множества вершин использует результат сортировки предыдущего этапа, что полностью исключает элемент случайности и дает однозначный результат.

2.5 Алгоритм "трех махов" для распознавания единичных интервальных графов

Этапы алгоритма [2]:

у <LBFS

у+ <LBFS(у)

у++ <LBFS+(у+)

если у++ является UI порядком то граф единичный интервальный, иначе нет.

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

Рис.9 - Пример единичного интервального графа

Для единичного интервального графа, показанного на Рис.9 необходимы три прохода для получения UI порядка:

у = c [b d] a e

у+ = e d [b c] a

у++ = a b c d e

Если на третьем проходе использовать алгоритм LBFS, то получим: a b [c d] e. Необходим произвольный выбор из вершин c и d. Но при использовании алгоритма LBFS+ вершины c и d отсортированы на втором этапе в порядке у+. И хотя на втором этапе присутствует случайная выборка между вершинами b и c, это никак не влияет на получаемый в итоге результат: вершины b и c выбираются в нужной последовательности на третьем этапе.

В трехмаховом алгоритме возможно использование алгоритма MNS и MNS+ [7], вместо LBFS и LBFS+.

2.6 Алгоритм LBFS*

Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы дополнительные алгоритмы. Одним из таких алгоритмов является алгоритм LBFS* [6]. В нем на этапе выборки из множества вершин с наибольшими лексикографическими метками используются дополнительные параметры, сосчитанные по предыдущему этапу LBFS. Пусть граф с вершинами и порядок (последовательность) вершин . Обозначим множество (закрытое множество соседей вершины минус вершина ) и пустое множество. Обозначим число как .

Пусть множество вершин с лексикографически наибольшим номером.

Пусть и

пусть некоторая вершина такая что

Необходимая вершина выбирается следующим образом: когда иначе когда и когда

2.7 Алгоритм "четырех махов" для распознавания единичных интервальных и интервальных графов

Этапы алгоритма [6]:

д <LBFS

у <LBFS+(д)

Расчет и для всех вершин

с <LBFS*(у)

ф <LBFS+(с)

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

если ф является I порядком, то граф интервальный, иначе «граф не интервальный».

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

3. Программные модули проекта

Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное приложение, которому в виде параметров командной строки можно передать необходимые для работы данные. Общий объем всех кодов с комментариями более 2500 строк и около 100 кбайт.

3.1 Представление графа в памяти ЭВМ

Для хранения данных о вершинах и ребрах графа в памяти ЭВМ был выбран списочный подход - для каждой вершины хранится число соседей и их номера. Как показали тесты, такой подход позволяет хранить данные о графах с числом вершин и ребер сотни миллионов, и ограничен только оперативной памятью ЭВМ. Данные хранятся в одном целочисленном массиве ig.

Таблица 1 - значения элементов массива ig представляющего граф в памяти ЭВМ

ig[0]

Размерность массива минус 1

ig[1]

Начало списка соседей вершины 1 - число вершин N плюс 2

ig[2]

Начало списка соседей вершины 2

ig[N]

Начало списка соседей вершины N

ig[N+1]

Конец списка вершины N - размерность массива

ig[N+2]

Соседи вершины 1

ig[ig[2]-1]

Соседи вершины 1

ig[ig[2]]

Соседи вершины 2

ig[ig[3]-1]

Соседи вершины 2

ig[ig[3]]

Соседи вершины 3

ig[ig[N+1]-1]

Соседи вершины N

---

Элемента с номером ig[N+1] в массиве нет.

Размерность массива составляет число вершин графа плюс удвоенное число ребер плюс два.

Для поиска соседей вершины i (1 <= i <= N) используется цикл for (j=ig[i]; j<ig[i+1]; j++) и номера соседей ig[j].

Число соседей вершины i (1 <= i <= N) составляет ig[i+1]-ig[i].

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

3.2 Программа задания единичного интервального графа

Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается граф, имя файла для записи результатов (Рис.10, Рис.11). Если имя файла имеет расширение bin, то записывается двоичный файл, иначе текстовый, что удобно для визуального контроля и отладки.

Рис.10

Рис.11

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

Изменяя длину отрезка графа можно для заданного числа вершин изменять число ребер графа.

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

3.3 Программа задания интервального графа

Программа задания интервального графа была реализована по аналогии с программой задания единичного интервального графа. Изменения коснулись алгоритмов задания связей графа с помощью I-порядка. Для каждой вершины случайно задается число соседей вверх, например, для вершины j число r, 0 <= r <= N-j. Считаем, что вершина связана ребрами с вершинами j+1, j+2, ... , j+r. Для вершины возможны соседи и с меньшими номерами - соответствующие ребра задаются для вершин с меньшими номерами. Таким образом, интервальный граф задается с помощью всего одного массива целых чисел размерностью N. Сразу известно число ребер графа V - это сумма всех элементов массива. Для того, чтобы преобразовать эти данные о связности интервального графа в вид представленный в таблице 1, необходим временный массив размерностью 4*V для хранения списков ребер, так как мы не знаем заранее, сколько ребер у каждой вершины. При формировании временного массива легко выполняются проверки на связность графа - может оказаться так, что никакие из вершин с меньшими номерами не связаны ребрами с рассматриваемой вершиной (и значит со всеми остальными). Так как перебор вершин и формирование их ребер осуществляется последовательно снизу вверх, то если у рассматриваемой вершины кроме первой в списках нет ребер, то имеет место несвязность графа. Граф легко сделать связным, если соединить ребром рассматриваемую вершину с предыдущей. После этого данные из временного массива можно записать в необходимом формате таблицы 1, также как для единичного интервального графа выполнить перемешивание номеров вершин, и записать результат в текстовом или двоичном виде в выходной файл.

Входные параметры программы задания интервального графа: число вершин, параметр Лямбда (Число ребер / Число вершин), имя файла для записи результатов.

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

Пример работы программы показан на Рис.12

Рис.12

3.4 Программа задания случайных графов Эрдёша - Реньи

Программа реализует алгоритм задания случайных графов Эрдёша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер выбираются случайным образом. Используются списки ребер, как в программе задания интервальных графов. Для связности графа при необходимости добавляются дополнительные ребра. Для этого используется рекурсивный алгоритм закраски вершин графа. Как показали тестовые расчеты, такой алгоритм дает хорошие результаты для графов с большим числом вершин, но небольшим соотношением Число Ребер / Число Вершин. Если это соотношение увеличивается, то время работы программы сильно растет из-за необходимости проверок на уже наличие в графе нового случайного ребра: при этом идет перебор всех соседей одной из вершин. Для задания графов с относительно небольшим числом вершин и большим числом ребер был разработан и реализован другой алгоритм задания графов Эрдёша-Реньи. Так как число вершин невелико, то связность такого графа можно задавать с помощью матрицы связности, где для каждого возможного ребра есть отдельный элемент матрицы. Кроме того, если задаваемое число ребер превышает половину максимального числа ребер графа, то эффективнее задавать случайным образом отсутствующие ребра. Из полученной матрицы связности далее формируются списки ребер, выполняется проверка на связность и формирование нужных текстовых или двоичных файлов так же, как и в первом варианте алгоритма. Два реализованных алгоритма позволили задавать случайные графы Эрдёша-Реньи с любым числом вершин и ребер, ограниченным только оперативной памятью ЭВМ.

3.5 Программа добавления/удаления ребер графа

Входные параметры: входной файл, выходной файл, номер вершины, номер вершины.

Если задаваемые номера вершин положительные, то добавляется соответствующее ребро, иначе удаляется. На Рис.13 Рис.14 показаны оба варианта соответственно.

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

Рис.13

Рис.14

3.6 Программа распознавания единичного интервального графа

Программа реализует алгоритм трех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным или нет, а также время работы алгоритма и программы. На Рис.15 и Рис.16 показаны оба варианта.

Рис.15

Рис.16

Первоначальный вариант программы реализовывал алгоритмы MNS и MNS+ (обозначим, как MNS3). После реализации алгоритма LBFS и алгоритма четырех махов стало возможным легко и быстро реализовать алгоритм трех махов с использованием LBFS и LBFS+ (обозначим, как LBFS3). Ниже приводится сравнение быстродействия этих алгоритмов.

3.7 Программа распознавания единичного или интервального графа

Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным, интервальным или не интервальным, а также время работы алгоритма и программы. На Рис.17, Рис.18 и Рис.19 показаны все три варианта.

Рис.17

Рис.18

Рис.19

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

3.8 Подпрограмма изменения последовательности вершин графа

На этапе отладки алгоритма четырех махов возникла следующая проблема: результат расчета мог зависеть от входной последовательности вершин графа. Если изначально вершины расположены в нужном порядке, то распознавание интервального графа выполняется успешно, если вершины перемешаны, то результат был нестабилен. Перемешивание вершин случайным образом выполняется при задании графов. Для отладки кода была реализована отдельная подпрограмма, которая сохраняя структуру ребер графа, перемешивает вершины графа в памяти программы. Это позволило быстро выполнять тестирование кода на одном и том же графе, но с разной последовательностью вершин и отладить алгоритм LBFS*. Результаты, полученные с помощью данного алгоритма, приведены в разделе 4.1.

4. Результаты численных экспериментов

Численные эксперименты были проведены для следующих целей:

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

Подтверждение линейности временных затрат алгоритмов.

В расчетах были использованы три алгоритма:

Алгоритм четырех махов (обозначим, как LBFS4, раздел 2.7);

Алгоритм трех махов LBFS3 (раздел 2.5);

Алгоритм трех махов MNS3 (раздел 2.5).

Все три алгоритма распознают единичные интервальные графы,

В программах LBFS3 и MNS3 встроен алгоритм проверки на I и UI порядок (UI включает в себя проверку на I порядок), что в некоторых случаях позволило определить интервальные графы. Конечно, это получается случайно, если порядок вершин изменить, то программы LBFS3 и MNS3 выдадут: граф не является интервальным.

Все программы также определяют, является ли граф связным.

4.1 Тестирование алгоритма четырех махов

Для подтверждения работоспособности алгоритма четырех махов были проведены серии расчетов на тестовом графе с 22 вершинами (Рис.8, раздел 2.3). В расчетах случайным образом менялся порядок вершин и контролировались выходные данные. Во всех расчетах было получено, что граф является интервальным. Некоторые из возможных получаемых порядков вершин на каждом из 4 этапов приведены на Рис.20. Если расчет начинается с вершин 4, 21 или 22, то в итоговом порядке вершины расположены по возрастанию. Если расчет начинается с других вершин, то UI порядок будет обратным, отсортированным по правой границе интервалов, и не по убыванию порядковых номеров. Во всех случаях для данного графа на третьем этапе получается одинаковая последовательность вершин, хотя и не являющаяся UI порядком, что требует четвертого окончательного прохода и сортировки.

Рис. 20- Результаты работы LBFS4 на каждом этапе для 8 запусков

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

4.2 Исследования временных затрат алгоритмов

Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла: Debug и Release (без оптимизации и с оптимизацией кода); для трех типов графов: единичный интервальный, интервальный, случайный Эрдёша-Реньи. В сериях расчетов одновременно пропорционально увеличивалось число вершин и ребер графа для проверки линейности трудозатрат алгоритмов. Также были проведены две серии расчетов для графов с различным соотношением числа ребер к числу вершин: 25 и 1000. В расчетах контролировалось время выполнения алгоритма. Результаты засечек приведены в таблицах 2-5 и на рисунках 21, 22 в виде графиков.

Таблица 2 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~25.

Число вершин,

тысяч

Число ребер

LBFS 4

LBFS 3

MNS 3

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

20

500537

0.889

1.155

2.655

0.842

0.76

1.721

0.187

0.214

0.598

40

998937

1.544

2.214

5.028

1.17

1.517

3.685

0.343

0.462

1.186

60

1498010

2.449

3.464

7.959

1.779

2.269

5.331

0.499

0.674

1.934

80

1997430

4.02

4.503

10.13

2.481

3.037

7.199

0.718

0.9

2.54

100

2497160

5.07

5.687

12.88

2.948

3.748

9.049

0.889

1.104

3.301

120

2996730

5.726

6.838

15.77

3.51

4.569

11.14

1.092

1.34

3.834

140

3496650

6.349

8.071

18.31

4.664

5.352

12.91

1.577

1.54

4.506

160

3996480

8.034

9.177

20.92

5.164

6.046

14.71

1.513

1.752

5.047

180

4497290

8.096

10.39

23.6

6.115

6.854

16.66

2.184

2.007

5.916

200

4997230

10.37

11.47

26.28

7.27

7.589

18.45

2.215

2.235

6.326

220

5497100

10.93

12.62

28.96

7.753

8.332

20.38

2.106

2.447

7.41

240

5995570

11.45

13.74

31.42

7.675

9.041

22.24

2.387

2.698

8.016

260

6496380

12.68

14.9

34.45

8.143

9.798

23.95

2.527

2.904

8.62

280

6998290

13.65

16.16

37.17

9.142

10.65

25.9

2.886

3.084

9.348

300

7500650

14.29

17.31

39.73

9.843

11.39

27.69

3.042

3.312

10.05

320

8000110

16.08

18.44

42.44

10.10

12.09

29.63

3.338

3.564

10.85

340

8499520

16.38

19.49

45.06

10.62

12.85

31.44

3.407

3.789

11.42

360

8998140

17.64

20.76

47.92

11.34

13.64

33.55

3.686

4.006

12.22

380

9497400

19.78

21.93

50.44

11.94

14.51

35.47

4.056

4.247

12.93

400

9995670

20.49

23.17

52.98

13.01

15.29

37.21

4.109

4.473

13.6

420

10494700

21.09

24.27

55.77

13.36

16

38.89

4.288

4.689

14.25

440

10993800

22.62

25.37

58.33

14.73

16.72

40.8

4.504

4.891

15.1

460

11494100

23.80

26.58

61.18

15.69

17.51

42.81

4.765

5.134

15.63

480

11995100

24.20

27.71

63.75

15.91

18.36

44.58

5.023

5.341

16.4

500

12495700

24.67

28.93

66.49

16.20

19.08

46.65

5.242

5.573

17

520

12996400

26.02

30.11

69.23

16.97

19.9

48.46

5.429

5.789

17.74

540

13497300

27.19

31.24

71.83

18.00

20.57

50.22

5.567

5.995

18.56

560

13996200

28.79

32.33

74.34

19.16

21.36

51.97

5.852

6.257

19.16

580

14495400

29.45

33.57

77.5

19.99

22.09

53.87

6.052

6.468

19.72

Таблица 3 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~25.

Число

вершин, тысяч

Число ребер

LBFS 4

LBFS 3

MNS 3

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

20

500537

0.509

0.576

2.058

0.276

0.323

1.373

0.133

0.141

0.55

40

998937

0.966

1.098

3.778

0.574

0.679

2.988

0.273

0.282

1.072

60

1498010

1.526

1.728

6.171

0.839

0.988

4.292

0.417

0.444

1.775

80

1997430

1.928

2.184

7.846

1.11

1.306

5.744

0.555

0.592

2.386

100

2497160

2.403

2.735

9.758

1.385

1.642

7.12

0.702

0.747

3.068

120

2996730

2.987

3.389

12.13

1.73

2.051

9.055

0.835

0.912

3.592

140

3496650

3.5

3.962

14.22

2.004

2.37

10.44

0.981

1.042

4.153

160

3996480

4

4.534

16.33

2.293

2.73

11.94

1.133

1.19

4.739

180

4497290

4.52

5.122

18.37

2.591

3.07

13.55

1.261

1.347

5.438

200

4997230

4.976

5.687

20.35

2.861

3.432

14.85

1.4

1.497

6.102

220

5497100

5.519

6.251

22.45

3.156

3.725

16.37

1.554

1.658

6.939

240

5995570

6.061

6.862

24.47

3.44

4.053

17.74

1.693

1.802

7.5

260

6496380

6.578

7.445

26.56

3.736

4.505

19.36

1.823

1.949

8.065

280

6998290

7.126

8.068

28.81

4.026

4.796

20.99

1.972

2.102

8.755

300

7500650

7.63

8.639

30.85

4.322

5.109

22.55

2.116

2.25

9.4

320

8000110

8.132

9.2

32.91

4.597

5.436

23.86

2.263

2.41

10.08

340

8499520

8.656

9.774

34.74

4.898

5.796

25.48

2.402

2.562

10.73

360

8998140

9.142

10.36

36.97

5.182

6.177

26.98

2.545

2.716

11.4

380

9497400

9.672

10.95

39.09

5.467

6.461

28.69

2.688

2.865

12.03

400

9995670

10.19

11.52

41.09

5.762

6.817

30.23

2.826

3.015

12.62

420

10494700

10.69

12.11

43.25

6.055

7.173

31.76

2.972

3.167

13.3

440

10993800

11.21

12.7

45.36

6.354

7.514

33.31

3.116

3.321

13.99

460

11494100

11.73

13.27

47.29

6.637

7.855

34.76

3.257

3.472

14.62

480

11995100

12.23

13.84

49.42

6.926

8.189

36.35

3.398

3.632

15.26

500

12495700

12.8

14.45

51.73

7.214

8.584

38.07

3.538

3.774

15.87

520

12996400

13.28

15.03

53.74

7.512

8.931

39.44

3.679

3.925

16.54

540

13497300

13.8

15.62

55.85

7.799

9.249

40.91

3.824

4.089

17.25

560

13996200

14.26

16.14

57.64

8.102

9.639

42.53

3.966

4.23

17.83

580

14495400

14.86

16.91

60.13

8.368

9.925

43.83

4.103

4.377

18.39

Таблица 4 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Debug. Число Ребер / Число вершин ~1000.

Число

вершин, тысяч

Число ребер

LBFS 4

LBFS 3

MNS 3

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

0.5

124750

0.721

0.718

0.891

0.463

0.47

0.576

0.102

0.043

0.054

1

499500

1.313

1.299

1.606

1.008

1.014

1.26

0.198

0.084

0.105

1.5

1124300

2.163

2.153

2.674

1.478

1.429

1.785

0.333

0.139

0.172

2

1512800

2.727

2.668

3.287

1.926

1.93

2.406

0.456

0.188

0.233

2.5

2352000

3.529

3.425

4.137

2.49

2.361

3.042

0.588

0.238

0.313

3

2508400

4.253

4.205

5.271

3.059

3.081

3.827

0.699

0.280

0.407

3.5

3410000

5.004

4.961

6.052

3.521

3.515

4.376

0.845

0.330

0.445

4

3506500

5.759

5.627

7.029

4.067

4.093

5.051

0.916

0.374

0.552

4.5

4431000

6.519

6.38

7.941

4.586

4.617

5.722

1.066

0.421

0.570

5

4499600

7.147

7.044

8.771

5.094

5.003

6.279

1.146

0.472

0.663

5.5

5443200

7.868

7.797

9.708

5.597

5.55

6.944

1.316

0.530

0.679

6

5489300

8.599

8.552

10.68

6.106

6.048

7.506

1.418

0.579

0.781

6.5

6443100

9.302

9.293

11.57

6.631

6.602

8.143

1.552

0.614

0.858

7

6482800

10.1

10.06

12.49

7.147

7.193

8.865

1.692

0.680

0.862

7.5

7439000

10.8

10.77

13.37

7.659

7.707

9.566

1.775

0.749

0.952

8

7469000

11.54

11.48

14.25

8.136

8.166

10.17

1.933

0.780

0.982

8.5

8437300

12.26

12.18

15.11

8.654

8.712

10.81

2.048

0.836

1.042

9

8472800

13.03

12.92

16.02

9.118

9.21

11.47

2.153

0.879

1.107

9.5

9442700

13.71

13.66

16.94

9.642

9.723

12.14

2.276

0.934

1.169

10

9477600

14.4

14.37

17.8

10.2

10.24

12.76

2.38

0.980

1.254

10.5

10448000

15.15

15.09

18.74

10.72

10.78

13.39

2.533

1.032

1.313

11

10471000

15.87

15.83

19.61

11.27

11.29

14.1

2.664

1.024

1.368

11.5

11449000

16.61

16.56

20.53

11.75

11.81

14.69

2.778

1.107

1.407

12

11477000

17.32

17.25

21.41

12.23

12.31

15.34

2.88

1.164

1.467

12.5

12451000

18.11

18.02

22.36

12.72

12.87

16.03

2.999

1.209

1.536

13

12479000

18.79

18.74

23.37

13.23

13.41

16.68

3.117

1.26

1.612

13.5

13458000

19.54

19.48

24.19

13.81

13.93

17.28

3.255

1.291

1.631

14

13476000

20.2

20.12

24.98

14.36

14.58

17.93

3.365

1.366

1.703

14.5

14458000

21.05

20.91

26.01

14.8

14.92

18.52

3.48

1.409

1.786

Таблица 5 - Время счета задач, секунд. Нетбук с процессором Интел Атом 1.6GHz. Режим Release. Число Ребер / Число вершин ~1000.

Число

вершин, тысяч

Число ребер

LBFS 4

LBFS 3

MNS 3

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

ед.инт.

инт.

случ.

0.5

124750

0.201

0.238

0.312

0.126

0.151

0.198

0.053

0.024

0.030

1

499500

0.362

0.421

0.551

0.277

0.334

0.439

0.105

0.050

0.061

1.5

1124300

0.605

0.713

0.935

0.389

0.466

0.607

0.176

0.084

0.101

2

1512800

0.739

0.854

1.164

0.510

0.608

0.793

0.24

0.114

0.135

2.5

2352000

0.943

1.074

1.478

0.649

0.743

1.033

0.310

0.145

0.188

3

2508400

1.177

1.375

1.854

0.842

1.016

1.338

0.358

0.165

0.222

3.5

3410000

1.379

1.597

2.139

0.960

1.142

1.532

0.423

0.196

0.258

4

3506500

1.566

1.826

2.438

1.096

1.316

1.742

0.476

0.221

0.295

4.5

4431000

1.786

2.079

2.76

1.258

1.514

1.994

0.549

0.257

0.339

5

4499600

1.934

2.261

3.061

1.356

1.634

2.149

0.601

0.288

0.381

5.5

5443200

2.18

2.537

3.387

1.518

1.823

2.385

0.698

0.326

0.401

6

5489300

2.402

2.801

3.711

1.633

1.974

2.61

0.746

0.353

0.446

6.5

6443100

2.606

3.051

4.019

1.804

2.162

2.831

0.804

0.382

0.473

7

6482800

2.825

3.33

4.37

1.946

2.348

3.073

0.880

0.409

0.507

7.5

7439000

3.026

3.563

4.673

2.103

2.53

3.328

0.942

0.442

0.542

8

7469000

3.216

3.794

4.965

2.218

2.687

3.515

1.01

0.474

0.590

8.5

8437300

3.424

4.003

5.215

2.383

2.868

3.762

1.081

0.506

0.618

9

8472800

3.617

4.256

5.551

2.527

3.046

3.978

1.148

0.536

0.662

9.5

9442700

3.837

4.52

5.927

2.678

3.209

4.225

1.213

0.566

0.691

10

9477600

4.059

4.776

6.228

2.801

3.382

4.449

1.271

0.595

0.720

10.5

10448000

4.245

5.003

6.551

2.956

3.559

4.686

1.348

0.625

0.759

11

10471000

4.439

5.249

6.867

3.084

3.728

4.907

1.418

0.658

0.827

11.5

11449000

4.668

5.506

7.185

3.24

3.896

5.152

1.486

0.687

0.845

12

11477000

4.85

5.719

7.498

3.376

4.067

5.4

1.544

0.716

0.867

12.5

12451000

5.089

5.991

7.853

3.54

4.288

5.633

1.602

0.745

0.917

13

12479000

5.265

6.246

8.211

3.664

4.429

5.826

1.666

0.776

0.944

13.5

13458000

5.479

6.489

8.554

3.82

4.61

6.064

1.751

0.810

1.005

14

13476000

5.655

6.666

8.746

3.974

4.836

6.34

1.801

0.838

1.012

14.5

14458000

5.919

7.002

9.229

4.084

4.93

6.485

1.856

0.864

1.058

Рис.21

Рис.22

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

По результатам таблиц 2-5 и графиков (Рис.21, Рис.22) видна линейная зависимость времени счета от суммы количеств вершин и ребер графа, и можно сделать следующие выводы:

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

Наиболее быстрым является алгоритм MNS3, затем LBFS3 и LBFS4. Алгоритм LBFS3 быстрее LBFS4 примерно на треть, хотя в названии фигурируют 3 и 4 прохода, реально выполняются 4 и 6 переборов всех вершин и соседей - это и дает выигрыш в скорости примерно на треть. Алгоритм MNS3 быстрее LBFS3 на разных графах от 2 до 10 раз, хотя эти программы дают полностью одинаковый результат. Это проявляется преимущество алгоритма быстрой сортировки по сравнению с упорядочиванием через множества алгоритма LBFS. Таким образом, развитие алгоритма распознавания единичных интервальных графов (MNS3) до уровня распознавания интервальных и единичных интервальных графов (LBFS4) требует увеличения трудозатрат примерно на порядок (от 3 до 15 раз на разных графах).

Режим без оптимизации Debug примерно в 2 раза медленнее, чем с оптимизацией Release. Однако на случайных графах с небольшим числом ребер (отношение числа ребер к числу вершин 25) скорость счета двух режимов различается на <20%. Видимо, перебор запутанной сложной структуры случайного графа является тяжелым для современных процессоров.

Графы с отношением числа ребер к числу вершин 25 считаются в примерно два раза дольше, чем с отношением числа ребер к числу вершин 1000. Таким образом, число вершин оказывает условно большее влияние на скорость счета, чем число ребер графа.

Замер скорости счета на современном процессоре Intel i5-2400 3.1GHz показал, что задача со случайным графом с числом вершин 580 тысяч и числом ребер 14.5 миллиона сосчиталась за 12.8, 9.6, 1.2 секунд для LBFS4, LBFS3, MNS3 в режиме Release. То же в режиме Debug 15.4, 11.3, 1.7 секунд. Это показывает высокую скорость счета реализованных алгоритмов: обработка графов с числом вершин и ребер десятки миллионов не превышает десятков секунд.

Временные засечки времени работы алгоритмов распознавания (таблицы 2-5) показали хорошую масштабируемость реализованных программ: при увеличении числа вершин и ребер время счета увеличивается практически линейно. Таким образом практически показано, что временные затраты алгоритмов составляют O(|V|+|E|) (время счета прямо пропорционально числу вершин и ребер).

Заключение

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

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

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

1. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

2. Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138, 371-379 (2004)

3. D.J. Rose, R.E. Tarjan, G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing, 5 (1976), pp. 266-283.

4. F. S. Roberts. On the compatibility between a graph and a simple order. Journal of Combinatorial Theory, Series B, 11(1):28-38, 1971.

5. D.G. Corneil, S. Olariu, L. Stewart, The LBFS structure and recognition of interval graphs, SIAM Journal on Discrete Mathematics, 23 (2009), pp. 1905-1953.

6. Peng Li, Yaokun Wu. A Four-Sweep LBFS Recognition Algorithm for Interval Graphs. Discrete Mathematics & Theoretical Computer Science, Vol 16, No 3 (2014).

7. D. G. Corneil and R. Krueger. A unified view of graph searching. SIAM Journal on Discrete Mathematics, 22(4):1259-1276, 2008.

8. Татт У. Теория графов. -- М.: Мир, 1988. -- 424 с.

9. Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/ wiki/ Interval_graph

10. C.G. Lekkerkerker, J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962), pp. 45-64.

11. F.S. Roberts, Indifference graphs, F. Harary (Ed.), Proof Techniques in Graph Theory, Academic Press, New York, (1969), pp. 139-146.

12. G. Ramalingam, C.P. Rangan, A uniform approach to domination problems on interval graphs, Information Processing Letters, 27 (1988), pp. 271-274.

13. P.J. Looges, S. Olariu, Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, 25 (1993), pp. 15-25.

14. Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/wiki/Breadth-first_search

15. Wikipedia - The Free Encyclopedia [Электронный ресурс] -- Режим доступа : https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search

16. Erdos P., Renyi A. On random graphs I // Publ. Math. Debrecen. -- 1959. -- V. 6. -- P. 290-297.

Размещено на Allbest.ru


Подобные документы

  • Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.

    курсовая работа [525,6 K], добавлен 14.07.2012

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

    курсовая работа [2,1 M], добавлен 20.09.2014

  • Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.

    презентация [22,8 K], добавлен 16.09.2013

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

    курсовая работа [1,0 M], добавлен 05.01.2013

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

    курсовая работа [1,1 M], добавлен 11.01.2015

  • Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.

    курсовая работа [653,5 K], добавлен 18.02.2013

  • Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры. Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа. Проверка работоспособности программы на тестовых примерах.

    реферат [929,8 K], добавлен 23.09.2013

  • Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.

    реферат [39,6 K], добавлен 06.03.2010

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

    курсовая работа [684,8 K], добавлен 05.04.2015

  • Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.

    лабораторная работа [20,2 K], добавлен 03.12.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.