Message boards :
Science :
О серии алгоритмов PADLS
Message board moderation
Author | Message |
---|---|
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Поскольку ветвей алгоритма PADLS стало много, надо их все собрать в одном месте с подробным описанием. Аббревиатура PADLS означает: псевдоассоциативные ДЛК в английском написании - Pseudo-Associative Diagonal Latin Squares. Разработка алгоритма PADLS начиналась мной в теме "Ассоциативные ДЛК" в декабре 2017 г. Цитирую сообщение от 24 декабря 2017 г. из этой темы Решила "отпустить" последнюю пару строк, то есть не выполнять в этих строках требование ассоциативности. отсюда https://boinc.progger.info/odlk/forum_thread.php?id=51&postid=1247#1247 Вот с этого момента и начался алгоритм PADLS. Первая программа, которую я написала для получения псевдоассоциативных ДЛК, - это генератор 1. Как известно, ассоциативных ДЛК 10-го порядка не существует. Вместе с тем известно, что ассоциативные ДЛК 9-го порядка дают очень много ортогональных ДЛК. Вот из этих двух известных фактов и появилась идея поискать ОДЛК для псевдоассоциативных ДЛК 10-го порядка. Идея оказалась весьма эффективной. Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
В линейках 15, 38, 51 обе диагонали - главная и побочная - полностью ассоциативны. [Термин линейка, а также правила составления СН ДЛК в линейках, из теории Белышева.] С этих линеек и был начат алгоритм PADLS. На приведённой выше иллюстрации вы видите псевдоассоциативный ДЛК из линейки 15. Итак, первые три ветви алгоритма PADLS соответствуют трём указанным линейкам: 1. PADLS rule 15 2. PADLS rule 38 3. PADLS rule 51 В этих экспериментах (при первом их выполнении) работал только один генератор псевдоасоциативных ДЛК - генератор 1. Эти ветви эксперимента я начала выполнять на своём ПК сразу же, как алгоритм был разработан. В апреле 2018 г. в этом эксперименте были получены уникальные семёрка и десятка, смотрите сообщения https://boinc.progger.info/odlk/forum_thread.php?id=1&postid=1741#1741 https://boinc.progger.info/odlk/forum_thread.php?id=1&postid=1742#1742 Потом ко мне присоединился Demis. Конечно, у него выполнение экспериментов пошло намного быстрее. Я тоже продолжала эксперимент. Тут есть важный момент: мы пропускали довольно большие множества исходных строк, так как шли сплошные повторы решений. Но мало ли что мы могли пропустить! Эти три ветви были завершены, но вот с такими белыми пятнами. Решений эти ветви эксперимента дали очень много, в том числе - много солидных групп пар ОДЛК. Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
И ещё одно обстоятельство было замечено при первом выполнении трёх ветвей эксперимента PADLS: не для всех исходных строк генерировались псевдоассоциативные ДЛК. Так например, из 6164 строк линейки 15 только 3388 строк давали ДЛК. Это обстоятельство было учтено при усовершенствовании алгоритма. Я написала программку фильтрации строк. Ну и главное усовершенствование состояло в добавлении нового генератора псевдоассоциативных ДЛК - генератора 2. Генератор 1 генерировал ДЛК с нарушением ассоциативности в двух центральных строках. Генератор 2 генерировал ДЛК с нарушением ассоциативности в четырёх центральных строках. Цитата Показываю примеры псевдоассоциативных ДЛК в данной ветви эксперимента, произведённых генераторами 1 и 2 в одном и том же WU (для одной и той же строки) отсюда https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3162#3162 Итак, появился усовершенствованный алгоритм для тех же трёх ветвей. Я решила выполнить эксперимент с повторным применением генератора 1 - по указанной выше причине (белые пятна при первом выполнении). Ну, и добавился генератор 2. Усовершенствованная ветвь эксперимента PADLS rule 38 была выполнена в BOINC-проекте Tomas Brada. Результаты выложены здесь https://boinc.tbrada.eu/download/padls_13.zip Аналогичная ветвь эксперимента PADLS rule 15 завершается Demis, осталось совсем чуть-чуть. И третью аналогичную ветвь эксперимента PADLS rule 51 выполняет XAVER. Выводы уже можно сделать: 1. Решений при первом выполнении этих трёх ветвей эксперимента мы с Demis потеряли мало. 2. Генератор 2 даёт больше псевдоассоциативных ДЛК, но от них получается меньше решений (ОДЛК). Думаю, что не последнюю роль тут играет степень ассоциативности ДЛК, то есть как много в ДЛК нарушений ассоциативности. 3. В экспериментах высокая повторяемость решений. Ну, причина этого понятна: изоморфизм генерируемых псевдоассоциативных ДЛК. Отчёты о выполнении ветвей эксперимента PADLS rule 15 и PADLS rule 51 смотрите в теме https://boinc.progger.info/odlk/forum_thread.php?id=107 Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Ещё были у меня эксперименты с вариантами побочных диагоналей. Таких ветвей было несколько, я выполняла эти эксперименты сама. Но была одна ветвь, выполненная в BOINC-проекте Tomas Brada. Посмотрите на эту фотографию На фотографии хорошо видна побочная диагональ (в начале страницы) 8 2 3 4 0 9 5 6 7 1 Это были интересные ветви, они дали довольно много уникальных решений. Решения выложены здесь https://boinc.tbrada.eu/download/padls_10.zip https://boinc.tbrada.eu/download/padls_12.zip В этих экспериментах работали оба моих генератора. Много уникальных решений я сама нашла в этих вариантах эксперимента. Можно бы и продолжить варьирование побочной диагонали. PS. А далее на странице уже написано о ветви PADLS rule 38, выполненной в проекте Tomas Brada. Об этой ветви рассказано выше. В конце страницы написано о ветви эксперимента PADLS rule 15, которую я начала сама, а потом продолжил Demis. Сейчас он завершает этот эксперимент. Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Далее я написала генератор 3. Смотрите тему https://boinc.progger.info/odlk/forum_thread.php?id=105 Этот генератор можно применять для генерирования псевдоассоциативных ДЛК в линейках 15, 38, 51, а также для вариантов побочной диагонали (полностью ассоциативной). На иллюстрации показан псевдоассоциативный ДЛК с вариантом побочной диагонали, полученный генератором 3 Нарушения ассоциативности в ДЛК, производимых данным генератором, в 6 центральных строках. Из-за низкой степени ассоциативности ДЛК генерируется очень много. Я выложила тест для порции из 2 миллионов псевдоассоциативных ДЛК (ввела ограничение в программе генерации). XAVER тестирование выполнил. Смотрите об этом в указанной теме. Я решила этот генератор отставить в сторону; может быть, не навсегда. Пусть пока будет запасной алгоритм. Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
И теперь следует алгоритм PADLS TOTAL. Есть тема, посвящённая этому алгоритму https://boinc.progger.info/odlk/forum_thread.php?id=121 В этой теме всё довольно подробно рассказано. Не буду дублировать всё здесь. Главная суть: все ДЛК в линейках 15, 38 и 51 являются псевдоассоциативными ДЛК с разной степенью ассоциативности. Все мои генераторы выбирали из этого огромного множества малюсенькие подмножества. У ДЛК, производимых генератором 1, очень высокая степень ассоциативности. Отмечу, что именно в этих ветвях эксперимента (с генератором 1) получена основная масса групп пар ОДЛК выше двушки. В общем, проверили малюсенькие подмножества псевдоассоциативных ДЛК. Сняли сливки :) А теперь хотим проверить все псевдоассоциатвиные ДЛК в линейках 15, 38, 51. Я начала разработку с ветви PADLS TOTAL rule 51. Эта линейка выбрана по той простой причине, что в ней более высокое содержание КФ, нежели в линейках 15 и 38. Собственно, в этой версии эксперимента генератор писать не надо, он уже давно написан Белышевым. Это программа generator_kf. Мне принадлежит идея алгоритма. Идея в том, что мы должны сгенерировать все КФ в выбранной линейке и проверить их программой Белышева family_mar. Однако не так-то просто сгенерировать все КФ в линейке 51. Посмотрите тему https://boinc.progger.info/odlk/forum_thread.php?id=115 И даже справившись с генерацией всех КФ в линейке, не так-то просто их все проверить! Ведь КФ будет о-ч-е-н-ь много. В общем, эксперимент PADLS TOTAL может быть выполнен только в BOINC-проекте, для ручного проекта он неприемлем. К этой версии эксперимента присматривается Tomas Brada. Возможно, и присмотрится :) Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Господа! Я недаром ведь говорю, что у меня есть десятки экспериментов. К сожалению, у меня нет много помощников, у меня их пока всего два (Demis и XAVER). Пожалуйста, присмотритесь к моим алгоритмам. Может, что-то вас и заинтересует. Вы можете выполнить любой эксперимент на любой технике. Это может быть и новый BOINC-проект, как у Tomas Brada. Это может быть кластер или суперкомпьютер. Наконец, просто обычные компьютеры. Я считаю на очень простеньком ПК (2 ядра). Вот, например, сейчас только что отработал скрипт Это работает ветвь эксперимента - PADLS, генератор 4, rule 38. Об этой ветви рассказ будет дальше. Посмотрите на результаты; 11 марьяжных ДЛК на такую маленькую порцию ДЛК (51700) - это отличный результат! И обратите внимание на время проверки. Такая маленькая порция проверялась 3097 сек. Очень долго! Это притом, что сейчас работала одна эта программа. Обычно я запускаю до 4-х программ одновременно. Тогда скорость резко снижается. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Две новые ветви алгоритма PADLS описаны в теме "Принципиально новый алгоритм PADLS". Эти алгоритмы работают в линейках 16 и 39. Для каждой линейки написан свой генератор. Цитата из указанной темы
Этот ДЛК из линейки 39. Для этой линейки я протестировала три WUs, об этом рассказано в указанной теме. Результаты тестов хорошие. Линейка 39 хороша тем, что: а) в этой линейке высокое содержание КФ, в среднем соотношение КФ к СН ДЛК 1:2; б) линейка 39 ещё нигде не проверялась (в рамках всех наших проектов). Мне кажется, что это должен быть эффективный эксперимент. Дело покажет. К эксперименту PADLS rule 39 уже присматривается Demis. Надеюсь, что присмотрится :) Ко второй ветви - PADLS rule 16 - пока никто не присматривается. В этой ветви псевдоассоциатвиные ДЛК у меня получились похуже, в смысле степени ассоциативности. Но, может, это просто случайно так получилось. Покажу два псевдоассоциативных ДЛК из линейки 16 Я начала тестировать WU в линейке 16, но не закончила, отвлеклась на другой алгоритм. Потом вернусь и закончу. PS. Принципиальное отличие этих двух ветвей алгоритма от предыдущих версий в том, что в линейках 16 и 39 ассоциативность нарушается в побочной диагонали. Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Дополнение к ветви алгоритма PADLS rule 39... Цитата И ещё напомню: в этом эксперименте всего 3713 WUs, два из них я уже обработала при тестировании. Demis начал генерацию псевдоассоциативных ДЛК в этом эксперименте и обнаружил, что не для всех строк ДЛК генерируются. [При тестировании мной первых трёх строк это не обнаружилось.] Пришлось написать новую прогрммку фильтрации строк (специально для данного эксперимента). После фильтрации осталось всего 1589 строк (каждая строка это один WU). Однако псевдоассоциативных ДЛК в этом эксперименте генерируется довольно много: в среднем около миллиона для каждого WU. Точнее скажет Demis, у него уже завершается генерация ДЛК в этой ветви эксперимента. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Продолжаю рассказ о серии алгоритмов PADLS. Для меня это очень интересная серия. Думаю, что и для всех, кого интересует поиск ОДЛК, серия алгоритмов тоже интересна. Следующие три ветви алгоритма опять для линеек 15, 38, 51. Цитата Сейчас в эксперименте PADLS (ветви rule 15 и rule 51) работают два генератора - 1 и 2. Это из темы "Новая ветвь эксперимента PADLS" https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3588#3588 Итак, генератор 4. Особенность этого генератора в том, что он генерирует ДЛК для всех строк, фильтрация строк не нужна. Да, конечно, повторяемость решений будет, немудрено: в линейках 15, 38, 51 уже столько проверено ДЛК! Ну, каждое малюсенькое подмножество ДЛК будет пересекаться с другими малюсенькими подмножествами, что не критично. Главное, что все эти малюсенькие подмножества дают-таки новые решения! И ещё ценно то, что эти ветви эксперимента подъёмны для ручного проекта. Сейчас я выполняю ветвь эксперимента PADLS, генератор 4, rule 38. Отчёты в указанной теме. Дальше покажу иллюстрации для линейки 38 в данной версии эксперимента. PS. Совершенно понятно, что если будет выполнен, скажем, эксперимент PADLS TOTAL rule 51, то ветвь эксперимента с генератором 4 для линейки 51 можно не выполнять. Но... эксперимент PADLS TOTAL выполнить весьма затруднительно, без BOINC-проекта не обойтись. Генераторы 1, 2, 4 работают, как сепаратор. Знаете, что делает сепаратор? Снимает сливки :) |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Вот иллюстрации для линейки 38, псевдоассоциативные ДЛК, полученные генератором 4 Нарушения ассоциативности в коричневых ячейках. Как видите, степень ассоциативности в этих ДЛК довольно высокая; во втором ДЛК она даже максимальная - всего в 4-х ячейках нарушена ассоциативность. Для линеек 15 и 51 можно посмотреть иллюстрации в теме "Новая ветвь эксперимента PADLS". Для этих линеек я тоже немного тестировала эксперименты, уникальные решения есть. Ветвь эксперимента для линейки 38 содержит 6200 WUs. Я проверила 137 WUs. Пока всё отлично, уникальные решения стабильно идут. Уникальность решений проверяю относительно результатов, полученных и в первом эксперименте PADLS rule 38, и во втором его витке, выполненном в BOINC-проекте Tomas Brada. Для меня хорошо то, что ДЛК в этой ветви генерируется не очень много: до 300000 ДЛК. Хотя изредка встречаются и такие сюрпризы (это сейчас выполняется) . . . . . . . . C:\Users\Дом\Downloads\kanonizator_dlk (1)\ДВА_ГЕНЕРАТОРА>copy /b prov.txt+outpu t_sub_prov.txt prov.txt prov.txt output_SUB_prov.txt Скопировано файлов: 1. C:\Users\Дом\Downloads\kanonizator_dlk (1)\ДВА_ГЕНЕРАТОРА>copy output_sub_prov.t xt input.txt Скопировано файлов: 1. C:\Users\Дом\Downloads\kanonizator_dlk (1)\ДВА_ГЕНЕРАТОРА>family_mar.exe Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 585608 Не скоро у меня такая порция ДЛК проверяется. Надеюсь, до отбоя проверится :) Продолжение следует |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Уф! Наконец-то... вырулила C:\Users\Дом\Downloads\kanonizator_dlk (1)\ДВА_ГЕНЕРАТОРА>family_mar.exe Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК Введено ЛК: 585608 Найдено марьяжных ДЛК: 73 они записаны в файл output.txt Время работы в сек : 29761.6 73 марьяжных ДЛК найдено! Класс! Обрабатывать завтра буду, то есть уже сегодня :) |
Send message Joined: 11 Jul 17 Posts: 174 Credit: 4,965,085 RAC: 5 |
Сложно назвать среднее значение по числу квадратов. Это примерно от 600тыс. до 1,7 миллиона. Вот примерная статистика по квадратам: file: input-new-1.txt squares:651701 file: input-new-2.txt squares:830436 file: input-new-3.txt squares:1189493 file: input-new-4.txt squares:1264764 file: input-new-5.txt squares:579895 file: input-new-6.txt squares:930262 file: input-new-7.txt squares:1207297 file: input-new-8.txt squares:1036392 file: input-new-9.txt squares:1698360 file: input-new-10.txt squares:1754952 file: input-new-11.txt squares:1143846 file: input-new-12.txt squares:977826 file: input-new-13.txt squares:1072201 file: input-new-14.txt squares:1591221 file: input-new-15.txt squares:931694 file: input-new-16.txt squares:1485516 file: input-new-17.txt squares:562534 file: input-new-18.txt squares:1044445 file: input-new-19.txt squares:667753 file: input-new-20.txt squares:680483 file: input-new-21.txt squares:651788 file: input-new-22.txt squares:809912 file: input-new-23.txt squares:803243 file: input-new-24.txt squares:818918 file: input-new-25.txt squares:864760 file: input-new-26.txt squares:1081520 file: input-new-27.txt squares:954837 file: input-new-28.txt squares:825545 file: input-new-29.txt squares:796652 file: input-new-30.txt squares:1575154 file: input-new-31.txt squares:1256312 file: input-new-32.txt squares:891803 file: input-new-33.txt squares:1493907 file: input-new-34.txt squares:752610 file: input-new-35.txt squares:1263281 file: input-new-36.txt squares:790866 file: input-new-37.txt squares:701777 file: input-new-38.txt squares:559205 file: input-new-39.txt squares:740003 file: input-new-40.txt squares:1174138 file: input-new-41.txt squares:706533 file: input-new-42.txt squares:865782 file: input-new-43.txt squares:955310 file: input-new-44.txt squares:1147591 |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Demis спасибо. Интересная статистика. Итак, 1589 файлов с ДЛК у вас уже готовы. Здорово! Осталась проверка. Ждём завершения ветви PADLS rule 15. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Продолжаю рассказ о серии алгоритмов PADLS. Цитата А у меня уже готова новая модификация генератора для линейки №15. Да, будем покорять отдельные ветви. Как жаль, что почти нет тех, кто хочет покорять :( И снова линейка 15! Это уже генератор 5. Этот генератор работает для всех строк, фильтрация строк не нужна. Но лучше всё-таки выполнить этот эксперимент для тех строк, которые не проверялись генераторами 1 и 2, потому что для проверенных строк вероятность повторения решений будет высокая, хотя и нельзя утверждать, что будут повторены все решения. В линейке 15 всего строк 6164, генераторами 1 и 2 проверно 3388 строк, следовательно, остаётся проверить генератором 5 2776 строк. Отличная порция WUs. Сейчас я тестирую один WU. И ... увязла с ним, потому что ДЛК всё генерируются и генерируются! Уже проверила 3 миллиона ДЛК, сгенерировала сейчас следующую порцию 300000 ДЛК, а всё не конец генерации. Весьма интересный случай. Не думаю, что это просто случайность для одного конкретного WU. И решения уникальные идут!! Вот такая веточка занимательная :) ну как её не покорить?! А посмотрите на иллюстрацию, какие красивые псевдоассоциативные ДЛК получены генераторм 5! Просто прелесть. Увидеть красоту! Создать красоту! |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Ещё одна иллюстрация в этом эксперименте (генератор 5, линейка 15) Здесь показаны псевдоассоциативный СН ДЛК и его КФ. Цитата Интересный момент: при переходе от СН ДЛК к КФ степень ассоциативности не изменилась. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Кстати, надо подумать над определением степени ассоциативности псевдоассоциативного ДЛК. Наверное, всё-таки надо определить так: степень ассоциативности псевдоассоциативного ДЛК - отношение количества ячеек, в которых есть ассоциативность, к общему количеству ячеек ДЛК. Пример 1 в ДЛК нарушение ассоциативности в 4-х ячейках. В этом случае степень ассоциативности равна 0,96. Это максимальная степень ассоциативности для ДЛК 10-го порядка. Пример 2 на приведённой в предыдущем посте иллюстрации в ДЛК ассоциативность нарушена в 28 ячейках, в 72 ячейках ассоциативность имеется. Для этого ДЛК степень ассоциативности равна 0,72. Думаю, что это корректное определение степени ассоциативности псевдоассоциативного ДЛК. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Идеи у меня не закончились. Есть ещё как минимум две. Вот закончу с тестированием одного WU в экспериментах PADLS, генератор 5, rule 15 и PADLS rule 16, тогда попробую реализовать новые идеи. Так что, продолжение следует... А пока у нас в работе три ветви эксперимента PADLS 1. PADLS rule 15 2. PADLS rule 51 3. PADLS, генератор 4, rule 38 Demis уже начал принципиально новую ветвь эксперимента - PADLS rule 39. Эксперимент PADLS rule 15 он заканчивает, осталось совсем чуть-чуть. Эксперимент PADLS rule 51 у XAVER идёт хорошо, больше четверти WUs обработано. Ну, а у меня всё в самом начале, эксперимент PADLS, генератор 4, rule 38. Я не тороплюсь :) Как поётся в моём любимом романсе - Мне некуда больше спешить... Ямщик, не гони лошадей! PS. Возможно, Tomas Brada запустит в своём BOINC-проекте ветвь эксперимента PADLS TOTAL rule 51. Это было бы здорово! |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Цитата А у меня уже готова новая модификация генератора для линейки №15. Эта ветвь эксперимента тестируется для одного WU. Случай удивительный: уже сгенерировано больше 4 миллионов псевдоассоциативных ДЛК и до конца генерации ещё далеко. Покажу иллюстрации к этой ветви эксперимента (две иллюстрации показаны выше) Красота! Верхний ДЛК на второй иллюстрации дьявольски красив! Отчёты о тестировании в теме "Новая ветвь эксперимента PADLS" В эксперименте уже найдено 79 уникальных КФ ОДЛК. И это от одного WU, и ещё, возможно, не всё. И это в линейке №15, в которой уже очень хорошо поработали генераторы 1 и 2. |
Send message Joined: 6 Apr 17 Posts: 14536 Credit: 0 RAC: 0 |
Вот этот красивый квадратик надо запомнить! Это из ветви PADLS, генератор 5, rule 15. |
©2025 (C) Progger