О серии алгоритмов PADLS

Message boards : Science : О серии алгоритмов PADLS
Message board moderation

To post messages, you must log in.

1 · 2 · Next

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3788 - Posted: 2 Jun 2019, 4:40:50 UTC
Last modified: 3 Jun 2019, 15:34:42 UTC

Поскольку ветвей алгоритма PADLS стало много, надо их все собрать в одном месте с подробным описанием.
Аббревиатура PADLS означает: псевдоассоциативные ДЛК в английском написании -
Pseudo-Associative Diagonal Latin Squares.

Разработка алгоритма PADLS начиналась мной в теме "Ассоциативные ДЛК" в декабре 2017 г.
Цитирую сообщение от 24 декабря 2017 г. из этой темы

Решила "отпустить" последнюю пару строк, то есть не выполнять в этих строках требование ассоциативности.
Так программа выдала решения, много. Вот самое первое



Встречайте - псевдоассоциативный ДЛК 10-го порядка.
Вот, значит, как: конфликт возник в 4-х ячейках (они выделены красным цветом) и элементы в этих ячейках расположились не центрально-симметрично, а вертикально-симметрично. А всё остальное в полном соответствии с ассоциативностью.

отсюда
https://boinc.progger.info/odlk/forum_thread.php?id=51&postid=1247#1247

Вот с этого момента и начался алгоритм PADLS.
Первая программа, которую я написала для получения псевдоассоциативных ДЛК, - это генератор 1.

Как известно, ассоциативных ДЛК 10-го порядка не существует.
Вместе с тем известно, что ассоциативные ДЛК 9-го порядка дают очень много ортогональных ДЛК.
Вот из этих двух известных фактов и появилась идея поискать ОДЛК для псевдоассоциативных ДЛК 10-го порядка. Идея оказалась весьма эффективной.

Продолжение следует
ID: 3788 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3789 - Posted: 2 Jun 2019, 4:56:01 UTC
Last modified: 3 Jun 2019, 15:37:01 UTC

В линейках 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. Конечно, у него выполнение экспериментов пошло намного быстрее.
Я тоже продолжала эксперимент.
Тут есть важный момент: мы пропускали довольно большие множества исходных строк, так как шли сплошные повторы решений.
Но мало ли что мы могли пропустить!
Эти три ветви были завершены, но вот с такими белыми пятнами.
Решений эти ветви эксперимента дали очень много, в том числе - много солидных групп пар ОДЛК.

Продолжение следует
ID: 3789 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3790 - Posted: 2 Jun 2019, 5:57:37 UTC
Last modified: 2 Jun 2019, 6:04:13 UTC

И ещё одно обстоятельство было замечено при первом выполнении трёх ветвей эксперимента PADLS: не для всех исходных строк генерировались псевдоассоциативные ДЛК.
Так например, из 6164 строк линейки 15 только 3388 строк давали ДЛК.
Это обстоятельство было учтено при усовершенствовании алгоритма. Я написала программку фильтрации строк.
Ну и главное усовершенствование состояло в добавлении нового генератора псевдоассоциативных ДЛК - генератора 2.
Генератор 1 генерировал ДЛК с нарушением ассоциативности в двух центральных строках.
Генератор 2 генерировал ДЛК с нарушением ассоциативности в четырёх центральных строках.
Цитата

Показываю примеры псевдоассоциативных ДЛК в данной ветви эксперимента, произведённых генераторами 1 и 2 в одном и том же WU (для одной и той же строки)



Нарушения ассоциативности в белых ячейках.

PS. Как я уже отмечала ранее, множество ДЛК, полученное генератором 1, не включается полностью во множество ДЛК, полученное генератором 2 (для одной и той же строки), хотя пересечение есть.
С этими двумя множествами прекрасно справляется программа Белышева kanonizator_dlk_1.03, она канонизирует все ДЛК и удаляет дубликаты КФ.

отсюда
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

Продолжение следует
ID: 3790 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3796 - Posted: 2 Jun 2019, 11:24:44 UTC
Last modified: 2 Jun 2019, 11:38:04 UTC

Ещё были у меня эксперименты с вариантами побочных диагоналей.
Таких ветвей было несколько, я выполняла эти эксперименты сама.
Но была одна ветвь, выполненная в 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. Сейчас он завершает этот эксперимент.

Продолжение следует
ID: 3796 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3799 - Posted: 2 Jun 2019, 14:21:38 UTC
Last modified: 2 Jun 2019, 16:46:41 UTC

Далее я написала генератор 3.
Смотрите тему
https://boinc.progger.info/odlk/forum_thread.php?id=105

Этот генератор можно применять для генерирования псевдоассоциативных ДЛК в линейках 15, 38, 51, а также для вариантов побочной диагонали (полностью ассоциативной).
На иллюстрации показан псевдоассоциативный ДЛК с вариантом побочной диагонали, полученный генератором 3



Нарушения ассоциативности в ДЛК, производимых данным генератором, в 6 центральных строках.
Из-за низкой степени ассоциативности ДЛК генерируется очень много.
Я выложила тест для порции из 2 миллионов псевдоассоциативных ДЛК (ввела ограничение в программе генерации).
XAVER тестирование выполнил.
Смотрите об этом в указанной теме.

Я решила этот генератор отставить в сторону; может быть, не навсегда.
Пусть пока будет запасной алгоритм.

Продолжение следует
ID: 3799 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3801 - Posted: 2 Jun 2019, 17:18:18 UTC
Last modified: 2 Jun 2019, 17:28:31 UTC

И теперь следует алгоритм 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.
Возможно, и присмотрится :)

Продолжение следует
ID: 3801 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3802 - Posted: 2 Jun 2019, 17:33:25 UTC
Last modified: 2 Jun 2019, 17:53:38 UTC

Господа!

Я недаром ведь говорю, что у меня есть десятки экспериментов.
К сожалению, у меня нет много помощников, у меня их пока всего два (Demis и XAVER).

Пожалуйста, присмотритесь к моим алгоритмам.
Может, что-то вас и заинтересует.

Вы можете выполнить любой эксперимент на любой технике.
Это может быть и новый BOINC-проект, как у Tomas Brada.
Это может быть кластер или суперкомпьютер.
Наконец, просто обычные компьютеры.
Я считаю на очень простеньком ПК (2 ядра).
Вот, например, сейчас только что отработал скрипт



Это работает ветвь эксперимента - PADLS, генератор 4, rule 38.
Об этой ветви рассказ будет дальше.
Посмотрите на результаты; 11 марьяжных ДЛК на такую маленькую порцию ДЛК (51700) - это отличный результат!
И обратите внимание на время проверки. Такая маленькая порция проверялась 3097 сек. Очень долго! Это притом, что сейчас работала одна эта программа. Обычно я запускаю до 4-х программ одновременно.
Тогда скорость резко снижается.
ID: 3802 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3803 - Posted: 3 Jun 2019, 5:09:20 UTC
Last modified: 3 Jun 2019, 6:28:44 UTC

Две новые ветви алгоритма PADLS описаны в теме "Принципиально новый алгоритм PADLS".
Эти алгоритмы работают в линейках 16 и 39.
Для каждой линейки написан свой генератор.

Цитата из указанной темы



Это первый (из 830436) псевдоассоциативный ДЛК, полученный генератором от второго WU.
Второму WU соответствует строка
2 3 4 5 7 9 8 6

Этот ДЛК из линейки 39.
Для этой линейки я протестировала три WUs, об этом рассказано в указанной теме.
Результаты тестов хорошие.
Линейка 39 хороша тем, что:
а) в этой линейке высокое содержание КФ, в среднем соотношение КФ к СН ДЛК 1:2;
б) линейка 39 ещё нигде не проверялась (в рамках всех наших проектов).
Мне кажется, что это должен быть эффективный эксперимент.
Дело покажет.
К эксперименту PADLS rule 39 уже присматривается Demis.
Надеюсь, что присмотрится :)
Ко второй ветви - PADLS rule 16 - пока никто не присматривается.
В этой ветви псевдоассоциатвиные ДЛК у меня получились похуже, в смысле степени ассоциативности.
Но, может, это просто случайно так получилось.
Покажу два псевдоассоциативных ДЛК из линейки 16



Я начала тестировать WU в линейке 16, но не закончила, отвлеклась на другой алгоритм. Потом вернусь и закончу.

PS. Принципиальное отличие этих двух ветвей алгоритма от предыдущих версий в том, что в линейках 16 и 39 ассоциативность нарушается в побочной диагонали.

Продолжение следует
ID: 3803 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3804 - Posted: 3 Jun 2019, 5:58:34 UTC
Last modified: 3 Jun 2019, 15:56:33 UTC

Дополнение к ветви алгоритма PADLS rule 39...

Цитата
И ещё напомню: в этом эксперименте всего 3713 WUs, два из них я уже обработала при тестировании.
То есть эксперимент вполне реально выполнить в ручном проекте.
Ну, конечно, помощнее моего ПК нужна техника.

Demis начал генерацию псевдоассоциативных ДЛК в этом эксперименте и обнаружил, что не для всех строк ДЛК генерируются.
[При тестировании мной первых трёх строк это не обнаружилось.]
Пришлось написать новую прогрммку фильтрации строк (специально для данного эксперимента).
После фильтрации осталось всего 1589 строк (каждая строка это один WU).
Однако псевдоассоциативных ДЛК в этом эксперименте генерируется довольно много: в среднем около миллиона для каждого WU.
Точнее скажет Demis, у него уже завершается генерация ДЛК в этой ветви эксперимента.
ID: 3804 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3807 - Posted: 3 Jun 2019, 16:49:18 UTC
Last modified: 3 Jun 2019, 17:31:16 UTC

Продолжаю рассказ о серии алгоритмов PADLS. Для меня это очень интересная серия.
Думаю, что и для всех, кого интересует поиск ОДЛК, серия алгоритмов тоже интересна.

Следующие три ветви алгоритма опять для линеек 15, 38, 51.
Цитата

Сейчас в эксперименте PADLS (ветви rule 15 и rule 51) работают два генератора - 1 и 2.
О генераторе 3 я уже писала, решила его отставить.

Написала ещё один генератор - четвёртый.
Этот генератор, как и генераторы 1, 2, применим к линейкам 15, 38, 51.
У него есть принципиальное отличие от генераторов 1, 2.
Плохо то, что множества псевдоассоциативных ДЛК от генератора 4 включают некоторые псевдоассоциативные ДЛК от генераторов 1, 2.
Пересечения есть, но, как мне кажется, полного совпадения не должно быть.
Псевдоассоциативные ДЛК от генератора 4 с высокой степенью ассоциативности.

Будут ли новые оригинальные решения от этого генератора, сказать сразу не могу, надо экспериментировать.

Это из темы "Новая ветвь эксперимента 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 работают, как сепаратор.
Знаете, что делает сепаратор? Снимает сливки :)
ID: 3807 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3808 - Posted: 3 Jun 2019, 17:08:12 UTC
Last modified: 3 Jun 2019, 17:14:23 UTC

Вот иллюстрации для линейки 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

Не скоро у меня такая порция ДЛК проверяется. Надеюсь, до отбоя проверится :)

Продолжение следует
ID: 3808 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3809 - Posted: 3 Jun 2019, 20:48:46 UTC - in response to Message 3808.  
Last modified: 3 Jun 2019, 20:49:17 UTC

Уф!
Наконец-то... вырулила

C:\Users\Дом\Downloads\kanonizator_dlk (1)\ДВА_ГЕНЕРАТОРА>family_mar.exe
Поиск марьяжных ДЛК (кроме симметричных) для семейства ЛК

Введено ЛК: 585608

Найдено марьяжных ДЛК: 73 они записаны в файл output.txt
Время работы в сек   : 29761.6

73 марьяжных ДЛК найдено! Класс!
Обрабатывать завтра буду, то есть уже сегодня :)
ID: 3809 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Demis

Send message
Joined: 11 Jul 17
Posts: 98
Credit: 3,036,219
RAC: 0
Message 3811 - Posted: 4 Jun 2019, 7:12:44 UTC - in response to Message 3804.  

Сложно назвать среднее значение по числу квадратов.
Это примерно от 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
ID: 3811 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3812 - Posted: 4 Jun 2019, 8:02:13 UTC - in response to Message 3811.  

Demis
спасибо.
Интересная статистика.
Итак, 1589 файлов с ДЛК у вас уже готовы. Здорово!
Осталась проверка.
Ждём завершения ветви PADLS rule 15.
ID: 3812 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3815 - Posted: 4 Jun 2019, 17:04:48 UTC
Last modified: 4 Jun 2019, 17:19:59 UTC

Продолжаю рассказ о серии алгоритмов PADLS.

Цитата

А у меня уже готова новая модификация генератора для линейки №15.
Генератор даёт оригинальные псевдоассоциативные ДЛК!
Ни генератором 1, ни генератором 2 такие ДЛК не могут быть получены.



Красота!
Уже начала тестировать, и есть уникальные решения.
[Показанные на иллюстрации псевдоассоциативные ДЛК созданы для строки
7 5 8 6 9 2 4 3

Нарушения ассоциативности в белых ячейках. Степень ассоциативности довольно высокая.]

Я уже не раз отмечала, что и генератор 1, и генератор 2, и новый генератор дают решения, которые обязательно будут найдены в эксперименте PADLS TOTAL rule 15.
Но! Эта ветвь эксперимента ещё даже не стоит в ближайших планах (в ближайших планах ветвь PADLS TOTAL rule 51, это если Tomas Brada не передумает запускать эксперимент в его BOINC-проекте).
А поэтому, а поэтому... предлагаются небольшие ветви эксперимента, приемлемые для ручного проекта.
PADLS TOTAL - это огромное дерево, будем покорять отдельные небольшие ветви.

Да, будем покорять отдельные ветви.
Как жаль, что почти нет тех, кто хочет покорять :(

И снова линейка 15! Это уже генератор 5.
Этот генератор работает для всех строк, фильтрация строк не нужна.
Но лучше всё-таки выполнить этот эксперимент для тех строк, которые не проверялись генераторами 1 и 2, потому что для проверенных строк вероятность повторения решений будет высокая, хотя и нельзя утверждать, что будут повторены все решения.
В линейке 15 всего строк 6164, генераторами 1 и 2 проверно 3388 строк, следовательно, остаётся проверить генератором 5 2776 строк.
Отличная порция WUs.

Сейчас я тестирую один WU. И ... увязла с ним, потому что ДЛК всё генерируются и генерируются!
Уже проверила 3 миллиона ДЛК, сгенерировала сейчас следующую порцию 300000 ДЛК, а всё не конец генерации.
Весьма интересный случай. Не думаю, что это просто случайность для одного конкретного WU.
И решения уникальные идут!!
Вот такая веточка занимательная :) ну как её не покорить?!

А посмотрите на иллюстрацию, какие красивые псевдоассоциативные ДЛК получены генераторм 5! Просто прелесть.
Увидеть красоту! Создать красоту!
ID: 3815 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3816 - Posted: 4 Jun 2019, 17:47:44 UTC
Last modified: 4 Jun 2019, 18:18:47 UTC

Ещё одна иллюстрация в этом эксперименте (генератор 5, линейка 15)



Здесь показаны псевдоассоциативный СН ДЛК и его КФ.

Цитата
Интересный момент: при переходе от СН ДЛК к КФ степень ассоциативности не изменилась.
[Понятно, что степень ассоциативности определяется количеством ячеек с нарушением ассоциативности, или, если точнее, соотношением количества ячеек с нарушением ассоциативности к количеству ячеек, в которых ассоциативность имеет место.]
ID: 3816 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3817 - Posted: 4 Jun 2019, 17:59:11 UTC
Last modified: 5 Jun 2019, 4:08:18 UTC

Кстати, надо подумать над определением степени ассоциативности псевдоассоциативного ДЛК.
Наверное, всё-таки надо определить так:
степень ассоциативности псевдоассоциативного ДЛК - отношение количества ячеек, в которых есть ассоциативность, к общему количеству ячеек ДЛК.

Пример 1
в ДЛК нарушение ассоциативности в 4-х ячейках.
В этом случае степень ассоциативности равна 0,96. Это максимальная степень ассоциативности для ДЛК 10-го порядка.



Пример 2
на приведённой в предыдущем посте иллюстрации в ДЛК ассоциативность нарушена в 28 ячейках, в 72 ячейках ассоциативность имеется.
Для этого ДЛК степень ассоциативности равна 0,72.

Думаю, что это корректное определение степени ассоциативности псевдоассоциативного ДЛК.
ID: 3817 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3819 - Posted: 5 Jun 2019, 3:49:04 UTC
Last modified: 5 Jun 2019, 4:01:19 UTC

Идеи у меня не закончились. Есть ещё как минимум две.
Вот закончу с тестированием одного 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.
Это было бы здорово!
ID: 3819 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3847 - Posted: 7 Jun 2019, 16:20:47 UTC
Last modified: 8 Jun 2019, 1:37:17 UTC

Цитата
А у меня уже готова новая модификация генератора для линейки №15.
Генератор даёт оригинальные псевдоассоциативные ДЛК!
Ни генератором 1, ни генератором 2 такие ДЛК не могут быть получены.

Эта ветвь эксперимента тестируется для одного WU.
Случай удивительный: уже сгенерировано больше 4 миллионов псевдоассоциативных ДЛК и до конца генерации ещё далеко.

Покажу иллюстрации к этой ветви эксперимента (две иллюстрации показаны выше)





Красота! Верхний ДЛК на второй иллюстрации дьявольски красив!

Отчёты о тестировании в теме "Новая ветвь эксперимента PADLS"
В эксперименте уже найдено 79 уникальных КФ ОДЛК. И это от одного WU, и ещё, возможно, не всё.
И это в линейке №15, в которой уже очень хорошо поработали генераторы 1 и 2.
ID: 3847 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 4652
Credit: 0
RAC: 0
Message 3910 - Posted: 15 Jun 2019, 18:35:11 UTC

Вот этот красивый квадратик надо запомнить!



Это из ветви PADLS, генератор 5, rule 15.
ID: 3910 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · Next

Message boards : Science : О серии алгоритмов PADLS


©2020 (C) Progger