Форум

Поздравляю всех форумчан с Новым Годом! Это год 15-ти летия нашего ресурса, который несмотря на многие сложности проолжает существовать и работать. Желаю всем здоровья, удачи, благополучия и успешного участия в любимых проектах.
Вы должны войти, чтобы создавать сообщения и темы.

Проект 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