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

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

Уведомление

Icon
Error

106 Страницы«<104105106
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#2101 Оставлено : 21 октября 2017 г. 10:47:46(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 938 раз
Поблагодарили: 1552 раз в 759 постах
Автор: Disel Перейти к цитате
Вы планируете что-либо предпринять, что бы изменить данную ситуацию?


Поймите меня правильно, над расчетной частью проекта я работаю один, я не могу одновременно заниматься 10 делами. Сейчас на мой взгляд важнее подправить научную часть в сторону новых симметрий, чем я и занимаюсь, пока меня не сорвали по работе на очередные никому не нужные бумажки

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline evatutin  
#2102 Оставлено : 23 октября 2017 г. 14:54:45(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 938 раз
Поблагодарили: 1552 раз в 759 постах
В проекте запущен новый эксперимент e44, целью которого является поиск ОДЛК на базе обобщенных симметрий. В двух словах попытаюсь объяснить, что это такое smile
Если вы читаете форум, то недавно я постил сюда информацию о том, что

Найдена еще одна (центральная) симметрия, симметрию можно описывать математической функцией
Центр симметрии можно сместить
Можно найти примеры не очевидных симметрий

Таким образом, кроме очевидных и известных симметрий относительно прямых, проходящих через центр квадрата, или центральной точки симметрии есть и еще симметрии, которые получаются либо математически (в проекте будет делаться именно так), либо путем вращения квадрата на торе (это для наглядности, у кого богатое воображение smile ), либо похожими способами, но без вращения и без тора smile. А раз есть новые симметрии, значит необходимо попытаться построить соответствующие им ОДЛК! Это было опробовано на моей машине в несколько потоков, результаты были проверены citerra'ой: найдено несколько десятков новых КФов однушек (этого добра у нас много, более 200 тысяч), несколько десятков КФов двушек (это уже интереснее, они довольно редки) и две разные КФ четверок без очевидных симметрий (это весьма интересно). А раз так, значит за данными симметриями может скрываться довольно много интересных комбинаторных структур, которые весьма интересно получить 199

При простом подходе (полный (ODLS@Home) либо случайный (Gerasim@Home) перебор) вероятность обнаружить данные структуры весьма мала. Известно, что приблизительно на 30 млн. ДЛК порядка 10 общего вида приходится 1 пара ОДЛК. Приблизительно на 1000 пар ОДЛК однушек приходится 1 двушка. Ну а все остальное (трешки, четверки, ...) — получить просто так вообще маловероятно (хотя некоторым везет smile ), нужен специальный подход.

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

Какие симметрии нам известны? Прежде всего это очевидные горизонтальная и вертикальная (транспонированием или вращением на 90 градусов приводится к горизонтальной, поэтому не интересна). Также это недавно найденная центральная симметрия, которой правда для N=10 вроде бы нет (но мы это проверим попозже повнимательнее!). Кроме этих очевидных есть еще с десяток не очевидных (картинку я рисовал в последнем посте по ссылкам выше 199 ). На данный момент в квадратах четного порядка замечены 14 разных симметрий (имен пока у них нет, можно придумать, как в истории с рыбой, о которой расскажу чуть позже после выхода соответствующей публикации Present, пока ДСП):
* для 3 симметрий нет диагональных заполнений (в сильно нормализованной форме в соответствии с положениями whitefox'а), а значит нет ДЛК и, соответственно, ОДЛК;
* для 2 симметрий проверить отсутствие ОДЛК мне удалось в 1 поток на своей машине — для них число ДЛК составляет 48 526 336 и ни одного ОДЛК;
* остались еще 9, с ними все неоднозначно.
Для некоторых из этих 9 ДЛК есть, причем по всем линейкам, но ОДЛК нет. Для некоторых ОДЛК есть и прекрасно находятся даже в 1 поток, что уж говорить про грид — с помощью проекта мы сможем найти их весьма много angry, чем и будем заниматься

Теперь как все это работает. На машину кранчера приходит одно из начальных заполнений квадрата в соответствии с выбранной при генерации заданий симметрией, дальше оно дозаполняется всеми возможными способами с сохранением выбранной симметрии, находятся ОДЛК, которые передаются на сервер проекта и потом забираются для постобработки и анализа. Число дозаполнений в WU'шке варьируется, в большинстве случаев оно составляет порядка 300-500 тыс. ДЛК на WU'шку, в редких случаях оно может быть меньше или больше. По времени счета на Core i7 4770 это составляет в среднем около 10-15 минут, чуть быстрее предыдущего эксперимента e43 (он актуален, его результаты также забираются и анализируются, их не прерывать!). Редко когда дозаполнений может не быть, тогда WU'шка закончится сразу после старта, или быть много (мне попадались начальные заполнения с 1 185 792 ДЛК, время обработки около 1 часа) — все нужно обрабатывать, ничего не прерывать, все пойдет в дело! WU'шки пока считаются с кворумом 2, дедлайн 7 дней. Чекпоинтов нет, т.к. там внутри работает довольно сложный полный перебор с кучей наворотов (X-образное заполнение + дозаполнение 1 при генерации заданий + дозаполнение 2 на машине кранчера), внутри него сделать чекпоинт не так то и просто, однако думаю это не проблема учитывая малое время счета заданий. С прогрессом тут тоже есть определенная проблема, т.к. число дозаполнений для каждого начального заполнения неизвестно (его можно посчитать за несколько минут, но зачем тратить впустую вычислительное время). Из-за этой причины прогресс считается линейно исходя из максимально найденного числа заполнений (1 185 792 ДЛК), приведенного выше (на самом деле процесс нелинейный). Следствием этого является то, что некоторые WU'Шки могут перепрыгивать по прогрессу например с 40% сразу на 100%, если дозаполнения закончились. Теоретически прогресс может перевалить за 100% (такое бывает не только на выборах smile ), если число дозаполнений окажется больше, чем предполагалось — в этом нет ничего страшного, пусть считается, будет больше ОДЛК

PS. Ну и попутно сообщу, что во время отладки рекурсии пришлось проверять новый код с симметриями на известных примерах — теория whitefox'а про СНДЛК работает, число дозаполнений у меня совпало со значениями, которые он приводил, хотя местами пришлось почесать репу на предмет того, почему горизонтально симметричных заполнений получается почти в 2 раза больше, чем в OEIS'е smile

PPS. Приглашаю всех к поиску симметрий в ДЛК и ОДЛК порядка 10! Present

PPPS. Время текущего эксперимента, как и предыдущих, целиком и полностью лимитируется скоростными характеристиками процесса построения трансверсалей и покрытия из них. Если кому-либо удастся сделать более быстрый DLX, чем получилось у меня, или предложить еще более быстрый подход, время эксперимента удастся снизить 199

Отредактировано пользователем 23 октября 2017 г. 15:21:49(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 3 пользователей поблагодарили evatutin за этот пост.
citerra оставлено 23.10.2017(UTC), ReaDy оставлено 23.10.2017(UTC), Yura12 оставлено 23.10.2017(UTC)
Offline evatutin  
#2103 Оставлено : 23 октября 2017 г. 18:43:30(UTC)
evatutin


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

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

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

Сказал(а) «Спасибо»: 938 раз
Поблагодарили: 1552 раз в 759 постах
Процесс пошел! За полдня счета ошибок валидации нет, все вроде считается нормально, +57 новых КФов к списку находок Герасима (не к общему списку citerra'ы, обращаю внимание, об этом он сам расскажет, а именно к списку находок проекта). Первая находка — горизонтально симметричная двушка с характеристикой ортогональности 52:

Код:
0 1 2 3 4 5 6 7 8 9
3 9 4 7 1 8 2 5 0 6
7 6 1 5 9 0 4 8 3 2
9 7 6 8 5 4 1 3 2 0
8 3 5 9 2 7 0 4 6 1
2 0 8 4 6 3 5 1 9 7
6 4 9 2 8 1 7 0 5 3
5 2 3 1 0 9 8 6 7 4
1 5 0 6 7 2 3 9 4 8
4 8 7 0 3 6 9 2 1 5



Работаем дальше Present

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

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