ИССЛЕДОВАНИЕ АЛГОРИТМА ДАББАГЯНА-ВУ ДЛЯ ПОСТРОЕНИЯ НЕЦИКЛИЧЕСКИХ ПАНДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ
Ключевые слова:
Пандиагональные латинские квадраты, нециклические латинские квадраты, циклический сдвиг, построение, алгоритм, математическая модель, вычислительная сложностьАннотация
Рассматривается математическая модель и базирующийся на ней алгоритм Даббагяна-Ву,
предназначенный для построения нециклических пандиагональных латинских квадратов. Показано,
что из-за высокой вычислительной сложности и факта существования других разновидностей
пандиагональных квадратов, применение классических алгоритмов, таких как полный перебор и
циклических сдвигов, недостаточно для построения полного перечня пандиагональных латинских
квадратов. Этим подтверждается цель работы – исследование и экспериментальная апробация
математических моделей и алгоритмов, предназначенных для задачи построения за приемлемое
время. Здесь производится исследование алгоритма, представленного Даббагяном В. и Ву. Т, ко-
торый предназначен для построения пандиагональных латинских квадратов простых порядков p,
определяемых выражением p=6n+1. Можно сказать, что он является модификацией алгоритма
циклического построения. То есть, позволяет получить из исходного циклического квадрата пан-
диагональный нециклический. Преобразование выполняется путем циклических сдвигов в опреде-
ленных ячейках в каждой строке исходного квадрата. Была разработана программная реализация
алгоритма Даббагяна-Ву. Результат экспериментов подтвердил корректность предложенной
Даббагяном В. и Ву. Т. методики построения. Таким образом, для порядка 13 удалось найти 72
уникальных квадрата. К тому же, проведена попытка построения для порядка, не являющегося
нечетным простым числом, например 25. В данном случае удалось получить 4 корректных пан-
диагональных латинских квадрата. Путем дополнительных преобразований полученных наборов
увеличить количество квадратов, так, для порядка 13 коллекция расширена до 1570, а для 25 – до
210. Исследование позволило углубленно ознакомиться с алгоритмом Даббагяна-Ву и сделать вы-
вод о его особенностях – к достоинствам относится его относительно низкая вычислительная
сложность, а к недостаткам – полноценная корректность построений только для нечетных про-
стых порядков. Полученные наборы квадратов в дальнейшем будут задействованы для получения
их числовых характеристик при помощи распределенных вычислений.
