Форум

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

Проект Gerasim@Home

В ходе эксперимента e1055 в подпроекте ODLS BS найден квадрат

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

у которого 15004 диагональных трансверсалей и 3071828 ОДЛК, что позволяет усилить текущее нижнее ограничение с a(12)>=2874987 до a(12)>=3071828 в ряду https://oeis.org/A287695.

Array
hoarfrost and citerra have reacted to this post.
hoarfrostciterra

И еще один квадрат вдогонку:

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

у которого 15456 диагональных трансверсалей и 4167043 ОДЛК, что позволяет усилить текущее нижнее ограничение с a(12)>=3071828 до a(12)>=4167043 в ряду https://oeis.org/A287695.

Array
hoarfrost, SerVal and citerra have reacted to this post.
hoarfrostSerValciterra

после восстановления базы данных я заметил что https://gerasim.boinc.ru/users/viewApps.aspx стала обновляться  не каждый час в 00 минут а каждый час в 05 минут

Array
Цитата: kotenok2000 от 01.05.2021, 16:01

после восстановления базы данных я заметил что https://gerasim.boinc.ru/users/viewApps.aspx стала обновляться  не каждый час в 00 минут а каждый час в 05 минут

Так нужно. Это для того, чтобы всякие обновления статистики не запускались одновременно и меньше загружали процессор.

Array

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

За месяц найдено 376 779 КФ ОДЛК порядка 10. Среди наиболее интересных находок:

ONCE (A):1 - 297778, where:
1 CFs - 33160
2 CFs - 264618

LINE3 (B):1 - 91959, where:
2 CFs - 18735
3 CFs - 73224 (+1720)

LINE3 (B):2 - 55347, 5:1, where:
2 CFs - 18735
3 CFs - 36612 (+860)

LINE4 (C):1 - 154, where:
2 CFs - 4
4 CFs - 150 (+4)

LINE4 (C):2 - 154, where:
2 CFs - 4
4 CFs - 150 (+4)

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

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

LOOP4 (E):2 - 2264, where:
1 CFs - 2
2 CFs - 138
3 CFs - 1464
4 CFs - 660

1TO3 (F):1 - 426, where:
4 CFs - 426 (+6)

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

1TO4 (G):1 - 1342, where:
3 CFs - 882
5 CFs - 460 (+8)

1TO4 (G):4 - 556, where:
3 CFs - 441
5 CFs - 115 (+2)

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]: пройдено 458 (+72) окрестностей из 1764 (26,0%, +4,1%).

Эксперимент по исследованию быстровычислимых свойств ДЛК порядка 12 подходит к концу, осталось окончательно выяснить вопрос с максимальным числом ОДЛК для одного ДЛК, границы для остальных числовых характеристик более менее зафиксированы.

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

В ходе эксперимента e1055 в подпроекте ODLS BS проекта Gerasim@Home (http://gerasim.boinc.ru) найден квадрат

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

у которого 15264 диагональных трансверсалей и 4901623 ОДЛК, что позволяет усилить текущее нижнее ограничение с a(12)>=4167043 до a(12)>=4901623 в ряду https://oeis.org/A287695.

Array

При параллельной реализации DLX возникает проблема появления дублирующихся решений. Например, допустим, что для некоторой матрицы CM размером M строк на K столбцов покрытия существует единственное решение в виде следующего множества строк: {1, 2, 10, 15}. Простейшей стратегией распараллеливания DLX на глубину рекурсии 1 (см. анонс https://vk.com/wall162891802_1650) является фиксация одной из строк матрицы в подзадачах (другими словами, ее принудительное добавление в покрытие) и получение таким образом числа подзадач (WU'шек), равного числу строк матрицы:

* WU1 (зафиксирована строка 1);
* WU2 (зафиксирована строка 2);
* WU3 (зафиксирована строка 3);
...
* WUM (зафиксирована строка M).

В таком случае решение (покрытие) будет найдено в WU'шках с номерами 1, 2, 10 и 15, т.е. 4 раза, появятся дубли. Чтобы их отсечь при такой стратегии распараллеливания, необходимо гарантировать, чтобы решение нашлось только в одной из WU'шек, а в остальных был запрет на его нахождение. Этого можно добиться очень просто: запретить нахождение покрытий, в которых присутствуют номера строк, меньшие зафиксированной. В таком случае будет наблюдаться следующая картина:

* WU1: найдено решение {1, 2, 10, 15};
* WU2: решений не найдено ввиду того, что значение 1 (меньшее 2) запрещено;
* WU3: решений нет;
...
* WU9: решений нет;
* WU10: решений не найдено ввиду того, что значения 1, 2, ..., 9 (меньшие 10) запрещены;
* WU11: решений нет;
...
* WU14: решений нет;
* WU15: решений не найдено ввиду того, что значения 1, 2, ..., 14 (меньшие 15) запрещены;
* WU16: решений нет;
...

При практической реализации данный запрет легко реализуется путем сброса в ноль части строк матрицы покрытия CM (в случае глубины рекурсии d>1 тут не все так просто, сбрасываются не все подряд строки, но идея работает, что проверено на нескольких квадратах в проекте).

Другим способом, гарантирующим отсутствие дублей среди находимых решений, является следующий. Возьмем любую ячейку квадрата L[i][j] и построим множество трансверсалей T, которые проходят через данную ячейку. Несложно убедиться в том, что все трансверсали множества T попарно пересекаются в выбранной ячейке [i][j], а значит не могут попасть в состав одного и того же покрытия (в наших задачах — в состав одного и того же ОДЛК). А раз так, то им автоматически соответствуют разные поддеревья в дереве комбинаторного перебора, не пересекающиеся между собой по составу множеств трансверсалей в их листьях. Ну а далее, вспоминая, как строится матрица покрытия для поиска ОДЛК по известному множеству трансверсалей (см. http://ceur-ws.org/Vol-2638/paper26.pdf), автоматически получаем следующее свойство (лемма).

Если зафиксировать множество всех строк матрицы покрытия CM, которым соответствуют единицы в одном из ее столбцов, то дублей решений среди них не будет.

Причина та же самая: данные строки пересекаются и в одно и то же покрытие войти не могут, а значит им соответствуют разные не пересекающиеся поддеревья и, соответственно, разные множества решений. При этом никаких дополнительных манипуляций с матрицей покрытия (сброс строк в ноль, запреты на использование строк, апостериорная проверка дублей) делать не нужно. Распараллеливание на глубину более 1 при этом становится сложнее и выполняется рекуррентно аналогично рассмотренному выше. Число WU'шек в данном случае зависит от выбранного элемента квадрата [i][j] (или, что то же самое, — от выбранного столбца матрицы покрытия CM). В соответствии с принципом минимума возможностей выбирать рекомендуется тот элемент квадрата, через который проходит минимальное число трансверсалей: |T|->min (или, что то же самое, — столбец матрицы покрытия с минимальным числом единиц).

Например, для квадрата L

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

покрытие элементов диагональными трансверсалями имеет следующий вид:

1312 1294 1544 1306 1224 1048 1048 1224 1306 1544 1294 1312
1362 1274 1126 1086 1478 1402 1402 1478 1086 1126 1274 1362
1324 1392 1228 1424 *1020* 1340 1340 1020 1424 1228 1392 1324
1394 1086 1134 1282 1458 1374 1374 1458 1282 1134 1086 1394
1272 1372 1152 1344 1328 1260 1260 1328 1344 1152 1372 1272
1064 1310 1544 1286 1220 1304 1304 1220 1286 1544 1310 1064
1064 1310 1544 1286 1220 1304 1304 1220 1286 1544 1310 1064
1272 1372 1152 1344 1328 1260 1260 1328 1344 1152 1372 1272
1394 1086 1134 1282 1458 1374 1374 1458 1282 1134 1086 1394
1324 1392 1228 1424 1020 1340 1340 1020 1424 1228 1392 1324
1362 1274 1126 1086 1478 1402 1402 1478 1086 1126 1274 1362
1312 1294 1544 1306 1224 1048 1048 1224 1306 1544 1294 1312

Через минимальный элемент L[2][4] проходит 1020 диагональных трансверсалей, соответственно при разбиении на подзадачи получается 1020 WU'шек при размере матрицы покрытия 15456x144 (странное на первый взгляд значение, не кратное размеру CM).

Еще один пример:

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

2372 2052 2464 2380 2500 2480 2480 2500 2380 2464 2052 2372
2052 2372 2380 2464 2480 2500 2500 2480 2464 2380 2372 2052
2480 2500 2376 2048 2380 2464 2464 2380 *2048* 2376 2500 2480
2500 2480 2048 2376 2464 2380 2380 2464 2376 2048 2480 2500
2380 2464 2480 2500 2376 2048 2048 2376 2500 2480 2464 2380
2464 2380 2500 2480 2048 2376 2376 2048 2480 2500 2380 2464
2464 2380 2500 2480 2048 2376 2376 2048 2480 2500 2380 2464
2380 2464 2480 2500 2376 2048 2048 2376 2500 2480 2464 2380
2500 2480 2048 2376 2464 2380 2380 2464 2376 2048 2480 2500
2480 2500 2376 2048 2380 2464 2464 2380 2048 2376 2500 2480
2052 2372 2380 2464 2480 2500 2500 2480 2464 2380 2372 2052
2372 2052 2464 2380 2500 2480 2480 2500 2380 2464 2052 2372

L[2][8], |T|=2048 диагональных трансверсалей, число подзадач 2048, размер матрицы покрытия 28496x144.

Array
hoarfrost and AenBleidd have reacted to this post.
hoarfrostAenBleidd

Ребятки, кто-нибудь знает, есть ли здесь возможность вставлять код С++  или просто [code]... [/code] ?

Вот например, Эдуард Игоревич добавляет ВУшки в проект

В логах сервера:

[code = c++]

<wu_addition>
<archive_name>WUs5.zip</archive_name>
<app_name>gt_cl</app_name>
<n_wu_processed>95232</n_wu_processed>
<n_wu_inserted>95232</n_wu_inserted>
<start_time>04 May 2021, 15:06:12</start_time>
<end_time>04 May 2021, 15:09:00</end_time>
<duration>2 minutes, 48 seconds</duration>
</wu_addition>

[/code]

  • или как-нибудь ещё?
Array

Уважаемые участники проекта! У меня к вам большая просьба 🙂 дружно навалиться на подпроект Graph Coloring! Зачем...

 

Сейчас мы подошли к интересному рубежу — подсчету ОДЛК порядка 12 для квадратов с числом трансверсалей в диапазоне 24 000 - 29 000. Это много... Для сравнения, квадраты с числом трансверсалей в районе 5 000 считаются нормально и так без особых ухищрений, при числе трансверсалей в пределах 10 000 - 15 000 для их обсчета пришлось сделать распределенную версию DLX'а (вы наверняка помните WU'шки эксперимента e1054, которые висели по нескольку суток — это как раз оно самое), сейчас она почти отработала (висят хвосты) на глубине рекурсии d=1, в квадратах оказалось от ~1 до ~5 млн. ОДЛК. Теперь на очереди еще более тяжелая серия квадратов... Если считать их с той же глубиной рекурсии d=1, то одна WU'шка по моим прикидкам будет считаться минимум 7-10 суток, что тяжело. Разбиение сделано на глубину d=2, WU'шек при это получается около 20 млн., зато считаются они не дольше 5 минут, но... При таком разбиении многим из них не соответствует покрытий, что при расчете в проекте выясняется за несколько секунд. Примерное соотношение: 20% 5-минутных WU'шек и остальные 80% совсем короткие. Заранее отсечь короткие WU'шки на своей машине я не могу (точнее, это будет очень долго, неделями). Поэтому мы имеем подпроект, в котором много коротких WU'шек. Это неудобно, но ненадолго, прошу простить и понять :). Если считать его параллельно с остальными подпроектами, то на расчет потребуется около 200 дней (ввиду особенностей выдачи заданий Герасимом). Если пустить всю мощь проекта на этот подпроект, расчет завершится за 5 суток, что я и хочу сделать с вашей помощью. Выдачу заданий в других подпроектах я временно запретил, очень хочу посчитать эту партию, потом вернемся в обычный режим. Очень прошу поддержать техникой (в том числе слабой, от нее здесь будет хороший толк) и проверить наличие соответствующей галочки в профиле напротив подпроекта Graph Coloring. Заодно проведем стресс-тестирование новой аппаратной конфигурации сервера Герасима... 🙂

Array

Сейчас Пентатлон начался.... Много мощностей уйдёт туда.

Array