Форум

Уважаемые посетители. В связи с массовой регистрацией на форуме спамовых и рекламных аккаунтов нам пришлось установить некоторые защитные программные блоки. Если при регистрации на Ваш почтовый адрес не придет письмо с паролем для активации учетнойзаписи, прошу написать на адрес tpp12@rambler.ru или boinc.ru@yandex.ru. Я активирую учетку в ручную и вышлю Вам времнный пароль.
Вы должны войти, чтобы создавать сообщения и темы.

Проект Gerasim@Home

Опубликована статья

Ватутин Э.И., Белышев А.Д., Заикин О.С., Никитина Н.Н., Манзюк М.О. Исследование свойств обобщенных симметрий в диагональных латинских квадратах с использованием добровольных распределенных вычислений // Высокопроизводительные вычислительные системы и технологии. 2019. Т. 3, № 2. С. 39–51. http://evatutin.narod.ru/evatutin_dls_gen_symms.pdf

В ней приведено обобщенное математическое описание симметрий в диагональных латинских квадратах, задаваемых формулами (до этого, напомню, были построены описания для плоскостной (вертикальной/горизонтальной) и центральной симметрий, далее они были математически обобщены). Для одной плоскости было найдено 5 формул, описывающих симметрию в виде функции Ax+By+C, что дает 5^2=25 обобщенных симметрий ввиду того, что квадрат — двумерная структура, элементы которой адресуются двумя координатами X и Y. Из теоретически существующих 25 симметрий на практике ОДЛК соответствуют 8 различным (не включая тривиальную), соответствующие симметрии были исследованы в проекте Gerasim@Home (эксперименты exp46, exp54, exp58-60). Соответствующие им и их окрестностям ОДЛК порождают множество интересных комбинаторных структур из ДЛК на множестве бинарного отношения ОДЛК, описанных ранее. К сожалению, в их составе не присутствует тройки ВОДЛК порядка 10, а соответствующие псевдотройки не позволяют улучшить известную рекордную характеристику ортогональности 274/300.
В настоящее время в проекте обсчитывается обобщение обобщенных (!!! 🙂 ) симметрий и их окрестностей, в котором соответствия задаются не формулами, а перестановками с фиксированным составом мультимножеств длин циклов (43 перестановки в одной плоскости и 903 их комбинации в двух).

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

Оценим теоретически максимальное число диагональных трансверсалей A, которые могут быть в латинском квадрате порядка N. Для этого построим N! перестановок P порядка N (чтобы получить из них трансверсаль, полагаем x=i, y=P[i]) и выберем из них те, которые являются диагональными трансверсалями. Получится следующий числовой ряд (1 <= N <= 12): 1, 0, 0, 8, 20, 96, 656, 5568, 48912, 494080, 5383552, 65097600. Оказывается, данный числовой ряд уже представлен в OEIS под номером A007016 — число перестановок длины N с одной фиксированной и одной отраженной точкой! Число трансверсалей в ЛК/ДЛК не может быть больше данного теоретического максимума. ДЛК — это N непересекающихся трансверсалей. Из указанного теоретически максимального числа трансверсалей можно сложить не более чем C^{N}_{A} = A! / (N! * (A-N)!) ДЛК (C — число сочетаний из A по N, известная формула). Используя это соотношение, можно получить верхнюю оценку числа ДЛК порядка N: 1, 0, 0, 7, 15504, 927048304, 1.00e16, 2.28e25, 4.41e36, 2.39e50 (N=10), 2.76e66, 1,21e85. Данная оценка является завышенной (и сильно завышенной) ввиду того, что некоторые трансверсали могут пересекаться и образовать из них ДЛК нельзя.

Array

Опубликована статья

Kochemazov S., Zaikin O., Vatutin E., Belyshev A. Enumerating Diagonal Latin Squares of Order Up to 9 // Journal of Integer Sequences. Vol. 23. Iss. 1. 2020. Article 20.1.2. https://cs.uwaterloo.ca/journals/JIS/VOL23/Zaikin/zaikin3.pdf

У нее сложная судьба: она побывала в трех журналах и была опубликована в последнем. В ней подробно рассмотрено устройство генераторов ДЛК на базе вложенных циклов, дающих рекордный темп генерации ДЛК ~6,6 млн. ДЛК/с. Напомню, что с использованием этих генераторов в рамках нашего коллектива было определено число ДЛК порядка 1 <= N <= 9.

Array

Результаты поиска КФ ОДЛК в проекте Gerasim@Home за месяц:

ONCE (A):1
1 CFs - 32020 (+3)

LINE3 (B):1 - 57231, where:
2 CFs - 18735
3 CFs - 38496 (+2760)

LINE3 (B):2 - 37983, 44:1, where:
2 CFs - 18735
3 CFs - 19248 (+1380)

LINE4 (C):1 - 95, where:
2 CFs - 3
4 CFs - 92 (+2)

LINE4 (C):2 - 95, where:
2 CFs - 3
4 CFs - 92 (+2)

LINE5 (D):1 - 17, where:
3 CFs - 17

LINE5 (D):2 - 34, where:
3 CFs - 34

LOOP4 (E):2 - 2240, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 636

1TO3 (F):1 - 330, where:
4 CFs - 330 (+3)

1TO3 (F):3 - 110, where:
4 CFs - 110 (+1)

1TO4 (G):1 - 1274, where:
3 CFs - 882
5 CFs - 392 (+4)

1TO4 (G):4 - 539, where:
3 CFs - 441
5 CFs - 98 (+1)

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

Окрестности обобщенных симметрий: пройдено 328 (+42) из 903 (36,3%, +4,6%). В месячный отчет добавлен новый рисунок, который показывает, в окрестностях каких симметрий попадаются интересные комбинаторные структуры (L4 — line-4, S — SODLS, 3 — 1:3, C4 — loop-4, 4 — 1:4, huge — большое количество разных структур).

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array

С утверждением о верхней оценке числа диагональных трансверсалей согласились в OEIS: https://oeis.org/A007016. Еще 2 последовательности висят на подтверждении правок...

Array

Утверждение: для всех 312 CMS-схем каждая диагональная трансверсаль квадрата A отображается в диагональную трансверсаль квадрата B (квадраты A и B образуют ортогональную ESODLS пару). Проверено полным перебором для N=10, всех 312 CMS-схем и всех 494080 возможных диагональных трансверсалей.

Для "странных" CMS-схем, не входящих в число схем, получаемых комбинацией M-преобразований, и вытащенных из одного из интересных и редких 1-КФных циклов-4 данное свойство нарушается. С данными схемами видимо придется разбираться отдельно...

Array

Подтверждены еще две правки последовательностей в OEIS, связанные с верхней оценкой числа диагональных трансверсалей в латинских квадратах:

https://oeis.org/A287647
https://oeis.org/A287648

Array

Продолжим изучение свойств трансверсалей после их отображения в ортогональный соквадрат с использованием ESODLS CMS схем. Недавно (см. https://vk.com/wall162891802_1034) было показано, что для 312 возможных ESODLS схем, получаемых комбинацией эквивалентных M-преобразований, трансверсали образуют только циклы длины 1 и 2. Другими словами, трансверсаль T1 в квадрате A отображается в трансверсаль T2 в квадрате B после применения преобразования согласно выбранной схеме, и наоборот, T2 в B отображается в T1 в A обратно, т.е. образуется цикл длины 2 (T1->T2->T1). Если T1 в A отображается в T1 в B, цикл имеет длину 1 (T1->T1). Циклы длины 1 интересны тем, что образующая данный цикл трансверсаль T1 является общей для пары квадратов A и B. Это важно потому, что если у ортогональной пары квадратов (A,B) имеется M<N общих непересекающихся трансверсалей, по ним тривиально выстраивается M*N ячеек квадрата C, что дает ХО не ниже чем 100 + M*N + M*N (первая трансверсаль в квадрате C заполняется значениями 0, вторая — 1, третья — 2 и т.д.). Если имеется N общих непересекающихся трансверсалей, автоматически получается третий квадрат C, ортогональный как квадрату A, так и B, т.е. искомая тройка ВОДЛК (а может быть, если повезет, и клика большего порядка в составе соответствующей комбинаторной структуры). Поэтому построение пар ОДЛК с общими трансверсалями является интересным (среди известных нам пар ОДЛК рекорд по числу общих трансверсалей принадлежит паре, образующей классическую SODLS через преобразование транспонирования).

А что, если попробовать сложить ДЛК из трансверсалей, образующих циклы длины 1? Это мы уже умеем делать через решение задачи о точном покрытии (exact cover) по известному множеству трансверсалей через DLX с той лишь разницей, что при построении ОДЛК берется известное множество трансверсалей для уже известного квадрата, а в данном случае сам квадрат нам неизвестен и нужно сперва его сложить, а потом уже проверять на наличие ОДЛК. Трансверсалей, образующих циклы длины 1, не так уж и много (не более нескольких тысяч), соответственно задача о точном покрытии решается не сильно дольше, чем при поиске ОДЛК. Сказано, сделано!
Для размерностей 1 <= N <= 8 все КФ ОДЛК и соответствующие им комбинаторные структуры нам известны. Таким образом находится множество интересных, но уже известных, структур.

Для интересующей нас размерности N=10, к сожалению, ОДЛК из подобных трансверсалей не складываются вообще :(.

А вот для размерности N=9 многие ДЛК входят в состав интересных и редких комбинаторных структур, большинство из которых было найдено в проекте RakeSearch, осуществлявшем поиск ESOLS и соответствующих им структур отталкиваясь от ограниченного множества эквивалентных преобразований на базе перестановки строк (еще часть — в ходе анализа центральной симметрии). Интересно то, что при подобном поиске в дополнение к 197 известным было найдено еще 9 новых структур:

* 7N7M7C
* 8N12M8C
* 8N13M8C
* 8N14M8C
* 24N128M15C
* 24N32M2C
* 36N96M14C
* 68N144M34C
* 96N800M64C

Клик мощности более 2 в их составе нет... Это позволяет сделать вывод о том, что скорее всего из таких трансверсалей с длиной цикла 1 клику с ESODLS сложить нельзя, для этого нужно использовать еще и трансверсали с длиной цикла 2. Искали одно (клики), нашлось другое (новые структуры), все как обычно в науке 🙂

Array

В журнале Проблемы информационных технологий, издаваемом под эгидой Национальной академии наук Азербайджана, опубликованы лучшие статьи, представленные на прошедшей на базе нашей кафедры конференции Распознавание (https://swsu.ru/structura/up/fivt/kvt/recogn19.php). В сборнике есть статья

Vatutin E., Panishchev V., Gvozdeva S., Titov V. Comparison of Decisions Quality of Heuristic Methods Based on Modifying Operations in the Graph Shortest Path Problem // Problems of Information Technology. No. 1. 2020. pp. 3–15. DOI: 10.25045/jpit.v11.i1.01. https://jpit.az/uploads/article/az/2020_1/COMPARISON_OF_DECISIONS_QUALITY_OF_HEURISTIC_METHODS_BASED_ON_MODIFYING_OPERATIONS_IN_THE_GRAPH_SHORTEST_PATH_PROBLEM.pdf

В ней представлены результаты сравнения качества решений группы эвристических методов на базе модификации уже имеющихся решений с использованием модифицирующих операций, специфичных для решаемой задачи (метод случайных блужданий (RW), метод имитации отжига (SA), генетический алгоритм (GA), метод пчелиной колонии (BC) и три модификации метода роя частиц (PSO)), в задаче поиска кратчайшего пути в графе (SSP). Вычислительные эксперименты были выполнены в проекте добровольных распределенных вычислений Gerasim@Home (http://gerasim.boinc.ru) на платформе BOINC. Данная статья дополняет опубликованные ранее статьи

* http://ceur-ws.org/Vol-1973/paper09.pdf
* https://www.degruyter.com/view/j/eng.2017.7.issue-1/eng-2017-0041/eng-2017-0041.xml?format=INT

в которых приведено описание аналогичных результатов, но для других групп методов. Впереди необходимо исследование как новых методов и их комбинаций, повышающих скорость сходимости, так и новых задач. Одна из них (раскраска графов) недавно была обсчитана в проекте для группы методов и будет считаться еще.

Array

Из любой пары ОДЛК (не важно, ESODLS или нет) можно извлечь схему CMS, что уже было отмечено ранее. Для любой пары ОДЛК данная схема будет иметь следующую структуру циклов из ячеек квадрата: N циклов длины 1 (элементы, соответствующие парам значений (0,0), (1,1), ..., (N-1,N-1)) и N*(N-1)/2 циклов длины 2 (все возможные пары значений (c,d), c<>d), или, короче — {1:N, 2:N*(N-1)/2} (для случая размерности N=10 — {1:10, 2:45}).

Ранее (см. https://vk.com/wall162891802_903) в результате применения M-преобразований из 15360 схем (для размерности N=10) были отобраны 312 со структурой циклов {1:10, 2:45}, они были названы корректными, с их участием в настоящее время в проекте Gerasim@Home (http://gerasim.boinc.ru) успешно выполняются эксперименты exp405 ... exp408: на данный момент соответственно найдено 4/6, 4/11, 2/10 и 2/8 КФ ESODLS (здесь запись x/y обозначает, что было найдено y КФ ESODLS, из них новыми оказались x), все однушки. Остальные 15360-312=15048 схем были записаны в некорректные, а, как оказалось, зря...

Нам известен 1-КФный цикл-4

0 1 2 3 4 5 6 7 8 9
1 2 0 6 7 9 8 3 4 5
3 6 7 9 8 4 2 5 1 0
4 0 8 5 2 3 7 1 9 6
5 9 4 8 3 6 0 2 7 1
7 8 6 4 0 1 3 9 5 2
6 4 5 2 1 7 9 0 3 8
9 5 1 7 6 0 4 8 2 3
2 3 9 0 5 8 1 4 6 7
8 7 3 1 9 2 5 6 0 4

в составе которого есть 4 образующие его ESODLS-пары ОДЛК. Как уже было отмечено ранее, ни одна из 312 корректных (а правильнее говорить по новому — канонических, и обозначать как cCMS) схем ему не соответствует. Это, в свою очередь, говорит о том, что существует какая-то другая комбинация M-преобразований, переводящая один из квадратов пары ESODLS ОДЛК в другой. В ходе проверки оказалось, что если не отбрасывать схемы со структурой циклов, отличной от {1:10, 2:45}, ранее считавшиеся некорректными, то есть схемы, переводящие квадраты цикла-4 один в другой. Эти схемы имеют номера 3407 и 4951 (см. рис.) и структуру циклов {4:25}. Квадраты в составе цикла могут быть получены друг из друга так (по кругу A->B->D->C->A, с точностью до нормализации):

B := ESODLS_CMS_4951(A)
D := ESODLS_CMS_4951(B)
C := ESODLS_CMS_4951(D)
A := ESODLS_CMS_4951(C)

или так (по сути, наоборот, в другую сторону по циклу A->C->D->B->A):

C := ESODLS_CMS_3407(A)
D := ESODLS_CMS_3407(C)
B := ESODLS_CMS_3407(D)
A := ESODLS_CMS_3407(B)

Я думаю, невооруженным глазом заметно, что движение по квадратам в составе структуры типа цикл-4 имеет период, равный 4, что по странному стечению обстоятельств совпадает с длиной циклов для соответствующих ESODLS CMS №№ 3407 и 4951 (случайности, как известно, не случайны :).

PS. Ну и маленькая, но интересная особенность: квадраты A и D отличаются друг от друга поворотом двух циклов из элементов 3 и 6 (длины 6 и 6), а квадраты B и C — поворотом одного цикла из элементов 5 и 8 длины 8.

PPS. Для другого известного 1-КФного цикла-4

0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 9 8 3 7 6
2 0 3 6 7 8 9 4 1 5
5 4 7 8 3 6 1 2 9 0
8 7 5 1 9 3 0 6 4 2
9 6 1 5 2 7 4 0 3 8
3 8 6 0 1 4 5 9 2 7
4 9 8 7 6 0 2 1 5 3
7 5 4 9 0 2 3 8 6 1
6 3 9 2 8 1 7 5 0 4

аналогичные ESODLS CMS схемы имеют номера 47 и 15031.

Загруженные файлы:
  • Вам нужно войти, чтобы просматривать прикрепленные файлы..
Array