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