Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 25 - Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 25 - Форум

#241 · 10.04.2020, 13:03

Цитата: evatutin от 10.04.2020, 13:03
О существовании CMS для известных циклов-4

Недавно (см. https://vk.com/wall162891802_1122) была высказана гипотеза о том, что для всех циклов-4 существует такая CMS, которая переводит квадраты в их составе друг в друга. Чуть позднее (см. https://vk.com/wall162891802_1131) к гипотезе был найден контрпример. На данный момент завершена обработка всех известных нам циклов-4 (их известно 718 по результатам поиска ОДЛК в проекте Gerasim@Home), в ее результате установлено, что для 326 известных циклов-4 такую CMS подобрать не удается, а вот для остальных 392 циклов-4 такие CMS существуют, и сразу помногу. Теперь надо бы понять причину наличия таких CMS у одних циклов и ее отсутствие у других... Для цикла из ОДЛК с существующей CMS на ее поиск уходит от нескольких секунд до нескольких минут, в случае не существования CMS поиск растягивается на несколько десятков часов. В составе найденных CMS встречаются циклы следующей длины: 1, 2, 3, 4, 5, 6, 8, 10, 12, 20, 24 (это не очередной числовой ряд и в OEIS мы его добавлять не будем :). Главное в результатах этого поиска то, что от CMS со сложной структурой циклов, отличной от {1:10, 2:45}, вполне существуют решения (циклы из ОДЛК). А раз так, то по таким схемам необходимо научиться эффективно находить ОДЛК, которые должны содержать в своем составе циклы из ДЛК, что, возможно, позволит найти новые комбинаторные структуры...

О существовании CMS для известных циклов-4

Недавно (см. https://vk.com/wall162891802_1122) была высказана гипотеза о том, что для всех циклов-4 существует такая CMS, которая переводит квадраты в их составе друг в друга. Чуть позднее (см. https://vk.com/wall162891802_1131) к гипотезе был найден контрпример. На данный момент завершена обработка всех известных нам циклов-4 (их известно 718 по результатам поиска ОДЛК в проекте Gerasim@Home), в ее результате установлено, что для 326 известных циклов-4 такую CMS подобрать не удается, а вот для остальных 392 циклов-4 такие CMS существуют, и сразу помногу. Теперь надо бы понять причину наличия таких CMS у одних циклов и ее отсутствие у других... Для цикла из ОДЛК с существующей CMS на ее поиск уходит от нескольких секунд до нескольких минут, в случае не существования CMS поиск растягивается на несколько десятков часов. В составе найденных CMS встречаются циклы следующей длины: 1, 2, 3, 4, 5, 6, 8, 10, 12, 20, 24 (это не очередной числовой ряд и в OEIS мы его добавлять не будем :). Главное в результатах этого поиска то, что от CMS со сложной структурой циклов, отличной от {1:10, 2:45}, вполне существуют решения (циклы из ОДЛК). А раз так, то по таким схемам необходимо научиться эффективно находить ОДЛК, которые должны содержать в своем составе циклы из ДЛК, что, возможно, позволит найти новые комбинаторные структуры...

hoarfrost отреагировал на эту запись.

#242 · 12.04.2020, 20:10

Цитата: evatutin от 12.04.2020, 20:10
В основной подпроект проекта добавлена новая версия расчетного модуля 3.1.5. В ней существенно усовершенствован код поиска ОДЛК по заданной CMS для неканонических схем (схем со структурой циклов, отличной от {1:10, 2:45}). Заполнение ячеек ДЛК теперь производится не только для исходного квадрата A и квадрата B, в который схема отображает его ячейки, а для всех ОДЛК в составе формируемого цикла, длина которого определяется как НОК от длин циклов в составе CMS. Это позволяет эффективно варьировать порядок заполнения ячеек ДЛК, уменьшая арность узлов в составе дерева комбинаторного перебора, и использовать отсечения на меньшей глубине рекурсии. Для схем, полученных недавно от 1-КФных циклов 4, эффективность получения решений составляет 6 ОДЛК/с для заполнения ячеек подряд и 190 ОДЛК/с для вариации порядка ячеек в соответствии с принципом минимума возможностей (данный принцип уже в который раз показывает себя с лучшей стороны!). До этого на подобные заполнения в лучшем случае уходили десятки часов, в худшем решения не находились вовсе. Первая партия из 100 тыс. WU'шек эксперимента e674 уже считается, кворум — 1, дедлайн — 7 дней. Посмотрим, будут ли интересные находки...

В основной подпроект проекта добавлена новая версия расчетного модуля 3.1.5. В ней существенно усовершенствован код поиска ОДЛК по заданной CMS для неканонических схем (схем со структурой циклов, отличной от {1:10, 2:45}). Заполнение ячеек ДЛК теперь производится не только для исходного квадрата A и квадрата B, в который схема отображает его ячейки, а для всех ОДЛК в составе формируемого цикла, длина которого определяется как НОК от длин циклов в составе CMS. Это позволяет эффективно варьировать порядок заполнения ячеек ДЛК, уменьшая арность узлов в составе дерева комбинаторного перебора, и использовать отсечения на меньшей глубине рекурсии. Для схем, полученных недавно от 1-КФных циклов 4, эффективность получения решений составляет 6 ОДЛК/с для заполнения ячеек подряд и 190 ОДЛК/с для вариации порядка ячеек в соответствии с принципом минимума возможностей (данный принцип уже в который раз показывает себя с лучшей стороны!). До этого на подобные заполнения в лучшем случае уходили десятки часов, в худшем решения не находились вовсе. Первая партия из 100 тыс. WU'шек эксперимента e674 уже считается, кворум — 1, дедлайн — 7 дней. Посмотрим, будут ли интересные находки...

#243 · 13.04.2020, 11:49

Утверждение о том, что "все ESODLS порядка 10 могут быть получены путем канонизации (aka замыкание) списка SOLS порядка 10", неверно. Контрпример: 1-КФные циклы-4. Один из них приведен ниже:

DLS 1: 0123456789120679834536798425104085237196594836027178640139526452179038951760482323905814678731925604
DLS 2: 0123456789538907142615926378049674185230745021396832487690152706948153693182054780153946724867502391
DLS 3: 0123456789835907142615926378049674185230748021396532457690182706948153693182054750183946724867502391
DLS 4: 0123456789120679834563798425104085267193594863027178640139523452179068951730482626905814378731925604

Adjacency matrix:
0110
1001
1001
0110

Vertexes powers: 2, 2, 2, 2.
Degree 2 - 4 times

Vertexes: 4
Arcs: 4

КФ, образующая цикл, является ESODLS, ОДЛК для нее получаются путем применения ESODLS CMS № 3407 и 4951, о чем уже сообщалось ранее (см. https://vk.com/wall162891802_1064). Она была найдена в ходе разведки окрестностей обобщенных симметрий (см. http://evatutin.narod.ru/evatutin_ls_all_structs_rus..., стр. 11). Запущенный вчера эксперимент как раз и направлен на прямой поиск подобных комбинаторных структур (см. https://vk.com/wall162891802_1140).

hoarfrost и SerVal отреагировали на эту запись.

#244 · 14.04.2020, 19:52

Цитата: evatutin от 14.04.2020, 19:52
Берем известную линию-2, точнее, 2 ОДЛК в ее составе

0123456789120436985727869351048057192346386957142059710486327648213095453062791894157802636392804571,
0123456789965201743852783490163819524607190526837460347825914391875260748693012585671039422740691853.

Вытаскиваем из них CMS с канонической стурктурой циклов {1:10, 2:45}

77 90 69 36 86 82 33 55 66 22
44 48 19 94 58 47 43 28 27 88
72 85 34 16 32 87 13 61 49 45
99 80 73 26 20 39 63 25 21 38
57 95 91 96 76 17 64 50 24 78
70 37 92 46 56 84 18 93 74 12
60 81 30 42 68 89 54 10 59 97
41 71 15 98 65 31 14 35 29 75
11 52 62 67 23 51 53 79 83 40

А дальше делаем поиск ОДЛК по ней с использованием нового высоко оптимизированного кода (см. https://vk.com/wall162891802_1140). Находится исходный квадрат, образующий двушку, а также еще один квадрат с новой КФ:

0123456789120478935643768012955089217643251764893076981354023960574821873192056498453620176452093178,

образующий новую, не известную нам до этого двушку. Если "средняя стоимость" получения 1 новой КФ составляет 8,3 ч с использованием классического подхода на базе метода Эйлера-Паркера и его высоко эффективной реализации в виде канонизатора whitefox'а, а на 228 однушек в среднем приходится одна двушка, то "стоимость" получения двушки составляет ~1892 ч = 79 сут. В данном случае (через CMS) новая двушка была получена за 9 минут, т.е. вычислительные затраты получения КФ таким способом в ~12600 раз ниже! Так ли будет для всех КФ? Открытый вопрос...

Берем известную линию-2, точнее, 2 ОДЛК в ее составе

0123456789120436985727869351048057192346386957142059710486327648213095453062791894157802636392804571,
0123456789965201743852783490163819524607190526837460347825914391875260748693012585671039422740691853.

Вытаскиваем из них CMS с канонической стурктурой циклов {1:10, 2:45}

77 90 69 36 86 82 33 55 66 22
44 48 19 94 58 47 43 28 27 88
72 85 34 16 32 87 13 61 49 45
99 80 73 26 20 39 63 25 21 38
57 95 91 96 76 17 64 50 24 78
70 37 92 46 56 84 18 93 74 12
60 81 30 42 68 89 54 10 59 97
41 71 15 98 65 31 14 35 29 75
11 52 62 67 23 51 53 79 83 40

А дальше делаем поиск ОДЛК по ней с использованием нового высоко оптимизированного кода (см. https://vk.com/wall162891802_1140). Находится исходный квадрат, образующий двушку, а также еще один квадрат с новой КФ:

0123456789120478935643768012955089217643251764893076981354023960574821873192056498453620176452093178,

образующий новую, не известную нам до этого двушку. Если "средняя стоимость" получения 1 новой КФ составляет 8,3 ч с использованием классического подхода на базе метода Эйлера-Паркера и его высоко эффективной реализации в виде канонизатора whitefox'а, а на 228 однушек в среднем приходится одна двушка, то "стоимость" получения двушки составляет ~1892 ч = 79 сут. В данном случае (через CMS) новая двушка была получена за 9 минут, т.е. вычислительные затраты получения КФ таким способом в ~12600 раз ниже! Так ли будет для всех КФ? Открытый вопрос...

#245 · 14.04.2020, 21:23

С целью тестирования нового оптимизированного кода нахождения ОДЛК по CMS в проект добавлена новая версия расчетного модуля 3.1.7 и 10 тыс. WU'шек эксперимента e396, в рамках каждой из которых производится построение случайной CMS с канонической структурой циклов {1:10, 2:45} и нахождение соответствующих ей ОДЛК. Дедлайн — 7 дней, кворум — 1, время счета — 20 минут.

#246 · 14.04.2020, 23:56

Цитата: evatutin от 14.04.2020, 23:56
Однушку можно рассматривать как цикл из ОДЛК длины 2. А раз так, не получится ли извлечь из него CMS со структурой циклов, отличной от канонической? Оказывается, что очень даже получится! В качестве примера возьмем однушку

0123456789120436597820156348973457981620574980216369812473058376019254963072854175681904324892573016
0123456789375869241049871032561209745863941258063720943685716830271945854601739256719340287365829104

и попытаемся поискать для нее CMS. Их, как и для подробно рассмотренных ранее циклов-4, находится превеликое множество. Некоторые из них приведены ниже:

CMS 1:

0 1 6 5 4 8 7 9 2 3
59 92 19 20 80 49 37 26 84 64
55 25 75 70 65 12 68 50 91 33
36 99 45 96 85 31 83 11 29 32
61 78 53 48 27 46 73 18 23 28
82 39 88 42 81 41 67 44 51 22
95 93 40 58 63 66 10 14 13 35
54 76 69 74 21 47 43 94 72 24
52 56 34 79 30 77 87 86 71 38
17 16 62 60 89 15 57 98 97 90

Loops structure: {1:3, 2:3, 7:1, 14:6}

CMS 2:

0 1 6 5 4 8 7 9 54 88
59 92 19 20 80 49 37 31 84 39
55 25 75 70 65 12 68 48 27 33
36 99 45 96 43 26 83 11 29 32
61 78 53 50 91 46 73 18 23 28
82 64 3 42 81 41 67 44 51 22
62 93 40 58 63 66 79 14 13 35
2 76 69 74 21 47 85 94 72 24
52 56 34 10 30 16 87 86 71 38
17 77 95 60 89 15 57 98 97 90

Loops structure: {1:3, 2:3, 4:4, 5:1, 10:5, 20:1}

CMS 3:

0 1 6 5 4 8 7 85 2 96
59 92 19 20 80 49 37 78 10 64
55 25 75 70 65 12 68 50 52 62
36 99 45 3 9 31 83 11 29 32
61 26 53 15 27 46 73 18 23 28
82 21 88 42 81 41 54 44 51 22
95 93 77 58 63 66 84 14 13 35
67 76 69 74 39 47 43 94 72 24
91 56 34 79 30 40 87 86 71 38
17 16 33 60 89 48 57 98 97 90

Loops structure: {1:3, 2:3, 3:1, 6:4, 8:5, 24:1}

CMS 4 (см. рис. из ОДЛК):

0 1 6 5 4 8 7 85 67 88
59 92 19 20 80 49 37 31 10 21
55 25 75 70 65 12 68 15 27 62
36 99 45 3 43 78 83 11 29 32
61 26 53 50 52 46 73 18 23 28
82 64 96 42 81 41 54 44 51 22
33 93 77 58 63 66 79 14 13 35
2 76 69 74 39 47 9 94 72 24
91 56 34 84 30 16 87 86 71 38
17 40 95 60 89 48 57 98 97 90

Loops structure: {1:3, 2:3, 3:1, 4:10, 6:4, 12:2}

и т.д.

По каждой из приведенных выше 4 CMS разработанный недавно полнопереборный код находит 10080 ОДЛК, в составе которых 2 различных КФ, совпадающие с исходными. Вполне вероятно, что где-то подобным образом будут найдены новые КФ, не совпадающие с исходными...

Однушку можно рассматривать как цикл из ОДЛК длины 2. А раз так, не получится ли извлечь из него CMS со структурой циклов, отличной от канонической? Оказывается, что очень даже получится! В качестве примера возьмем однушку

0123456789120436597820156348973457981620574980216369812473058376019254963072854175681904324892573016
0123456789375869241049871032561209745863941258063720943685716830271945854601739256719340287365829104

и попытаемся поискать для нее CMS. Их, как и для подробно рассмотренных ранее циклов-4, находится превеликое множество. Некоторые из них приведены ниже:

CMS 1:

0 1 6 5 4 8 7 9 2 3
59 92 19 20 80 49 37 26 84 64
55 25 75 70 65 12 68 50 91 33
36 99 45 96 85 31 83 11 29 32
61 78 53 48 27 46 73 18 23 28
82 39 88 42 81 41 67 44 51 22
95 93 40 58 63 66 10 14 13 35
54 76 69 74 21 47 43 94 72 24
52 56 34 79 30 77 87 86 71 38
17 16 62 60 89 15 57 98 97 90

Loops structure: {1:3, 2:3, 7:1, 14:6}

CMS 2:

0 1 6 5 4 8 7 9 54 88
59 92 19 20 80 49 37 31 84 39
55 25 75 70 65 12 68 48 27 33
36 99 45 96 43 26 83 11 29 32
61 78 53 50 91 46 73 18 23 28
82 64 3 42 81 41 67 44 51 22
62 93 40 58 63 66 79 14 13 35
2 76 69 74 21 47 85 94 72 24
52 56 34 10 30 16 87 86 71 38
17 77 95 60 89 15 57 98 97 90

Loops structure: {1:3, 2:3, 4:4, 5:1, 10:5, 20:1}

CMS 3:

0 1 6 5 4 8 7 85 2 96
59 92 19 20 80 49 37 78 10 64
55 25 75 70 65 12 68 50 52 62
36 99 45 3 9 31 83 11 29 32
61 26 53 15 27 46 73 18 23 28
82 21 88 42 81 41 54 44 51 22
95 93 77 58 63 66 84 14 13 35
67 76 69 74 39 47 43 94 72 24
91 56 34 79 30 40 87 86 71 38
17 16 33 60 89 48 57 98 97 90

Loops structure: {1:3, 2:3, 3:1, 6:4, 8:5, 24:1}

CMS 4 (см. рис. из ОДЛК):

0 1 6 5 4 8 7 85 67 88
59 92 19 20 80 49 37 31 10 21
55 25 75 70 65 12 68 15 27 62
36 99 45 3 43 78 83 11 29 32
61 26 53 50 52 46 73 18 23 28
82 64 96 42 81 41 54 44 51 22
33 93 77 58 63 66 79 14 13 35
2 76 69 74 39 47 9 94 72 24
91 56 34 84 30 16 87 86 71 38
17 40 95 60 89 48 57 98 97 90

Loops structure: {1:3, 2:3, 3:1, 4:10, 6:4, 12:2}

и т.д.

По каждой из приведенных выше 4 CMS разработанный недавно полнопереборный код находит 10080 ОДЛК, в составе которых 2 различных КФ, совпадающие с исходными. Вполне вероятно, что где-то подобным образом будут найдены новые КФ, не совпадающие с исходными...

#247 · 15.04.2020, 21:07

А почему приложение Test separator давно (с февраля) не обновляется?

#248 · 16.04.2020, 10:10

Цитата: Yura12 от 15.04.2020, 21:07

А почему приложение Test separator давно (с февраля) не обновляется?

Потому что оно решает свою задачу (исследование окрестностей обобщенных симметрий на предмет поиска ОДЛК), данные изменения в коде его не касаются.

Yura12 отреагировал на эту запись.

#249 · 16.04.2020, 14:58

И можно ещё один вопрос. А проекту Gerasim хватает на данный момент вычислительных мощностей?

Уже ручная пост-обработка данных успевает осуществляться?

#250 · 17.04.2020, 13:45

Мощностей мало не бывает :). Обработка результатов осуществляться успевает.

Yura12 отреагировал на эту запись.