Message boards :
Science :
Принципиально новый алгоритм PADLS
Message board moderation
Author | Message |
---|---|
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
В разработке новый алгоритм PADLS. Этот алгоритм принципиально отличается от предыдущей версии алгоритма. Программа уже написана, выполняю тестирование. Пока только иллюстрация. Весна пришла, выходим на природу :) ![]() Первый ДЛК, полученный генератором. Сгенерировано в первой порции 651701 псевдоассоциативных ДЛК. Удивило то, что все они КФ. Во второй порции ДЛК ещё больше сгенерировалось - 830436 шт. И они тоже все КФ! Как и в предыдущей версии, в новом алгоритме три этапа: генерация псевдоассоциативных ДЛК, канонизация сгенерированных ДЛК (программа Белышева kanonizator_dlk_1.03), проверка полученных КФ ДЛК на ОДЛК (программа Белышева family_mar). Генератор в данной версии один, написан мной. Позже, возможно, выложу тест. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Как и в предыдущей версии, WU - это строка из 8 элементов. Например, для самой первой группы ДЛК (из которой ДЛК на показанной иллюстрации) это будет строка 2 3 4 5 7 8 9 6 От этого WU генератор произвёл 651701 псевдоассоциативных ДЛК, которые все оказались КФ. Довольно большая порция для проверки. Проверено, найдено 12 уникальных КФ ОДЛК. Для второго WU имеем следующую строку 2 3 4 5 7 9 8 6 От этого WU получено 830436 псевдоассоциативных ДЛК, и все они тоже КФ! Сейчас проверяю эту порцию ДЛК программой family_mar. Проверяется у меня долго. Всего в этом эксперименте 3713 WUs (строк). На моём ПК за реальное время эксперимент не выполнить. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Вчера проверила 100000 ДЛК из второй порции ДЛК, найден один марьяжный ДЛК. Сегодня проверила 300000 ДЛК Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 300000 Найдено марьяжных ДЛК: 4 они записаны в файл output.txt Время работы в сек : 15646.8 Ещё 4 марьяжных ДЛК найдено. Проверена почти половина всех ДЛК. PS. Проверка сегодня шла больше 4-х часов. Долго :( |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Проверила ещё 200000 ДЛК Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 200000 Найдено марьяжных ДЛК: 2 они записаны в файл output.txt Время работы в сек : 10658.5 Запустила последнюю порцию - 230436 ДЛК. Ну вот, собственно, я протестировала два WU. Решения есть. От первого WU все 12 найденных КФ ОДЛК уникальные. От второго WU скоро проверю. Стоит ли выкладывать скрипт для тестирования? Он кому-то нужен? |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Уф! Наконец-то закончилась проверка последней порции Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 230436 Найдено марьяжных ДЛК: 1 они записаны в файл output.txt Время работы в сек : 10401 Ещё один марьяжный ДЛК найден. Осталось проверить все найденные решения на уникальность. Все найденные марьяжные ДЛК дают уникальные однушки, 16 уникальных КФ ОДЛК получено. Тестирование эксперимента можно считать выполненным. Выполнять эксперимент пока негде. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
У самого синего моря :) ![]() Это первый (из 830436) псевдоассоциативный ДЛК, полученный генератором от второго WU. Второму WU соответствует строка 2 3 4 5 7 9 8 6 Взяться что ли за следующий WU? Долго у меня проверяется порция ДЛК :( Эх, ну почему никто не хочет взять индивидуальный эксперимент? Demis и XAVER выполняют же! Ничего, не страшно. Один господин на форуме команды из Германии написал, что в консоли ничего не понятно. Ну да, кодировка... Однако XAVER работает и не жалуется. Ещё этот господин написал: "Вдруг обнаружил, что строки надо получить по запросу." Да, верно, по запросу. Не бойтесь! Вирусов я не рассылаю :) Вы можете написать мне ЛС здесь, на форуме. Здесь и вышлю вам строки, сколько запросите. Конечно, здесь в сообщение много строк не втолкаешь, но строк 20 запросто можно. Тут-то уж точно вирусы не живут :) |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Да, забыла самое главное... Если вы внимательно посмотрите на два показанных псевдоассоциативных ДЛК, увидите, что они из линейки №39. Вот в этом и принципиальное отличие данного эксперимента от предыдущих версий. Все предыдущие версии эксперимента PADLS обрабатывали (и обрабатывают) псевдоассоциативные ДЛК из трёх линеек: 15, 38, 51. В ДЛК этих линеек обе диагонали (главная и побочная) полностью ассоциативны. Осенила мысль: а почему нельзя нарушить ассоциативность в побочной диагонали? Оказалось, что вполне можно. Выбрала линейку с побочной диагональю, в которой минимальные нарушения ассоциативности. Это линейка №39. Посему этот эксперимент называется PADLS rule 39. И ещё напомню: в этом эксперименте всего 3713 WUs, два из них я уже обработала при тестировании. То есть эксперимент вполне реально выполнить в ручном проекте. Ну, конечно, помощнее моего ПК нужна техника. PS. ПО эксперимента выложу в Облако на mail.ru, ежели оно вдруг понадобится кому-то. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
О-о-о! Запустила генератор для третьего WU. Сгенерировалось 1189493 псевдоассоциативных ДЛК, и все они КФ! Чудеса! Ну, это у меня очень долго проверять. Не буду пока. Да у меня ещё два других эксперимента постоянно выполняются. Первый псевдоассоциативный ДЛК в порции от третьего WU 0 2 3 4 5 8 7 9 6 1 3 1 4 0 6 7 9 5 2 8 4 6 2 1 7 9 8 0 5 3 5 0 7 3 2 1 4 8 9 6 9 7 8 5 4 6 0 3 1 2 7 8 6 9 3 5 2 1 4 0 1 9 5 7 8 3 6 2 0 4 6 4 9 8 0 2 1 7 3 5 2 5 1 6 9 0 3 4 8 7 8 3 0 2 1 4 5 6 7 9 Сейчас я его разукрашу :) ![]() |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
А это последний псевдоассоциативный ДЛК от третьего WU 0 2 3 4 5 8 7 9 6 1 9 1 8 6 7 3 0 5 2 4 7 6 2 5 9 1 8 0 4 3 5 9 7 3 6 2 4 8 1 0 2 7 5 9 4 6 1 3 0 8 1 0 6 8 3 5 2 4 9 7 4 8 1 7 0 9 6 2 3 5 6 4 9 1 8 0 3 7 5 2 3 5 4 0 2 7 9 1 8 6 8 3 0 2 1 4 5 6 7 9 Разукрасить этот ДЛК предоставляю читателям :) Интересная порцийка получилась. Сколько она даст решений? Ещё такой нюанс в этом эксперименте: поскольку ДЛК из линейки №39 ещё не проверялись, есть надежда на малую повторяемость решений. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Цитата Запустила генератор для третьего WU. Сгенерировалось 1189493 псевдоассоциативных ДЛК, и все они КФ! Чудеса! С утречка, на свежую голову, чудеса разъяснились :) Вспомнила о соотношении КФ и СН ДЛК в разных линейках. Продублирую сообщение Белышева об этом, благо и ссылка сохранилась 1 48 отсюда http://forum.boinc.ru/default.aspx?g=posts&m=87625#post87625 Смотрим на линейку №39, соотношение КФ к СН ДЛК в этой линейке 1:2 (конечно, в среднем). В-о-о-о-т! А в линейке №38 "в среднем только 1 СНДЛК из 48 является КФ". Для эксперимента PADLS очень благоприятно соотношение в линейке №39: почти все сгенерированные псевдоассоциативные ДЛК будут КФ. В первых трёх порциях все сгенерированные псевдоассоциативные ДЛК являются КФ. Я даже удивилась сначала этому факту. Теперь всё понятно. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Просмотрела ещё раз внимательно побочные диагонали линеек. Есть другая линейка, в которой возможны псевдоассоциативные ДЛК с минимальными нарушениями в побочной диагонали. Но есть некоторая особенность. Надо написать программу-генератор, чтобы увидеть генерируемые псевдоассоциативные ДЛК воочию. Займусь программой. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Итак, встречайте: псевдоассоциативные ДЛК в линейке №16 ![]() Получились, но... очень низкая степень ассоциативности в ДЛК. Чем меньше степень ассоциативности, тем больше генерируется псевдоассоциативных ДЛК. Но! Тем меньше будет решений от таких ДЛК и мала вероятность солидных групп пар ОДЛК. В данном примере (для первого WU) сгенерировала 2000000 псевдоассоциативных ДЛК, и это ещё не все, просто я поставила в программе ограничение на количество генерируемых квадратов, сразу предположив, что их будет очень много. На иллюстрации вы видите первый ДЛК и 2000000-й ДЛК. В этом эксперименте 6184 WUs и от каждого WU очень много псевдоассоциативных ДЛК. К тому же, соотношение КФ к СН ДЛК в этой линейке 1:2. Не проверяла сгенерированные ДЛК на ОДЛК, слишком много их. Может быть, потом сгенерирую поменьше и проверю. В общем, псевдоассоциативные ДЛК в линейке №16 у меня получились похуже, нежели в линейке №39. Может быть, можно по-другому написать генератор, не такой, как я написала. Думайте сами, решайте сами... PS. Интересное получается ассоциативное ядро (подквадрат 4х4) в центре ДЛК; похоже, оно будет во всех ДЛК. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Да, и... все 2000000 сгенерированных псевдоассоциативных ДЛК являются КФ, как утверждает программа Белышева kanonizator_dlk_1.03 Канонизатор ДЛК10 Загружена хеш-таблица Время загрузки: 0.015 сек Введено ДЛК: 2000000 Время загрузки: 49.483 сек Найдено КФ: 2000000 Время поиска: 5.913 сек КФ записаны в файл: output.txt Время записи: 2.511 сек Общее время работы: 57.938 сек Это сколько ж ДЛК надо проверять! И это ещё не всё для первого WU, надо снять ограничение, чтобы все ДЛК сгенерировать. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
В эксперименте PADLS rule 39 всё-таки проверила третью порцию псевдоассоциативных ДЛК (1189493 шт.), негоже останавливаться на середине проверки WU. За два рабочих дня управилась. Найдено 6 марьяжных ДЛК, все уникальные однушки, 12 уникальных КФ ОДЛК. Вот все 6 марьяжных ДЛК 0 2 7 4 3 8 9 5 6 1 7 1 0 9 5 3 8 6 2 4 5 6 2 7 0 9 1 3 4 8 1 4 6 3 9 2 7 8 5 0 9 8 1 0 4 6 5 2 3 7 3 9 4 6 8 5 0 1 7 2 2 7 8 5 1 0 6 4 9 3 8 5 9 1 2 4 3 7 0 6 6 0 3 2 7 1 4 9 8 5 4 3 5 8 6 7 2 0 1 9 0 2 7 6 3 9 8 5 4 1 9 1 4 5 7 8 0 6 2 3 8 3 2 9 6 4 1 0 5 7 6 7 0 3 8 2 4 9 1 5 5 0 3 1 4 7 9 8 6 2 4 6 8 7 9 5 2 1 3 0 2 9 1 8 5 0 6 3 7 4 1 4 6 0 2 3 5 7 9 8 7 5 9 2 0 1 3 4 8 6 3 8 5 4 1 6 7 2 0 9 0 2 4 5 9 7 8 6 3 1 4 1 6 2 3 8 5 9 0 7 6 8 2 7 0 4 1 3 9 5 7 0 5 3 8 9 2 1 6 4 2 7 3 1 4 6 9 0 5 8 1 9 8 6 7 5 3 2 4 0 9 3 0 8 5 1 6 4 7 2 8 5 9 0 6 2 4 7 1 3 3 4 1 9 2 0 7 5 8 6 5 6 7 4 1 3 0 8 2 9 0 2 6 5 7 9 8 4 3 1 7 1 8 6 5 3 0 9 2 4 6 8 2 1 9 4 7 0 5 3 1 5 7 3 0 6 4 8 9 2 8 3 9 0 4 7 2 6 1 5 4 9 0 2 8 5 1 3 7 6 3 7 4 9 1 2 6 5 0 8 9 4 3 8 2 1 5 7 6 0 2 6 5 4 3 0 9 1 8 7 5 0 1 7 6 8 3 2 4 9 0 6 7 4 5 2 9 8 3 1 9 1 3 2 8 4 7 6 0 5 6 7 2 9 1 8 0 3 5 4 8 0 4 3 6 9 2 5 1 7 5 2 1 7 4 6 8 0 9 3 2 3 0 6 7 5 1 9 4 8 7 8 9 5 3 1 6 4 2 0 1 4 8 0 9 3 5 7 6 2 3 9 5 1 0 7 4 2 8 6 4 5 6 8 2 0 3 1 7 9 0 5 8 4 2 9 7 6 3 1 8 1 7 6 3 2 9 4 0 5 5 9 2 7 0 1 8 3 4 6 9 8 5 3 1 7 4 2 6 0 1 7 3 9 4 6 5 0 2 8 4 0 6 1 8 5 2 9 7 3 2 3 1 5 7 0 6 8 9 4 3 6 9 8 5 4 0 7 1 2 6 2 4 0 9 3 1 5 8 7 7 4 0 2 6 8 3 1 5 9 Итак, обработала 3 WUs, от каждого WU нашлись решения и все уникальные! Никаких повторений. Эксперимент обещает быть эффективным. Посмотрим, когда дойдёт до него очередь. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Как из стека, в голове выползла эта задача Итак, встречайте: псевдоассоциативные ДЛК в линейке №16 Стек работает :) Итак, сгенерировала 300000 псевдоассоциативных ДЛК в линейке №16 и запустила в проверку. Все они КФ. Интересно же всё-таки хоть чуть-чуть пощупать эту линейку. Псевдоассоциативных ДЛК в этой линейке очень много генерируется. А будут ли решения от них? Пока не знаю, надо экспериментировать. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Принципиально новых алгоритмов PADLS на данный момент разработано два: PADLS rule 16 и PADLS rule 39. Второй алгоритм я уже немножко потестировала, три WU проверила, решения нашлись от каждого WU и все уникальные. Сейчас тестирование этого эксперимента остановлено. Эксперимент ждёт своей очереди на выполнение. В эксперименте PADLS rule 16 есть сложности, о которых сказано выше. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Вот, проверилась порцийка псевдоассоциативных ДЛК из линейки №16 Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 300000 Найдено марьяжных ДЛК: 2 они записаны в файл output.txt Время работы в сек : 15830.9 Две уникальные однушечки 0 4 9 6 7 2 8 5 3 1 9 1 8 4 5 3 7 2 0 6 8 0 2 5 6 1 9 3 7 4 5 6 0 3 8 9 4 1 2 7 3 8 1 7 4 6 2 9 5 0 6 7 4 9 2 5 3 0 1 8 1 2 3 8 0 7 6 4 9 5 4 3 5 1 9 8 0 7 6 2 2 9 7 0 1 4 5 6 8 3 7 5 6 2 3 0 1 8 4 9 0 5 4 8 3 7 2 6 9 1 4 1 5 7 8 9 3 0 2 6 1 8 2 6 9 0 7 3 5 4 5 9 7 3 6 1 4 8 0 2 7 2 0 1 4 6 9 5 3 8 9 4 6 0 7 5 8 2 1 3 2 3 8 5 1 4 6 9 7 0 3 6 9 2 0 8 1 7 4 5 6 0 1 9 2 3 5 4 8 7 8 7 3 4 5 2 0 1 6 9 Итак, решения имеются и в этой ветви эксперимента PADLS. Это только маленькая часть всей порции от одного WU, в которой более 2 миллионов ДЛК. Если всё проверить, может, ещё решения найдутся. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Продолжаю проверку порции псевдоассоциативных ДЛК от первого WU в линейке №16, надо уж довести проверку этого WU до конца. Сегодня сгенерировала 350000 ДЛК; проверялись очень долго (у меня работают одновременно 4 программы) Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 350000 Найдено марьяжных ДЛК: 3 они записаны в файл output.txt Время работы в сек : 22470.5 Если бы работали только две программы, было бы в 2 раза быстрее. Ну, решеньица есть - 3 марьяжных ДЛК, они дали три уникальные однушки. Вот они сами - марьяжные 0 3 7 4 8 2 9 5 6 1 4 1 8 2 7 9 5 6 0 3 5 0 2 1 6 4 8 3 9 7 9 7 0 3 5 8 4 2 1 6 2 6 1 9 4 7 3 0 5 8 1 8 3 6 2 5 7 9 4 0 7 9 5 8 0 3 6 1 2 4 8 4 9 0 1 6 2 7 3 5 3 5 6 7 9 0 1 4 8 2 6 2 4 5 3 1 0 8 7 9 0 5 3 4 7 8 9 6 2 1 2 1 7 5 6 4 3 9 0 8 4 0 2 1 8 9 7 3 6 5 1 2 6 3 9 7 4 8 5 0 3 8 1 9 4 6 0 5 7 2 8 4 9 6 2 5 1 0 3 7 5 7 4 8 1 0 6 2 9 3 9 3 5 2 0 1 8 7 4 6 6 9 0 7 5 3 2 1 8 4 7 6 8 0 3 2 5 4 1 9 0 6 7 9 8 4 3 5 2 1 7 1 6 5 3 2 9 4 0 8 4 8 2 7 0 9 1 3 5 6 2 5 8 3 9 1 4 0 6 7 3 7 0 1 4 6 2 8 9 5 8 9 3 6 7 5 0 2 1 4 9 0 4 8 5 7 6 1 3 2 1 3 9 2 6 8 5 7 4 0 6 2 5 4 1 0 7 9 8 3 5 4 1 0 2 3 8 6 7 9 Итак, на 650000 ДЛК есть 5 марьяжных ДЛК, все уникальные однушки. Напомню: в порции больше 2 миллионов псевдоассоциативных ДЛК. Кстати, сгенерирую все ДЛК от этого WU, сколько там ещё сверх 2 миллионов будет. Интересно! И все проверю маленькими порциями. |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Это 300001-й псевдоассоциативный ДЛК от проверяемого WU 0 2 3 4 5 6 7 8 9 1 2 1 9 7 6 8 3 5 0 4 4 5 2 0 8 1 9 3 6 7 1 7 6 3 2 0 4 9 5 8 3 6 7 9 4 2 8 0 1 5 9 8 4 1 7 5 0 6 3 2 8 4 0 5 9 7 6 1 2 3 5 0 8 2 3 9 1 7 4 6 7 9 5 6 1 3 2 4 8 0 6 3 1 8 0 4 5 2 7 9 Обратите внимание на ассоциативное ядро (подквадрат 4х4) в центре ДЛК. Интересное ядро; оно было и в показанных выше псевдоассоциативных ДЛК из линейки №16. Дублирую иллюстрацию ![]() |
![]() ![]() Send message Joined: 6 Apr 17 Posts: 13824 Credit: 0 RAC: 0 |
Сегодня проверила ещё маленькую порцийку - 200000 КФ ДЛК из линейки №16 Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 200000 Найдено марьяжных ДЛК: 1 они записаны в файл output.txt Время работы в сек : 14447.6 Ещё одна уникальная однушечка найдена 0 6 3 7 8 9 2 4 5 1 3 1 7 9 6 4 5 8 2 0 5 7 2 4 0 1 8 3 9 6 4 2 1 3 9 8 0 6 7 5 2 9 0 8 4 6 7 5 1 3 9 0 4 2 7 5 3 1 6 8 1 3 8 5 2 0 6 9 4 7 6 8 9 0 5 2 1 7 3 4 7 4 5 6 1 3 9 0 8 2 8 5 6 1 3 7 4 2 0 9 Проверено 850000 КФ ДЛК. Впереди ещё много. |
©2024 (C) Progger