Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
А исходный код счётных приложений в открытом доступе? Может тогда к Даниэлю, программисту из Польши обратиться, он ведь RakeSearch и Acoustics компилировал под разные операционные системы.
О расширении спектра числа диагональных трансверсалей ДЛК порядка 10
Возьмем известный и близкий к своему максимальному составу благодаря выполненным ранее многочисленным вычислительным экспериментам спектр числа трансверсалей в ОДЛК порядка 10 со следующими параметрами:
минимальное значение = 60,
максимальное значение = 866,
ширина = 807,
мощность = 389.
Выполним над ним следующие преобразования.
1. Применим к нему процедуру замыкания с использованием хождения по окрестностям путем вращения 1 интеркалята. На выполнение замыкания уходит несколько секунд вычислительного времени, в результате получается спектр числа диагональных трансверсалей ДЛК порядка 10 со следующими параметрами:
минимальное значение = 60,
максимальное значение = 866,
ширина = 807,
мощность = 502 (!!!).
Видно, что данная процедура увеличила мощность спектра с 389 до 502 элементов.
2. К полученному спектру применим процедуру замыкания с использованием хождения по окрестностям путем вращения 1 цикла. На выполнение замыкания уходит аналогично несколько секунд вычислительного времени, в результате получается спектр числа диагональных трансверсалей ДЛК порядка 10 со следующими параметрами:
минимальное значение = 60,
максимальное значение = 866,
ширина = 807,
мощность = 555 (!!!).
Видно, что данная процедура еще дополнительно увеличила мощность спектра с 502 до 555 элементов.
3. Применим к полученному спектру процедуру поквадратного расширения путем вращения 1 интеркалята и построения соответствующих частичных спектров. На ее выполнение ушло 26 минут работы Core i7 4770 в 1 поток, в результате получен спектр со следующими параметрами:
минимальное значение = 38 (!!!),
максимальное значение = 890 (!!!),
ширина = 853 (!!!),
мощность = 660 (!!!).
Видно, что данная процедура позволила сдвинуть как верхнюю, так и нижнюю границы. Новая верхняя граница на минимальное число диагональных трансверсалей в ДЛК порядка 10:
a(10) <= 38 в ряду https://oeis.org/A287647
0 1 2 3 4 7 6 5 8 9
1 2 3 6 0 8 9 4 7 5
4 7 1 2 3 0 5 8 9 6
5 9 8 7 6 1 4 3 2 0
9 8 7 4 5 2 0 6 3 1
2 5 6 9 1 3 7 0 4 8
7 4 9 5 2 6 8 1 0 3
3 6 0 1 8 4 2 9 5 7
8 3 4 0 9 5 1 7 6 2
6 0 5 8 7 9 3 2 1 4
Новая нижняя граница на максимальное число диагональных трансверсалей в ДЛК порядка 10:
a(10) >= 890 в ряду https://oeis.org/A287648
0 8 2 3 5 4 6 7 1 9
1 2 3 4 9 0 5 6 7 8
2 6 4 9 1 8 0 5 3 7
6 4 0 1 2 7 8 9 5 3
3 5 9 8 7 2 1 0 4 6
8 7 6 5 0 9 4 3 2 1
9 1 7 6 4 5 3 2 8 0
5 9 1 2 6 3 7 8 0 4
7 3 5 0 8 1 9 4 6 2
4 0 8 7 3 6 2 1 9 5
Также увеличены ширина (807 -> 853) и мощность (555 -> 660) спектра. Приведенный выше ДЛК с рекордным числом д-трансверсалей ОДЛК не имеет и является квадратом Брауна с классической блочной структурой из 25 не пересекающихся интеркалятов.
4. Применим к полученному спектру процедуру поквадратного расширения путем вращения 1 цикла и построения соответствующих частичных спектров. В результате за 2,5 часа работы Core i7 4770 в 1 поток получен спектр со следующими параметрами:
минимальное значение = 6 (!!!),
максимальное значение = (890),
ширина = 885 (!!!),
мощность = 719 (!!!).
Верхняя граница на минимальное число диагональных трансверсалей в ДЛК порядка 10 усилена с 38 до 6:
a(10) <= 6 в ряду https://oeis.org/A287647
6 1 5 3 4 2 7 0 8 9
1 2 8 4 0 3 5 9 7 6
0 9 7 2 3 1 6 8 5 4
7 5 3 0 9 8 2 6 4 1
8 7 9 1 5 0 4 2 6 3
2 3 0 6 1 4 8 7 9 5
4 0 1 5 8 6 9 3 2 7
5 8 4 9 6 7 3 1 0 2
9 6 2 8 7 5 1 4 3 0
3 4 6 7 2 9 0 5 1 8
Ширина спектра увеличена с 853 до 885, мощность — с 660 до 719. Полученный в результате экспериментов спектр числа диагональных трансверсалей в ДЛК порядка 10 не является непрерывным (ширина (885) > мощности (719)), как и все остальные аналогичные спектры мощностью более 1.
PS. Напомню, что эксперименты, аналогичные 3 и 4, для размерности N=12 выполнялись несколько недель в проекте. Для данной размерности N=10 хватает вычислительных возможностей одного ядра CPU.
PPS. Над полученным спектром в перспективе можно поколдовать с использованием ряда других преобразований, но большого его расширения не ожидается...
Диагонализируя квадраты спектра числа диагональных трансверсалей в ДЛК порядка 10, удалось найти ДЛК
0 1 2 3 4 5 6 7 8 9
1 2 0 4 8 9 7 5 3 6
8 3 5 7 9 0 2 4 6 1
2 5 1 9 3 6 0 8 4 7
3 4 8 0 6 1 5 9 7 2
5 9 3 8 2 7 1 6 0 4
6 7 9 5 1 8 4 0 2 3
4 0 6 1 7 2 8 3 9 5
9 8 7 6 5 4 3 2 1 0
7 6 4 2 0 3 9 1 5 8
у которого 5 диагональных трансверсалей, что позволяет усилить верхнее ограничение: a(10)<=6 -> a(10)<=5 в ряду https://oeis.org/A287647. Кроме того, в спектр добавлено еще 2 значения.
В ходе эксперимента с поквадратным расширением спектра числа трансверсалей в ДЛК порядка 12 был найден квадрат
0 1 8 4 7 5 6 2 3 9 10 11
1 2 4 8 3 11 0 6 10 5 7 9
3 7 5 11 10 9 2 1 8 6 4 0
10 8 9 6 4 0 3 7 5 2 11 1
7 10 11 9 8 6 1 3 4 0 5 2
2 3 10 5 1 4 9 0 7 11 8 6
4 11 6 1 5 2 7 8 9 3 0 10
9 6 3 7 0 10 5 11 2 8 1 4
6 0 7 10 2 8 11 9 1 4 3 5
11 9 1 3 6 7 4 5 0 10 2 8
5 4 2 0 11 3 8 10 6 1 9 7
8 5 0 2 9 1 10 4 11 7 6 3
с 1312 трансверсалями, что позволяет усилить верхнее ограничение с a(12)<=1672 до a(12)<=1312 в ряду https://oeis.org/A287645. Параметры спектра числа трансверсалей в ДЛК порядка 12 на данный момент:
Min = 1312, max = 198144, ширина = 196833, мощность = 22406
Диагонализируя квадраты спектра числа трансверсалей в ДЛК порядка 10, удалось найти ДЛК
0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 7 9 8 6 3
7 6 4 2 0 9 5 1 3 8
5 9 1 7 8 6 3 2 0 4
9 8 6 1 3 4 2 5 7 0
3 4 9 5 7 8 0 6 2 1
4 7 3 8 6 2 1 0 9 5
8 3 5 6 2 0 4 9 1 7
6 0 8 9 1 3 7 4 5 2
2 5 7 0 9 1 8 3 4 6
у которого 3 диагональных трансверсали, что позволяет усилить верхнее ограничение с a(10)<=5 до a(10)<=3 в ряду https://oeis.org/A287647.
В ходе диагонализации новых ДЛК в составе спектра числа трансверсалей в ДЛК порядка 12 найден квадрат
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 9 7 8 11 10 3 6 5
10 6 8 11 5 0 4 1 9 7 3 2
4 8 11 5 1 6 7 9 3 2 0 10
6 9 3 10 7 4 1 2 11 8 5 0
8 10 7 9 11 3 0 5 4 6 2 1
5 7 10 0 6 1 9 8 2 11 4 3
11 0 1 7 10 2 3 4 6 5 8 9
2 5 6 8 3 11 10 0 1 4 9 7
7 11 5 6 8 9 2 3 0 10 1 4
3 4 9 2 0 10 5 6 7 1 11 8
9 3 4 1 2 8 11 10 5 0 7 6
у которого 50 диагональных трансверсалей, что позволяет усилить текущее ограничение с a(12)<=66 до a(12)<=50 в ряду https://oeis.org/A287647.
О расширении спектров числа трансверсалей и диагональных трансверсалей в ДЛК порядка 10
1. Возьмем имеющийся в распоряжении спектр числа диагональных трансверсалей в ДЛК порядка 10, для квадратов, входящих в его состав, построим спектр числа трансверсалей и объединим его с имеющимся спектром трансверсалей, в результате чего получится спектр со следующими параметрами:
Min value = 192, max value = 5504, width = 5313, cardinality = 275.
В его составе присутствует квадрат
6 1 5 3 4 2 7 0 8 9
1 2 8 4 0 3 5 9 7 6
0 9 7 2 3 1 6 8 5 4
7 5 3 0 9 8 2 6 4 1
8 7 9 1 5 0 4 2 6 3
5 3 0 6 1 4 8 7 9 2
4 0 1 5 8 6 9 3 2 7
2 8 4 9 6 7 3 1 0 5
9 6 2 8 7 5 1 4 3 0
3 4 6 7 2 9 0 5 1 8
с 192 трансверсалями, что позволяет усилить ограничение на их минимальное количество: было a(10)<=408, стало a(10)<=192.
2. Выполним замыкание полученного спектра путем вращения 1 интеркалята, на что требуется 20 с вычислительного времени. В результате получается спектр трансверсалей со следующими параметрами:
Min value = 192, max value = 5504, width = 5313, cardinality = 397 (!!!).
Мощность спектра увеличилась с 275 до 397, остальные параметры не изменились.
3. Выполним замыкание спектра путем вращения 1 цикла, на что требуется 55 с вычислительного времени. В результате получается спектр трансверсалей со следующими параметрами:
Min value = 192, max value = 5504, width = 5313, cardinality = 402 (!!!).
Мощность спектра увеличилась с 397 до 402, остальные параметры не изменились.
4. Выполним поквадратное расширения спектра путем вращения 1 интеркалята, на что потребовалось 52 минуты работы одного ядра Core i7 4770. В результате получается спектр трансверсалей со следующими параметрами:
Min value = 184 (!!!), max value = 5504, width = 5321 (!!!), cardinality = 434 (!!!)
Кроме увеличения мощности спектра с 402 до 434 элементов также изменилась нижняя граница (а значит и ширина), новое верхнее ограничение усилено с a(10)<=192 до a(10)<=184, соответствующий квадрат ниже:
0 1 7 3 4 5 6 2 8 9
1 2 0 4 8 9 7 5 3 6
8 3 5 7 9 0 2 4 6 1
2 5 1 9 3 6 0 8 4 7
3 4 8 0 6 1 5 9 7 2
5 0 3 8 2 7 1 6 9 4
6 7 9 5 1 8 4 0 2 3
4 9 6 1 7 2 8 3 0 5
9 8 2 6 5 4 3 7 1 0
7 6 4 2 0 3 9 1 5 8
5. Выполним поквадратное расширения спектра путем вращения 1 цикла, на что потребовалось 5 часов работы одного ядра Core i7 4770. В результате получается спектр трансверсалей со следующими параметрами:
Min value = 144 (!!!), max value = 5504, width = 5361 (!!!), cardinality = 442 (!!!)
Мощность полученного спектра увеличена с 434 до 442 элементов, нижняя граница усилена с a(10)<=184 до a(10)<=144, соответствующий квадрат ниже:
0 8 9 6 5 2 4 7 3 1
4 2 6 3 9 0 5 1 7 8
2 6 5 0 4 8 9 3 1 7
9 4 7 1 3 5 6 2 8 0
6 5 1 8 7 9 3 0 2 4
7 1 3 9 8 4 0 5 6 2
1 3 0 4 2 7 8 9 5 6
8 7 2 5 0 3 1 6 4 9
3 0 8 7 6 1 2 4 9 5
5 9 4 2 1 6 7 8 0 3
6. Ну и в заключение эксперимента выполним диагонализацию всех квадратов в спектре трансверсалей, на что потребовалось 2,5 ч работы Core i7 4770 в 1 поток. В результате получен спектр числа диагональных трансверсалей, объединяя который с имеющимся спектром получен результирующий спектр со следующими параметрами:
Min value = 3 (!!!), max value = 890, width = 888 (!!!), cardinality = 736 (!!!)
Изменились нижняя граница, ширина и мощность. Полученные спектры числа трансверсалей и диагональных трансверсалей близки к идеалу: если их и можно расширить, то не особо сильно. В спектре трансверсалей, как и ранее, все значения кратны 4.
Проделаем аналогичные рассмотренным ранее преобразования над спектром числа интеркалятов в ДЛК порядка 10. Из них к расширению спектра приводит только преобразование поквадратного расширения путем вращения 1 цикла, в результате которого получается спектр со следующими параметрами:
S = {0..83, 85, 87, 89, 93}
Min value = 0, max value = 93, width = 94, cardinality = 88
Таким образом, мощность спектра увеличена с 73 до 88.
Проделав преобразования расширения спектров числовых характеристик ДЛК порядка 9 аналогично рассмотренным ранее для порядка 10, был получен ряд расширений спектров (см. рис.). В ходе выполнения преобразований оказалось, что диагонализация (как и канонизация) не работают для нечетных порядков. Точнее, они скорее всего применимы, но алгоритм надо менять, о чем надо будет подумать в перспективе...