Результаты численных экспериментов, Тестирование алгоритма четырех махов - Алгоритмы нескольких махов
Численные эксперименты были проведены для следующих целей:
Подтверждение корректности алгоритмов.
Подтверждение линейности временных затрат алгоритмов.
В расчетах были использованы три алгоритма:
Алгоритм четырех махов (обозначим, как LBFS4, раздел 2.7);
Алгоритм трех махов LBFS3 (раздел 2.5);
Алгоритм трех махов MNS3 (раздел 2.5).
Все три алгоритма распознают единичные интервальные графы,
В программах LBFS3 и MNS3 встроен алгоритм проверки на I и UI порядок (UI включает в себя проверку на I порядок), что в некоторых случаях позволило определить интервальные графы. Конечно, это получается случайно, если порядок вершин изменить, то программы LBFS3 и MNS3 выдадут: граф не является интервальным.
Все программы также определяют, является ли граф связным.
Тестирование алгоритма четырех махов
Для подтверждения работоспособности алгоритма четырех махов были проведены серии расчетов на тестовом графе с 22 вершинами (Рис.8, раздел 2.3). В расчетах случайным образом менялся порядок вершин и контролировались выходные данные. Во всех расчетах было получено, что граф является интервальным. Некоторые из возможных получаемых порядков вершин на каждом из 4 этапов приведены на Рис.20. Если расчет начинается с вершин 4, 21 или 22, то в итоговом порядке вершины расположены по возрастанию. Если расчет начинается с других вершин, то UI порядок будет обратным, отсортированным по правой границе интервалов, и не по убыванию порядковых номеров. Во всех случаях для данного графа на третьем этапе получается одинаковая последовательность вершин, хотя и не являющаяся UI порядком, что требует четвертого окончательного прохода и сортировки.
Рис. 20- Результаты работы LBFS4 на каждом этапе для 8 запусков
Результаты приведенных расчетов показывают работоспособность алгоритма 4 махов для распознавания интервальных графов. Во всех случаях, при различной начальной перенумерации вершин тестового графа, был получен верный результат.
Похожие статьи
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Исследования временных затрат алгоритмов - Алгоритмы нескольких махов
Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла:...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Входные параметры: входной файл, выходной файл, номер вершины, номер вершины. Если задаваемые номера вершин положительные, то добавляется соответствующее...
-
Свойства алгоритмов - Алгоритм
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое "точное предписание" или "последовательность действий,...
-
Для администратора проекта ИИС "MD_SLAGMELT" разработано средство логирования. После завершения выполнения программы, в случае возникновения...
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Для тестирования процесса расчета оценок будет специально создан учебный курс с двумя модулями, один из которых будет включать экзамен, а другой - нет. В...
-
Вычислительные эксперименты для оценки эффективности параллельного варианта метода Гаусса для решения систем линейных уравнений проводились при следующих...
-
Выводы по результатам тестирования - Исследование алгоритмов
По полученным в ходе анализа данным сделать вывод о качестве обученных каскадных классификаторов и о причинах таких результатов, а также выяснить, какие...
-
Заключение, Список литературы - Алгоритмы нескольких махов
В ходе выполненной работы были изучены алгоритм распознавания единичного интервального графа с помощью трех проходов алгоритма лексикографического...
-
Работа программы представлена на рисунке 2.3 Рис. 2.3 Кодирование и тестирование программы Программа кодировалась на языке Си++, используя библотеку Qt5x...
-
Постановка задачи, Описание программы, Алгоритм работы - Алгоритм кодировки RSA
Реализовать клиент серверное приложение для пересылки закодированной информации. В качестве алгоритма реализовать алгоритм RSA. Описание программы...
-
При разработке данной программы были допущены следующие синтаксические ошибки: - неправильное использование операторов присваивания; - неверное...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги
В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути. Алгоритм Дейкстры Находит кратчайший путь от одной из вершин графа...
-
Базовый алгоритм - Моделирование эффектов
В качестве базового был разработан следующий алгоритм. Исходные данные: - фотография сцены с объектом (одна) - фотография сцены без объекта (одна) -...
-
Тестирование и отладка программы - Разработка электронного учебного пособия "VBA. Решение задач"
Процесс отладки является неотъемлемой частью создания любой программы. При программировании могут быть допущены ошибки, которые принадлежат к одному из...
-
Задание: 1. Прочитать текст "Алгоритм и его свойства", в таблице №1 "Алгоритм и его свойства" проверьте правильное заполнение таблицы. Запишите в тетрадь...
-
Тестирование, Анализ работы - Разработка программы на языке C++, реализующей игру "Морской бой"
Чтобы проверить корректность работы программы нужно провести тестирование. Бой с противником продолжается до полной победы, т. е. пока не будут...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
Для визуализации значений и представления отчетности различным лицам были созданы шаблоны отчетов в excel, содержащие все необходимые поля, описанные во...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
Тестирование эффективности многопоточной реализации исполнения локальных узлов производилось на примере расчета определенного интеграла функции. Расчет...
-
Для вычисления цвета могут быть использованы различные подходы. Вычисление цвета может проводиться одновременно с геометрической реконструкцией,...
-
Для создания трехмерной реконструкции сцены или объекта необходимо создать его трехмерную модель и вычислить цвет ее вершин. Для геометрической...
-
В данном разделе выпускной квалификационной работы описывается процесс разработки программы извлечения КП текста, а также производится оценка качества ее...
-
Описание алгоритмов Рассмотрим один из основных алгоритмов, задействованных в программе, - алгоритм передвижения мяча. Блок-схема алгоритма изображена на...
-
Программа экспериментальных исследований В предыдущей главе была описана процедура создания приложения, а также его структура и интерфейс. В данной главе...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
Результаты численных экспериментов, Тестирование алгоритма четырех махов - Алгоритмы нескольких махов