Инкрементальный алгоритм синтеза минимального графа смежности
Ключевые слова:
граф смежности, вероятностные графические модели, инкрементальный алгоритм, статистическая оценка сложности, структурное обучение, машинное обучениеАннотация
В статье предложен инкрементальный алгоритм, ускоряющий синтез минимального графа смежности по исходному минимальному графу смежности и новой вершине с заданной допустимой нагрузкой; доказана корректность работы такого алгоритма. Выполнен сравнительный анализ статистических оценок сложности реализаций предложенного алгоритма и двух известных алгоритмов синтеза минимального графа смежности: жадного и прямого; результаты вычислительных экспериментов представлены в виде графиков, снабжены комментариями и выводом. В целом, на наборах со средним и большим числом вершин инкрементальный алгоритм в 3-6 раз оказался быстрее, чем прямой, и в 10-50 раз быстрее, чем жадный. На наборах с небольшим числом вершин скорость алгоритмов отличается не сильно. Отмечено, что, чем больше в наборе вершин с нагрузкой 5-9 символов, тем более велик разброс отношения скоростей сравниваемых алгоритмов. В статье также достигнуты дидактические цели: в контексте синтеза минимальных графов смежности продемонстрировано обоснованное применение методов инкрементализации алгоритмов, статистического анализа скорости работы реализаций алгоритмов, визуализации данных, полученных в результате проведения вычислительных экспериментов.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2015 Даниил Григорьевич Левенец, Михаил Анатольевич Зотов, Александр Львович Тулупьев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
