Message boards :
Science :
Алгоритм PADLS TOTAL
Message board moderation
Previous · 1 · 2 · 3 · Next
Author | Message |
---|---|
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Are all CF DLS generated by generator_lk in lines 15, 38 and 51 pseudo associative? Все СН ДЛК и все КФ СН ДЛК в линейках 15, 38 и 51 являются псевдоассоциативными, с разной степенью ассоциативности. Is generator_lk THE generator for padls total? Генератором для эксперимента PADLS TOTAL является генератор Белышева generator_kf. Why you want to use family_mar instead of the faster orthogonality test? Ах! Вы же сами ответили на этот вопрос :) The family_mar program is more complex than checking whether a DLS is a ODLS. Checking that only requires enumerating the transversals and checking for a disjoint set thereof. Family_mar generates a whole family from that DLS and check them instead. So it is checking about 300 DLS instead of one DLS for othogonality. https://boinc.progger.info/odlk/forum_thread.php?id=117&postid=3554#3554 Мой ответ здесь https://boinc.progger.info/odlk/forum_thread.php?id=121&postid=3636#3636 |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
Hurra! Now I understand this. Then we must check that all the daughter squares that family_mar is checking are in ruler 15, 51 or 38 and that they do not repeat too much. BUT in padls total, all kf from these rows will be checked, so if the daughter square also belongs in the rulers, then it is not necessary to check them, because such will be checked later. And if the daughter square does not belong to the rulers, then they do not belong to the experiment. From this thought, it seems the family_mar program is not needed here. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Then we must check that all the daughter squares that family_mar is checking are in ruler 15, 51 or 38 and that they do not repeat too much. BUT in padls total, all kf from these rows will be checked, so if the daughter square also belongs in the rulers, then it is not necessary to check them, because such will be checked later. And if the daughter square does not belong to the rulers, then they do not belong to the experiment. Я ничего не поняла тут. Мы берём линейку №51 и генерируем в этой линейке КФ СН ДЛК. Все эти КФ являются псевдоассоциативными ДЛК и все они различные. Если мы применим к этим КФ только поиск ортогональных им ДЛК (что, кстати, делается в проекте ODLK), мы найдём тысячную долю решений (примерно). Проверка должна выполняться программой family_mar! Я уже тестирую этот эксперимент и получаю уникальные решения от тех КФ линейки №51, которые не имеют ортогональных ДЛК. Пожалуйста, прочтите ещё раз внимательно эту ветку, а также ветку "Задача". Мне приходится разъяснять одно и то же несколько раз. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
By reading the Family_mar program, I understand it works as follows: From each input LS, many more squares are derived. Let's call those daughter squares. And then, each daughter square is checked for orthogonality. The program works so fast, because a expensive step of transversal enumeration is performed only once for each input square and is shared for all the daughter squares. There are average of 300 daughter squares per input square. I do not yet understand how these are generated. Do you understand? Now what these daughter squares look like? I picked a bad example, because it has 509 daughter squares. I only show some. The example square has 868 trasversals, of which 131 are "diagonal". Input Square: MFU8P9W4nERBJRxCqKoiBbzmz #lin=39 (line №39) Daughter squares: 7TBNWSbTrQcULyGBq3KkYgEYV #lin=12 GsByHUmwv4qZ1u1PUNeXjwxvu #lin=30 MQ8aQpTyGSVs1JhSoGZVfschW #lin=39 ACHesZJxXJvnsXCrM4U98KzUC #lin=17 XdRoZYnGhJg7Y2Sq787xHNNof #lin=59 7ekgqDzZjGd9yCcvv39RJXjHg #lin=12 BzeVDKEbDGihTmcGHRbrT9kmv #lin=21 SbK5grSkSDtie77Mj11HHTcw9 #lin=49 FhEBGcVuL19ZMbA9dQMRqBi3q #lin=28 NHyQ5Zjn972k9zgDy26NoeCGF #lin=41 . . . MFU8P9W4nERBJRxCqKoiBbzmz #lin=39 1HgEzStK3DU6M3E5RAgpYTPFx #lin=0 8Q7a3F4iGJNjyvDkwBAZzPxRX #lin=14 8Q7a3EzDZJNjyv36FBAa9NiU1 #lin=14 Tu9z184RgCnfNcq2pS5fEhbxS #lin=52 2JnoY54D8LJSLjJn3AwyLoAkT #lin=2 CBn5b8jKg66isELKhCSZ4LcGv #lin=21 3zKxLwgGk2NyYq9n7CoEpU6WV #lin=5 . . . See - a lot of different line numbers. 13 of them are from line number 39, others are from bunch of other lines. These 13 (12 without original) will become duplicate, as they will be checked in other workunits. What about the other lines? Can they be orthogonal? Should they be checked? Should the be part of the results (if orthogonal)? |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Из какой линейки вы взяли исходную КФ СН ДЛК для проверки программой family_mar? Что у вас означает lin=39, lin=21 и т. д.? Я понимаю, как работает программа family_mar только в общей идее, но не в деталях. За разъяснением деталей работы этой программы, пожалуйста, обратитесь к автору программы. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Input Square: Вы хотите сказать, что исходный квадрат из линейки №39? Этот квадрат: MFU8P9W4nERBJRxCqKoiBbzmz 0 2 3 7 8 9 5 6 4 1 3 1 8 5 0 7 9 4 2 6 8 5 2 6 3 1 7 0 9 4 2 7 1 3 9 8 4 5 6 0 1 8 0 9 4 6 3 2 5 7 6 9 4 0 7 5 2 8 1 3 7 0 5 8 1 4 6 9 3 2 4 6 9 2 5 3 1 7 0 8 9 3 7 4 6 2 0 1 8 5 5 4 6 1 2 0 8 3 7 9 не принадлежит линейке №39. В линейке №39 побочная диагональ СН ДЛК имеет вид 1 2 0 4 6 3 7 9 5 8 |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
It seems I made a mistake with the rule number. Is this rule 1,0,3,2,6,7,4,5,9,8 - number 0 or number 1? |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Побочные диагонали линеек по теории Белышева №1 1032674598 №2 1032674895 №3 1032675498 №4 1032678945 №5 1032678954 №6 1032684957 №7 1032684975 №8 1032685947 №9 1032685974 №10 1032687495 №11 1032689475 №12 1032689574 №13 1034268957 №14 1034268975 №15 1034275698 №16 1034275896 №17 1034278956 №18 1034278965 №19 1034625897 №20 1034628597 №21 1034628957 №22 1034682975 №23 1034685927 №24 1034687925 №25 1034687952 №26 1034728956 №27 1034728965 №28 1034785926 №29 1034785962 №30 1034875926 №31 1034875962 №32 1034895627 №33 1034895672 №34 1037685924 №35 1037685942 №36 1037892645 №37 1037892654 №38 1204635978 №39 1204637958 №40 1204678935 №41 1204785936 №42 1204785963 №43 1204789365 №44 1204789563 №45 1204798536 №46 1204798653 №47 1230678954 №48 1230679458 №49 1234075968 №50 1234078956 №51 1234095678 №52 1234608975 №53 1234675908 №54 1234689507 №55 1237685904 №56 1237695408 №57 1032675894 №58 1034628975 №59 1034678925 №60 1034678952 №61 1034685972 №62 1034689527 №63 1034689572 №64 1034869527 №65 1204678953 №66 1230675948 №67 1234698057 А знаете ли вы, почему линеек 67? :) Белышев сделал гениальное открытие линеек в 2017 году; было мне в ту пору 67 лет :) Разумеется, это шутка. Просто совпадение такое. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
So it is that my program reports rule number one less. I correct the program. In my message (2672), the lin means rule number. In the code from Белышев, it is called "lin", but it is one less. So #lin=39 is rule №40. Silly mistake. But this fact does not change the idea. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Tomas Brada неважно, что вы ошиблись в нумерации линеек. Ну вот, программа family_mar нашла много ДЛК, разумеется, они из каких-то линеек. И что из этого? Все эти ДЛК должны быть проверены на наличие у них ОДЛК; проверены сейчас, а не тогда, когда будут проверяться соответствующие линейки. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
But this fact does not change the idea. Да, я вам уже ответила. В этом факте нет никакой идеи. Идея в том, что эти ДЛК из разных линеек нужно проверить сейчас на ОДЛК и найти все решения. Линейка №21 (и другие линейки), может быть, будет проверяться через 10 лет. Я могу не успеть :) Например, найденные мной уникальные решения при тестировании эксперимента PADLS TOTAL rule 51 0 4 5 9 3 2 7 8 6 1 4 1 6 0 8 3 5 9 2 7 5 7 2 1 0 8 9 3 4 6 6 8 7 3 2 9 4 1 0 5 1 3 9 7 4 6 8 2 5 0 8 0 1 4 9 5 2 6 7 3 2 9 3 8 7 0 6 5 1 4 3 2 0 5 6 4 1 7 9 8 9 5 4 6 1 7 3 0 8 2 7 6 8 2 5 1 0 4 3 9 0 4 6 7 2 9 8 5 3 1 6 1 7 8 3 4 0 9 2 5 8 5 2 9 0 1 4 3 7 6 5 2 4 3 1 8 7 6 9 0 7 9 5 1 4 6 2 8 0 3 3 7 0 4 8 5 9 1 6 2 9 8 3 5 7 2 6 0 1 4 1 6 9 2 5 0 3 7 4 8 2 0 1 6 9 3 5 4 8 7 4 3 8 0 6 7 1 2 5 9 0 2 4 8 9 3 7 6 5 1 4 1 7 5 0 6 8 9 2 3 8 7 2 4 3 1 5 0 9 6 1 8 9 3 6 2 4 5 7 0 2 9 0 6 4 7 1 8 3 5 7 4 6 0 8 5 9 3 1 2 5 3 1 9 7 8 6 2 0 4 6 0 5 1 2 9 3 7 4 8 9 6 3 2 5 4 0 1 8 7 3 5 8 7 1 0 2 4 6 9 0 5 3 2 9 7 8 4 6 1 7 1 8 4 5 9 2 6 0 3 5 9 2 8 1 0 4 3 7 6 9 8 6 3 2 1 7 0 5 4 8 7 1 0 4 6 3 5 9 2 3 2 7 6 8 5 9 1 4 0 1 0 4 5 7 2 6 9 3 8 4 6 9 1 3 8 0 7 2 5 6 4 5 9 0 3 1 2 8 7 2 3 0 7 6 4 5 8 1 9 0 6 7 8 3 9 5 2 4 1 3 1 5 7 0 8 9 4 2 6 4 9 2 1 5 0 7 3 6 8 2 5 8 3 1 4 0 6 9 7 1 0 3 9 4 6 8 5 7 2 9 3 6 4 7 5 2 8 1 0 7 2 4 5 8 1 6 9 0 3 5 8 9 0 6 2 1 7 3 4 6 4 0 2 9 7 3 1 8 5 8 7 1 6 2 3 4 0 5 9 Все они из каких-то линеек. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
Great! Now I have answer to my question. > What about the other rules? Can they be orthogonal? Should they be checked? Should the be part of the results (if orthogonal)? Yes, we also include the other lines. This is very interesting. Still the rule numbers of daughter squares can be used to eliminate some double checking. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Still the rule numbers of daughter squares can be used to eliminate some double checking. Если вас так пугает "двойная проверка", не надо ничего проверять :) Установление номеров линеек всех ДЛК (получаемых в процессе работы программы family_mar) и выяснение вопроса, были ли эти ДЛК уже проверены раньше, займёт больше времени, чем их "двойная проверка". Сейчас выполняются эксперименты PADLS rule 15 и PADLS rule 51, в которых очень много повторных проверок. Но мы получаем также уникальные решения за счёт нового генератора 2. Я выполняю эксперимент PADLS генератор 4, rule 38, в котором тоже много повторных проверок. Но я получаю и уникальные решения! Эти решения не были получены ни при первом выполнении эксперимента PADLS rule 38 мной и Demis в ручном режиме, ни при втором выполнении этого эксперимента в вашем BOINC-проекте. Я показала примеры таких решений https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3631#3631 Предлагаю вам разработать свой алгоритм, в котором совсем не будет "двойных проверок" и запустить его в BOINC-проекте. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
Yes, I know that checking for duplicate work is work in itself. Such check must be fast, otherwiese it is not worth it. The rule numbers are already calculated as a byproduct in the program! We will see. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
The rule numbers are already calculated as a byproduct in the program Хорошо, допустим, что номера линеек в программе family_mar уже определены. Но как вы установите по всем линейкам, были ли проверены данные ДЛК из этих линеек? Вероятность того, что они были проверены, ничтожно мала. Линейки содержат огромное количество СН ДЛК и КФ СН ДЛК! Такая проверка потребует немало времени. Гораздо быстрее сразу проверить все ДЛК на ОДЛК. Это моё мнение. Желаю вам удачи в вашем алгоритме без "двойных проверок". Я предпочитаю свой вариант алгоритма. В алгоритме PADLS TOTAL работают всего две программы Белышева: generator_kf и family_mar. Обе программы многократно опробованы и работают отлично. Я ничего не буду изменять в своём алгоритме. Если вы хотите запустить мой алгоритм без изменений, пожалуйста. Если вы хотите изменить мой алгоритм, тоже пожалуйста, но тогда это будет уже ваш алгоритм. Вы запускаете его в BOINC-проекте сами, без моего участия. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Цитата (из темы "Задача") Ну, если не вся линейка №51 может быть взята в разработку, то половина её точно может быть взята. https://boinc.progger.info/odlk/forum_thread.php?id=115&postid=3701#3701 |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Цитата Замечание 5. Продемонстрирую это замечание на примере. Вот интервал между двумя КФ ОДЛК, решения взяты с проекта ODLK КФ ОДЛК1 0 2 3 4 5 6 7 8 9 1 3 1 0 6 7 4 9 5 2 8 7 5 2 1 0 9 8 3 6 4 6 9 5 3 1 8 4 2 0 7 9 6 8 7 4 0 2 1 5 3 2 4 1 8 9 5 3 0 7 6 4 0 7 5 8 1 6 9 3 2 5 8 6 9 3 2 1 7 4 0 1 7 9 2 6 3 0 4 8 5 8 3 4 0 2 7 5 6 1 9 КФ ОДЛК2 0 2 3 4 5 6 7 8 9 1 3 1 0 6 7 4 9 5 2 8 7 5 2 1 0 9 8 3 6 4 6 9 8 3 2 1 4 0 5 7 2 3 5 8 4 0 1 9 7 6 4 8 1 7 9 5 0 6 3 2 9 0 7 5 1 8 6 2 4 3 5 4 6 9 8 3 2 7 1 0 1 7 9 0 6 2 3 4 8 5 8 6 4 2 3 7 5 1 0 9 Определяем, сколько в этом интервале имеется КФ. Это делается с помощью программы Белышева moschnometr_kf. Смотрите об этой программе тему https://boinc.progger.info/odlk/forum_thread.php?id=27#398 Итак, определили, что в данном интервале Найдено СНДЛК: 824102 Найдено КФ: 824102 Очень хорошо! Теперь генерируем 824102 КФ программой generator_kf и проверяем их программой family_mar. [Замечу, что КФ генерируются, начиная со следующей за КФ ОДЛК1 КФ, и до конца интервала, то есть включая КФ ОДЛК2.] Найдено 9 решений, в том числе КФ ОДЛК2. Если вы проверите все 824102 КФ интервала на наличие у них ортогональных ДЛК, будет найдено всего одно решение - КФ ОДЛК2!!! Вот так всё просто! Ну очень просто! Я проверила уже десятки интервалов. Во всех интервалах решения найдены, и все уникальные. Конечно, я выбрала лёгкие (короткие) интервалы, в которых не больше миллиона КФ. Есть огромные интервалы, содержащие несколько миллионов КФ. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Товарищи! Господа! Ну где вы с кластерами и суперкомпьютерами??? :) Задаёте минимальную КФ, задаёте максимальную КФ, запускаете генератор КФ (программа Белышева generator_kf), программа генерирует КФ, хватаете их и отправляете на проверку программой Белышева family_mar. Всё! Сколько времени потребуется суперкомпьютеру для решения этой задачи? Думаю, может быть, за месяц управится :) Это если половину линейки №51 взять в обработку. BOINC-проект уровня ODLK1, возможно, справится за год - полтора - два. Один ПК моего уровня не справится и за 10 лет. Минимальная КФ Максимальная КФ 0 5 4 7 8 6 9 2 3 1 9 1 8 4 7 3 0 6 2 5 5 4 2 6 0 8 1 3 9 7 1 2 9 3 5 7 4 8 0 6 6 8 5 2 4 0 7 9 1 3 7 3 0 1 9 5 8 4 6 2 3 9 1 5 2 4 6 0 7 8 2 0 6 8 1 9 3 7 5 4 4 7 3 9 6 2 5 1 8 0 8 6 7 0 3 1 2 5 4 9 И две программы Белышева. И больше ничего не надо! И всё решается сразу и до конца. Покажите же миру свою мощную технику! Что она может на самом деле. А то только разговоры слышу: кластеры, суперкомпьютеры... А где они? Не видно что-то. PS. Замечу, что в BOINC-проекте ODLK линейка №51 проверяется более лёгкой проверкой (только на наличие ОДЛК у КФ); проверяется уже больше года; половина линейки ещё не проверена. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
А посмотрите-ка на максимальную КФ (которую я имею в линейке №51 на данный момент) Весьма интересный псевдоассоциативный ДЛК! Повторю основной тезис: все СН ДЛК и КФ СН ДЛК в линейках 15, 38 и 51 являются псевдоассоциативными ДЛК с разной степенью ассоциативности. Сравните степень ассоциативности в минимальной КФ (см. предыдущий пост) и в максимальной КФ (нарушения ассоциативности в обеих КФ в белых ячейках). |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Накапливаю банк КФ в линейке №51 для эксперимента PADLS TOTAL. Зачем нужен банк КФ? Это опорные точки - границы интервалов. Зачем нужны интервалы? Интервалы нужны для возможности делать генерацию КФ порционной. Понятно же, что в заданном интервале КФ гораздо проще сгенерировать. Как уже отмечалось выше, в линейке №51 есть очень проблемные для генерации КФ области, в которых на миллиарды СН ДЛК нет ни одной КФ. Вот для таких областей необходимы опорные точки, которые задают интервалы. В начале линейки всё просто. Например, самый первый интервал минимальная КФ 0 2 3 4 5 6 7 8 9 1 3 1 0 6 7 4 5 9 2 8 1 0 2 7 6 8 9 3 4 5 2 5 1 3 8 9 4 0 6 7 5 3 7 9 4 0 8 2 1 6 6 4 8 0 9 5 2 1 7 3 7 8 9 5 0 1 6 4 3 2 4 9 6 8 1 2 3 7 5 0 9 7 5 1 2 3 0 6 8 4 8 6 4 2 3 7 1 5 0 9 минимальная КФ ОДЛК 0 2 3 4 5 6 7 8 9 1 3 1 0 6 7 4 5 9 2 8 1 0 2 9 6 7 8 3 4 5 7 6 9 3 8 1 4 5 0 2 9 5 8 1 4 0 3 2 6 7 6 3 1 8 9 5 2 4 7 0 2 9 7 5 1 8 6 0 3 4 4 8 6 0 2 9 1 7 5 3 5 7 4 2 0 3 9 1 8 6 8 4 5 7 3 2 0 6 1 9 В этом интервале программой Белышева moschnometr_kf Найдено СНДЛК: 93562426 Найдено КФ: 93562426 Больше 93 миллионов СН ДЛК и все они КФ! Понятно, что тут нет проблем с генерацией КФ. Кстати, я уже давно проверяю этот интервал в эксперименте PADLS TOTAL. Решения идут стабильно и все пока уникальные. Проверила 11 миллионов КФ в данном интервале. |
©2024 (C) Progger