Один метод построения циклов в графе

Аннотация

Задачи нахождения циклов в графе – неотъемлемая составная часть геоинформационных, логистических, и навигационных информационных систем.  Задачи нахождения гамильтоновых и эйлеровых циклов, задача коммивояжера настолько важны в современных информационных системах, обеспечивающих решение задач в различных предметных областях от традиционных транспортных до научных проблем в химии и биологии, что этому посвящено большое число публикаций. Современная особенность задач нахождения циклов в графе заключается в необходимости обработки больших и сверхбольших данных (Big Data). Методы, которые дают точное решение, сводятся к алгоритмам с экспоненциальной вычислительной сложностью. Для уменьшения сложности предлагаются эвристические методы, например, генетические алгоритмы. Предложен многомерно-матричный подход к обработке больших графов, ориентированный на построение всех возможных циклов независимо от способа вычисления их свойств (например, стоимости, гамильтоновости и прочих). Этот подход обеспечивает эффективное распараллеливание алгоритмов построения всех циклов и использование технологии in database для построения всех циклов, что возможно в силу изоморфизма алгебры многомерных матриц и реляционной алгебры для рассматриваемого класса задач.

Сведения об авторах

Evgeny Petrovich Yemelchenkov, Смоленский государственный университет

заведующий кафедрой информатики, физико-математический факультет, кандидат физико-математических наук, доцент

Victor Iosifovich Munerman, Смоленский государственный университет

доцент кафедры информатики, физико-математический факультет, кандидат технических наук, доцент

Daniel Victorovich Munerman, Смоленский государственный университет

лаборант-стажер кафедры информатики, физико-математический факультет

Tatyana Arkadyevna Samoylova, Смоленский государственный университет

доцент кафедры информатики, физико-математический факультет, кандидат технических наук, доцент

Опубликована
2021-12-20
Как цитировать
YEMELCHENKOV, Evgeny Petrovich et al. Один метод построения циклов в графе. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 17, n. 4, dec. 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/773>. Дата доступа: 25 jan. 2022
Раздел
Параллельное и распределенное программирование, грид-технологии