Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
По результатам расчетов в на моей машине и в проекте в OEIS в настоящее время добавлены 4 ряда, связанные со спектрами числовых характеристик ДЛК. Описание рядов было дополнено графическими изображениями спектров и подтверждающими списками (последние на данный момент выложены для размерностей, для которых их формирование завершено).
* https://oeis.org/A344105 — число трансверсалей в ДЛК;
* https://oeis.org/A345370 — число диагональных трансверсалей в ДЛК;
* https://oeis.org/A345760 — число интеркалятов в ДЛК;
* https://oeis.org/A345761 — число ОДЛК для ДЛК.
В ходе расширения спектров числовых характеристик ДЛК порядка 11 найден квадрат
1 2 3 0 5 7 10 8 9 4 6
10 8 9 4 6 2 7 0 5 1 3
7 0 5 10 3 8 4 6 1 2 9
8 5 1 6 7 9 0 10 2 3 4
6 7 8 9 10 1 3 4 0 5 2
9 10 6 7 8 4 5 2 3 0 1
4 6 0 2 9 10 1 3 7 8 5
5 3 7 8 1 6 2 9 4 10 0
2 9 4 5 0 3 8 1 10 6 7
3 4 10 1 2 0 9 5 6 7 8
Не так давно нами был обсчитан интересный ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 9 8 11 5 10 0 6 7
5 8 10 6 11 4 1 3 9 7 0 2
11 7 5 8 10 2 9 1 3 6 4 0
7 5 8 10 6 3 0 2 4 11 9 1
9 0 1 2 3 7 10 11 5 4 8 6
6 11 7 5 8 1 4 0 2 10 3 9
10 6 11 7 5 0 3 9 1 8 2 4
3 4 9 0 1 6 5 10 11 2 7 8
2 3 4 9 0 10 7 8 6 1 11 5
4 9 0 1 2 11 8 6 7 3 5 10
8 10 6 11 7 9 2 4 0 5 1 3
(впервые найден 18.08.2021 на моей машине в ходе диагонализации предыдущего рекордмена по числу диагональных трансверсалей) на предмет числа ОДЛК у него, в результате чего была получена цифра в 3855938736 ОДЛК (24.10.2021). Цифра вызвала сомнение, т.к. во время расчета были многочисленные аппаратные сбои на сервере. Конкретно, во время расчета WU'шек, соответствующих 1421 трансверсали, было видно, что некоторые результаты битые (ошибка типа SEU), трансверсаль была запущена на перерасчет, в ходе которого было выяснено что старое значение (1802828 ОДЛК) и новое значение (1847414 ОДЛК) для нее не совпадают, т.е. часть сбойных результатов все-таки имела место быть (27.10.2021). Новое значение получилось больше старого на 1847414-1802828=44586 ОДЛК, запомним этот факт... С учетом того, что битые результаты были обнаружены при обработке 1421 трансверсали, никто не гарантировал, что их не могло появиться в составе других трансверсалей, поэтому квадрат в настоящее время отправлен на обработку повторно. Какая из цифр (3855938736 ОДЛК или 3855938736+44586=3855983322 ОДЛК) является верной мы бы не узнали до окончания повторной обработки, если бы не доброволец с ником Mynx (спасибо ему!), который взял найденный нами квадрат и повторил процесс в одиночку с использованием программ поиска ОДЛК на базе кода, выложенного в свободный доступ довольно давно whitefox'ом. И получил Mynx значение 3855983322 ОДЛК (11.11.2021), что в точности совпадает с нашим после корректировки и пересчета части WU'шек битой трансверсали! Соответственно на данный момент времени можно сделать вывод о том, что с большой долей вероятности значение 3855983322 ОДЛК для рекордного на данный момент ДЛК порядка 12 является верным. Окончательную точку в этом вопросе должен поставить текущий расчет, выполняемый в подпроекте GT CL проекта в настоящее время.
На моей машине завершено расширение спектра трансверсалей для ДЛК порядка 11 с использованием хождения по окрестностям путем поворота 1 интеркалята. На это потребовалось 158 часов расчетов в 1 поток на Core i7 4770 (знал бы, что будет так долго, запустил бы в проекте, код для этого уже готов и был апробирован ранее для выполнения аналогичной задачи для порядка 12). В итоге получилось вот что:
Параметры спектра трансверсалей до: Min value = 2477, max value = 37851, width = 35375, cardinality = 3261
Параметры спектра трансверсалей после: Min value = 2091 (!!!), max value = 37851, width = 35761 (!!!), cardinality = 3561 (!!!)
Знаками "!!!" отмечены изменившиеся значения. Таким образом, верхнее ограничение на нижнюю границу числа трансверсалей усилено с a(11)<=2477 до a(11)<=2091 (ряд A287645), соответствующий квадрат ниже:
0 1 7 3 6 5 9 8 2 4 10
10 2 9 0 1 8 4 6 7 3 5
3 6 4 8 7 1 10 2 9 5 0
6 9 3 7 8 2 0 4 5 10 1
4 3 2 6 5 0 8 1 10 9 7
5 8 10 4 2 6 7 9 1 0 3
9 10 6 5 0 4 1 3 8 7 2
8 7 5 2 4 9 3 10 0 1 6
2 4 1 9 10 7 5 0 3 6 8
1 5 0 10 9 3 2 7 6 8 4
7 0 8 1 3 10 6 5 4 2 9
Также изменились ширина и мощность спектра числа трансверсалей в ДЛК, которая теперь составляет 3561 элемент, что позволяет усилить еще одно ограничение в ряду https://oeis.org/A344105: с a(11)>=1158 до a(11)>=3561.
Как нижняя граница, так и мощность спектра в перспективе теоретически допускают усиление, чем будем заниматься в предстоящих экспериментах.
А так есть ли полная гарантия, что в других подпроектах нет битых результатов (когда месяц назад были сбои на сервере)?
Гвоздева С.Н., Ватутин Э.И. Оценка вероятности досрочного прерывания процесса умножения бинарных матриц от их размера и плотности // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание — 2021). Курск, 2021. С. 87–90. http://evatutin.narod.ru/evatutin_matmul_bin_prob.pdf
Пшеничных А.О., Ватутин Э.И. О влиянии стохастического начального заполнения матрицы феромона на качество оценки хроматического числа графа для метода муравьиной колонии // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание — 2021). Курск, 2021. С. 206–208. http://evatutin.narod.ru/evatutin_cl_ac_start_tau.pdf
Цитата: Yura12 от 12.11.2021, 22:06А так есть ли полная гарантия, что в других подпроектах нет битых результатов (когда месяц назад были сбои на сервере)?
Полных гарантий никто не даст, но анализ результатов, который я провожу практически каждый день, ничего криминального не выявил. Получаемые квадраты и спектры проходят проверку корректности при постобработке, ошибок в их составе нет и никогда не было замечено до этого. Скажу больше, у меня есть сильное подозрение, что и среди ОДЛК для тяжелого квадрата ошибок тоже не будет за пределами полученной битой 1421-й трансверсали. Однако точно в этом мы убедимся, когда досчитаем текущую партию WU'шек подпроекта GT CL. Ошибки битой памяти на удивление легли очень компактно в небольшую партию заданий, которой видимо "повезло" обрабатываться как раз в этот момент. Я очень боялся за то, что подобные ошибки теоретически могли вообще нарушить целостность связей в БД, т.к. они то могут проявиться в любой таблице БД, не только в результатах, но видимо нам повезло и этого не произошло. Либо помог откат на backup, если таковые ошибки и появились. Т.е. ситуация с ошибками больше не повторяется, и последствия от той серии сбоев сильно меньше, чем могли бы быть.
Завтра, а точнее уже сегодня, на базе Тульского государственного университета стартует конференция Интеллектуальные и информационные системы (Интеллект 2021), на которой запланирован пленарный доклад
Ватутин Э.И., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. О построении спектров быстровычислимых числовых характеристик диагональных латинских квадратов малого порядка
представлять который буду я. В докладе будет приведено краткое обобщение того, что было сделано за последние несколько месяцев в плане построения спектров числа трансверсалей, диагональных трансверсалей, интеркалятов и ОДЛК для ДЛК порядков 1—8 и аналогичных спектров для ОДЛК порядков 1—9 (все значения точные, получены полным перебором). Кроме того, планируется коротко обозначить перспективы аппроксимации аналогичных спектров для ДЛК бОльших порядков (соответствующие вычислительные эксперименты частично выполнены, частично выполняются в настоящий момент и частично еще будут выполняться в проектах Gerasim@Home и RakeSearch). Здесь пространство перебора уже слишком велико для исчерпывающего поиска, что однако открывает границы для использования эвристических методов с учетом специфики текущей квадратной задачи 
и знаний, полученных ранее при апробации аналогичных эвристик в задачах поиска кратчайших путей и квазиоптимальных раскрасок в графах (мы когда-то давно выполняли соответствующие эксперименты в проекте Gerasim@home). С презентацией доклада можно ознакомиться тут:
http://evatutin.narod.ru/evatutin_spectra_t_dt_i_o_small_orders.pdf
Если кто-то очень захочет послушать, в личку за ссылкой на подключение.
В проекте завершен эксперимент по расширению спектра трансверсалей в ДЛК порядка 12 путем анализа окрестностей, получаемых вращением 1 интеркалята от уже известных элементов спектра. В результате получен спектр из 22407 значений, который данным преобразованием уже не расширяется, однако скорее всего может быть слегка расширен другими преобразованиями в перспективе. На данный момент это позволяет заключить, что в ряду https://oeis.org/A344105 a(12) >= 22407 (до этого наиболее сильным было нижнее ограничение a(12) >= 22398, в настоящее время присутствующее в описании ряда в OEIS).
Результаты поиска КФ ОДЛК порядка 10 в проекте Gerasim@Home за месяц.
За месяц найдено 107 336 КФ ОДЛК порядка 10 (большую часть времени поиск был приостановлен для того, чтобы быстрее были посчитаны результаты для других экспериментов). Среди наиболее интересных находок:
ONCE (A):1 - 139848, where:
1 CFs - 33160
2 CFs - 106688
LINE3 (B):1 - 99351, where:
2 CFs - 18735
3 CFs - 80616 (+400)
LINE3 (B):2 - 59043, 2:1, where:
2 CFs - 18735
3 CFs - 40308 (+200)
LINE4 (C):1 - 172, where:
2 CFs - 4
4 CFs - 168
LINE4 (C):2 - 172, where:
2 CFs - 4
4 CFs - 168
LINE5 (D):1 - 17, where:
3 CFs - 17
LINE5 (D):2 - 34, where:
3 CFs - 34
LOOP4 (E):2 - 2280, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 676
1TO3 (F):1 - 453, where:
4 CFs - 453
1TO3 (F):3 - 151, where:
4 CFs - 151
1TO4 (G):1 - 1362, where:
3 CFs - 882
5 CFs - 480
1TO4 (G):4 - 561, where:
3 CFs - 441
5 CFs - 120
1TO5 (k):1 - 10, where:
6 CFs - 10
1TO5 (k):5 - 2, where:
6 CFs - 2
1TO6 (H):1 - 42, where:
4 CFs - 24
7 CFs - 18
1TO6 (H):6 - 11, where:
4 CFs - 8
7 CFs - 3
1TO7 (h):1 - 7, where:
8 CFs - 7
1TO7 (h):7 - 1, where:
8 CFs - 1
1TO8 (I):1 - 48, where:
5 CFs - 32
9 CFs - 16
1TO8 (I):8 - 10, where:
5 CFs - 8
9 CFs - 2
RHOMBUS3 (J):2 - 9, where:
5 CFs - 9
RHOMBUS3 (J):3 - 6, where:
5 CFs - 6
RHOMBUS4 (K):2 - 73, where:
3 CFs - 2
4 CFs - 23
5 CFs - 32
6 CFs - 16
RHOMBUS4 (K):4 - 34, where:
3 CFs - 1
4 CFs - 17
5 CFs - 8
6 CFs - 8
FISH (N):1 - 7, where:
4 CFs - 1
6 CFs - 6
FISH (N):2 - 11, where:
4 CFs - 2
6 CFs - 9
FISH (N):4 - 4, where:
4 CFs - 1
6 CFs - 3
TREE1 (V):1 - 2, where:
4 CFs - 2
TREE1 (V):2 - 1, where:
4 CFs - 1
TREE1 (V):3 - 1, where:
4 CFs - 1
CROSS (X):1 - 16, where:
6 CFs - 16
CROSS (X):2 - 4, where:
6 CFs - 4
CROSS (X):4 - 4, where:
6 CFs - 4
DAEDALUS10 (i):1 - 6, where:
12 CFs - 6
DAEDALUS10 (i):2 - 4, where:
12 CFs - 4
DAEDALUS10 (i):4 - 1, where:
12 CFs - 1
DAEDALUS10 (i):10 - 1, where:
12 CFs - 1
FLYER (j):1 - 2, where:
8 CFs - 2
FLYER (j):2 - 3, where:
8 CFs - 3
FLYER (j):4 - 3, where:
8 CFs - 3
VENUS (l):1 - 1, where:
5 CFs - 1
VENUS (l):2 - 3, where:
5 CFs - 3
VENUS (l):4 - 1, where:
5 CFs - 1
DAEDALUS8 (m):1 - 2, where:
6 CFs - 2
DAEDALUS8 (m):2 - 2, where:
6 CFs - 2
DAEDALUS8 (m):4 - 1, where:
6 CFs - 1
DAEDALUS8 (m):8 - 1, where:
6 CFs - 1
RHOMBUS5 (n):2 - 4, where:
5 CFs - 4
RHOMBUS5 (n):5 - 1, where:
5 CFs - 1
1TO10 (o):1 - 5, where:
6 CFs - 5
1TO10 (o):10 - 1, where:
6 CFs - 1
ROBOT (p):1 - 4, where:
5 CFs - 4
ROBOT (p):2 - 4, where:
5 CFs - 4
ROBOT (p):4 - 2, where:
5 CFs - 2
STINGRAY (q):1 - 1, where:
5 CFs - 1
STINGRAY (q):2 - 3, where:
5 CFs - 3
STINGRAY (q):3 - 1, where:
5 CFs - 1
Эксперимент по исследованию свойств окрестностей обобщенных симметрий:
* парастрофический срез 1 [Px Py Pv]: обработка завершена;
* парастрофический срез 3 [Py Px Pv]: пройдено 1170 (+48) окрестностей из 1764 (66,3%, +2,7%).
Спектры числовых характеристик ДЛК порядка 9:
* трансверсали: ширина спектра — 2241-68+1 = 2174, мощность спектра — 359, спектр близок к максимальному;
* диагональные трансверсали: ширина спектра — 333-0+1=334, мощность спектра — 176, запланирован эксперимент по расширению данного спектра;
* интеркаляты: ширина спектра — 72-0+1 = 73, мощность спектра — 62, спектр близок к максимальному;
* ОДЛК: ширина спектра — 614-0+1 = 615, мощность спектра — 99.
Спектры числовых характеристик ДЛК порядка 10:
* трансверсали: ширина спектра — 5504-144+1 = 5361, мощность спектра — 442, спектр близок к максимальному;
* диагональные трансверсали: ширина спектра — 890-3+1=888, мощность спектра — 736, спектр близок к максимальному;
* интеркаляты: ширина спектра — 93-0+1 = 94, мощность спектра — 88, спектр близок к максимальному;
* ОДЛК: ширина спектра — 10-0+1 = 11, мощность спектра — 10, спектр близок к максимальному.
Спектры числовых характеристик ДЛК порядка 11:
* трансверсали: ширина спектра — 37851-2091 = 35761, мощность спектра — 1158, запланирован эксперимент по расширению данного спектра;
* диагональные трансверсали: ширина спектра — 4828-199+1=4630, мощность спектра — 353, запланирован эксперимент по расширению данного спектра;
* интеркаляты: ширина спектра — 94-0+1 = 95, мощность спектра — 100, спектр близок к максимальному;
* ОДЛК: ширина спектра — 32462-0+1 = 32463, мощность спектра — 36.
Спектры числовых характеристик ДЛК порядка 12:
* трансверсали: ширина спектра — 198144-1312+1 = 196833, мощность спектра — 22401 -> 22407 (+6) значений, запланирован эксперимент по расширению данного спектра;
* диагональные трансверсали: ширина спектра — 30192-50+1 = 30143, мощность спектра — 17620 -> 17641 значений, спектр близок к максимальному;
* интеркаляты: ширина спектра — 252-0+1 = 253, мощность спектра — 210, спектр не изменился за месяц и близок к максимальному;
* ОДЛК: ширина спектра — 3855983322-0+1 = 3855983323, мощность спектра — 2501 -> 2782 (+288) значений, расширение спектра в настоящее время выполняется на моей машине в несколько потоков.
Откорректирован рекорд (3855938736 -> 3855983322) на максимальное число ОДЛК для ДЛК порядка 12. Во время соответствующего вычислительного эксперимента на сервере проекта был ряд сбоев, полученное предыдущее значение не вызывало большого доверия, в ходе пересчета ОДЛК для 1421-й трансверсали число ОДЛК было откорректировано следующим образом: 3855938736-1802828+1847414=3855983322. Новое значение подтверждено группой добровольцев (CoolAtchOk, Mynx, etc.) и скорее всего является верным, точку в этом вопросе должен поставить текущий расчет, выполняемый в проекте.