Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

121 Страницы«<119120121
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#2401 Оставлено : 21 марта 2019 г. 12:58:16(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Обобщая идеи, которые появились в ходе диспута с citerra'ой и whitefox'ом, попытаемся еще что-нибудь "повертеть" в ДЛК, кроме уже подробно описанных выше поворотов интеркалятов и циклов. Интеркаляты по сути являются ЛК размером 2х2, а нельзя ли поискать в ДЛК вложенные в него ЛК размера 3x3, 4x4, ...? Оказывает можно (см. рисунок, элементы ЛК выделены красным). Несложно убедиться в том, что вместо найденного маленького ЛК можно поставить любой другой маленький ЛК того же размера из тех же значений. Например, вместо расположенного в верхнем правом углу большого ЛК на рисунке

0 1 2
1 2 0
2 0 1

можно поставить любой маленький ЛК:

0 2 1
2 1 0
1 0 2

1 0 2
0 2 1
2 1 0

и т.д., при этом большой ЛК всегда будет корректным. Для ДЛК иногда данное преобразование приводит к появлению дублирования значений на диагоналях, но это легко отслеживается и происходит не особо часто. Также в ДЛК можно поискать латинские прямоугольники — такие множества K строк {r1, r2, ...} и P столбцов {c1, c2, ...}, на пересечении которых стоит латинский прямоугольник размером KxP, образованный из max(K,P) значений (см. рисунок, элементы одного из латинских прямоугольников выделены белым). В рамках найденного латинского прямоугольника можно переставлять строки или столбцы по меньшей размерности, в таком случае, как и с рассмотренными выше преобразованиями маленьких ЛК, большой ЛК остается корректным ЛК, а в ДЛК иногда, но не часто, могут возникать дубли на диагоналях. Латинскими прямоугольниками по определению являются все пары ячеек квадрата размером 2x1 и 1х2 — они не интересны. Также латинские прямоугольники могут иметь размер YxN и NxY, Y<N, т.е. по сути любая комбинация строк и столбцов ДЛК попадает под определение корректного латинского прямоугольника, как и сам большой квадрат — под определение маленького ЛК в его составе, правда в данном случае он не такой уж и маленький и по размеру равен большому smile. Данные латинские прямоугольники и квадраты будем называть тривиальными — они не интересны в контексте рассмотренных ниже преобразований (в 1х1, 1х2 и 2х1 менять нечего, YxN и NxY уже меняются в рамках канонизации), а вот с остальными можно поработать... Для этого необходимо построить список всех нетривиальных ЛК и ЛП для заданного ДЛК, а дальше можно, как и ранее с интеркалятами и циклами, "вращать" комбинацию из 1, 2 или более ЛК/ЛП. "Вращать" тут взято в кавычки, потому как на самом деле происходит не вращение, а либо построение всех изоморфов для маленького ЛК, либо перестановка всех строк или столбцов по маленькой размерности для ЛП. А на самом деле можно вообще ничего не "вращать", а выполнять указанные преобразования с гораздо большей эффективностью в плане затрат вычислительного времени 199. С целью проверки того, будут ли данные преобразования давать что-то интересное для нашей коллекции ОДЛК, найденной в проекте, в тестовый подпроект была добавлена версия расчетного модуля 1.25 и WU'шки экспериментов exp242 ... exp249, нацеленные на "поворот" 1...5 ЛК/ЛП. Результаты поворота 1 ЛК/ЛП уже готовы и выложены выше — видно, что они позволяют получить новые КФы (+0,49% от общего числа), которые не получаются путем поворота интеркалятов и циклов. Ждем, что будет от остальных "поворотов"...

Отредактировано пользователем 21 марта 2019 г. 13:14:07(UTC)  | Причина: Не указана

Пользователь evatutin прикрепил следующие файлы:
Рис - ЛК 3х3.png
Рис - ЛП 2x4.png

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 3 пользователей поблагодарили evatutin за этот пост.
hoarfrost оставлено 21.03.2019(UTC), citerra оставлено 21.03.2019(UTC), whitefox оставлено 22.03.2019(UTC)
Offline evatutin  
#2402 Оставлено : 21 марта 2019 г. 20:03:17(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Результаты изменения 2 ЛК/ЛП в ДЛК:

Код:
ONCE (A):1 - 700, where:
2 CFs - 700

LINE3 (B):1 - 2, where:
3 CFs - 2

LINE3 (B):2 - 1, 700:1, where:
3 CFs - 1


Новых очень мало Не получается

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline evatutin  
#2403 Оставлено : 21 марта 2019 г. 21:39:45(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Раз уж мы тут начали использовать (относительно) новые понятия, давайте их посчитаем... Итак:

Зависимости числа интеркалятов от размерности ДЛК N

Минимальное число: 0, 0, 0, 12, 0, 9, 0, 0, ?, <=2
Максимальное число: 0, 0, 0, 12, 4, 9, 30, 112, ?, >=75
(оценки для размерности N=10 получены по списку ОДЛК, найденных в проекте, и в данный момент включающему чуть более чем 3,8 млн. КФ ОДЛК)


Зависимости общего числа циклов от размерности ДЛК N

Минимальное число: 1, 0, 0, 12, 10, 27, 21
Максимальное число: 1, 0, 0, 12, 14, 27, 53


Зависимости числа частичных циклов от размерности ДЛК N

Минимальное число: 0, 0, 0, 12, 0, 21, 0
Максимальное число: 0, 0, 0, 12, 8, 21, 53


Зависимости числа нетривиальных латинских прямоугольников (включая латинские квадраты размера KxK, K<N) от размерности ДЛК N

Минимальное число: 0, 0, 0, 12, 0, 21, 0
Максимальное число: 0, 0, 0, 12, 8, 21, 53


Зависимости общего числа латинских прямоугольников (включая латинские квадраты размера KxK, 1<=K<=N) от размерности ДЛК N

Минимальное число: 1, 0, 0, 137, 336, 884, 1968
Максимальное число: 1, 0, 0, 137, 348, 884, 2119


Ну а дальше — в OEIS... 199

PS. Анализируя полученные зависимости, можно заметить, что, например, для размерности N=4 все циклы и нетривиальные латинские прямоугольники являются интеркалятами и т.д. 199

Отредактировано пользователем 21 марта 2019 г. 21:55:03(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 3 пользователей поблагодарили evatutin за этот пост.
hoarfrost оставлено 22.03.2019(UTC), Vitalii Koshura оставлено 22.03.2019(UTC), citerra оставлено 22.03.2019(UTC)
Offline evatutin  
#2404 Оставлено : 22 марта 2019 г. 16:32:19(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Результаты поворота 3 ЛК/ЛП:

Код:
ONCE (A):1 - 68, where:
2 CFs - 68


Почти ничего

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline evatutin  
#2405 Оставлено : 23 марта 2019 г. 10:25:00(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Результаты поворот 4 ЛК/ЛП:

Код:
ONCE (A):1 - 4, where:
2 CFs - 4

LINE3 (B):1 - 2, where:
3 CFs - 2

LINE3 (B):2 - 1, 4:1, where:
3 CFs - 1


И 5 ЛК/ЛП в заключение эксперимента:

Код:
ONCE (A):1 - 10, where:
2 CFs - 10

Отредактировано пользователем 23 марта 2019 г. 21:01:41(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline evatutin  
#2406 Оставлено : 24 марта 2019 г. 16:24:05(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
1. По результатам серии коротких экспериментов, выполненных в проекте за последние 2 недели, была определена группа простых преобразований ОДЛК (поворот интеркалятов, поворот циклов, модификация латинских подпрямоугольников и подквадратов на заданную глубину рекурсии), которые позволяют получать дополнительные КФ ОДЛК с очень малыми затратами вычислительного времени. Не все указанные преобразования работают эффективно (в чем и заключалась цель исследования), однако оставленная совокупность позволяет в итоге поднять темп выхода КФ ОДЛК в проекте в районе 8-10%. Соответственно, в оба подпроекта были добавлены новые версии расчетного модуля с поддержкой постобработки найденных ОДЛК с использованием данных преобразований.

2. На этом исследование эффективности данных преобразований не окончено. В ходе модификации ОДЛК описанными выше простыми преобразованиями было выявлено, что часто после нее наблюдается дублирование значений на диагоналях, т.е. квадрат формально не является ДЛК и просто отбрасывается. В дискуссии с whitefox'ом сошлись на том, что среди отбрасываемых ДЛК есть много корректных ЛК, которые нам тоже интересны, только их необходимо отдавать не напрямую Эйлеру с Паркером и DLX'ом, а канонизатору. Эффективность данной группы преобразований мы и будем исследовать в ближайшее время в тестовом подпроекте (по каждому эксперименту в отдельности и по каждой смене версии расчетного модуля отписываться тут не буду, чтобы не разводить флуд, информацию буду давать кратко). Проблема в том, что канонизировать такие ЛК гораздо медленнее, чем обрабатывать ДЛК DLX'ом ("внутри" канонизатора темп обработки ДЛК выше, "снаружи" для ЛК — ниже), поэтому в настоящее время установлен порог в 1000 обрабатываемых ЛК на каждое преобразование. Если будет хороший выход новых КФ'ов, в перспективе порог можно и увеличить, что пропорционально приведет к увеличению времени обработки. Посмотрим, что из этого получится angry

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 3 пользователей поблагодарили evatutin за этот пост.
citerra оставлено 24.03.2019(UTC), Yura12 оставлено 24.03.2019(UTC), hoarfrost оставлено 25.03.2019(UTC)
Offline evatutin  
#2407 Оставлено : 25 марта 2019 г. 1:13:15(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,710
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 1040 раз
Поблагодарили: 1902 раз в 920 постах
Результаты поворота интеркалятов (без учета новых) с последующей канонизацией.

1 интеркалят

Код:
ONCE (A):1 - 7692, where:
2 CFs - 7692

LINE3 (B):1 - 6, where:
3 CFs - 6

LINE3 (B):2 - 3, 2564:1, where:
3 CFs - 3

LOOP4 (E):2 - 4, where:
4 CFs - 4

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Пользователи, просматривающие эту тему
Guest (3)
121 Страницы«<119120121
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2019, Yet Another Forum.NET
Страница сгенерирована за 0.149 секунды.