Результаты численных экспериментов, Тестирование алгоритма четырех махов - Алгоритмы нескольких махов

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

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

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

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

Алгоритм четырех махов (обозначим, как 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 порядком, что требует четвертого окончательного прохода и сортировки.

результаты работы lbfs4 на каждом этапе для 8 запусков

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

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

Похожие статьи




Результаты численных экспериментов, Тестирование алгоритма четырех махов - Алгоритмы нескольких махов

Предыдущая | Следующая