ПРИКАСПИЙСКИЙ ЖУРНАЛ

УПРАВЛЕНИЕ И ВЫСОКИЕ ТЕХНОЛОГИИ

СРАВНЕНИЕ АЛГОРИТМОВ ГРАССБЕРГЕРА И АХУНЖАНОВА ДЛЯ НАХОЖДЕНИЯ ОСТОВА ПЕРКОЛЯЦИОННОГО КЛАСТЕРА В ЗАДАЧАХ ПЕРКОЛЯЦИИ УЗЛОВ НА КВАДРАТНОЙ РЕШЕТКЕ

Читать

Гордеев Иван Иванович, Саенко Наталья Сергеевна СРАВНЕНИЕ АЛГОРИТМОВ ГРАССБЕРГЕРА И АХУНЖАНОВА ДЛЯ НАХОЖДЕНИЯ ОСТОВА ПЕРКОЛЯЦИОННОГО КЛАСТЕРА В ЗАДАЧАХ ПЕРКОЛЯЦИИ УЗЛОВ НА КВАДРАТНОЙ РЕШЕТКЕ // Прикаспийский журнал:  управление и высокие технологии. — 2022. — №3. — Стр. 44-60.

Гордеев Иван Иванович - Астраханский государственный университет им. В. Н. Татищева

Саенко Наталья Сергеевна - Астраханский государственный университет им. В. Н. Татищева

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

Ключевые слова: идентификация остова, перколяция узлов, двумерная решетка, открытые граничные условия, алгоритмы на графах, алгоритм Грассбергера, алгоритм Ахунжанова