Message boards :
Science :
Алгоритм PADLS TOTAL
Message board moderation
Author | Message |
---|---|
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Начну публикацию замечаний, относящихся к алгоритму PADLS TOTAL, который в настоящее время находится у меня в разработке и тестировании. Точнее: в тестировании находится одна из трёх ветвей данного алгоритма: PADLS TOTAL rule 51. Замечание 1. Задача, решаемая тут https://boinc.progger.info/odlk/forum_thread.php?id=115 имеет непосредственное отношение к указанной ветви алгоритма. Почему я выбрала для первой ветви алгоритма линейку №51? По той простой причине, что в этой линейке более высокий процент содержания КФ, по сравнению с линейками 15 и 38. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Замечание 2. Цитирую сообщение из указанной выше темы "Задача" Так, имеем минимальную КФ СН ДЛК в линейке №51 |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Замечание 3. Вот здесь https://boinc.progger.info/odlk/forum_thread.php?id=66&postid=1719#1719 24 марта 2018 г. сообщалось Three new rulers have been added to the Application odlk3@home: 15, 38, 51. Итак, больше года линейки 15, 38, 51 проверяются в BOINC-проекте ODLK. Это хорошо. Именно в результатах проекта ODLK я сейчас взяла КФ для составления своего банка КФ в линейке №51. Но! Линейки эти в проекте ODLK проверяются не так. Почему не так? Tomas Brada заметил: 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 Верное замечание! |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Замечание 4. При разработке алгоритма PADLS я писала (28 декабря 2017 г.) Все сгенерированные псевдоассоциативные ДЛК проверила на ОДЛК, пока не нашла решений, но ещё мало сгенерировала ДЛК. отсюда https://boinc.progger.info/odlk/forum_thread.php?id=51&postid=1260#1260 В-о-о-о-т! Удача была в том, что мне пришла в голову счастливая идея проверить сгенерированные псевдоассоциативные ДЛК программой Белышева Канонизатор ЛК по ДЛК (это и есть по сути программа family_mar). И после этого я стала проверять все псевдоассоциатвиные ДЛК именно этой программой. Сравните с замечанием Tomas Brada. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
В BOINC-проекте ODLK ДЛК из линеек 15, 38, 51 проверяются просто на наличие у них ортогональных диагональных соквадратов. Конечно, некоторые ДЛК из этих линеек имеют ОДЛК, но таких ДЛК очень мало. К тому же, решения получаются в основном однушки и двушки. Понятно, что абсолютно все ДЛК в этих линейках суть псевдоассоцитаивные ДЛК, только с разной степенью ассоциативности. Мой генератор 1 выбирал псевдоассоциативные ДЛК с самой высокой степенью ассоциативности. Затем генератор 2 выбирал псевдоассоциативные ДЛК с менее высокой степенью ассоциативности, нежели генератор 1. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Цитата Пока выложу эту замечательную КФ ОДЛК из линейки №51 без комментариев, чтобы потом не забыть про неё Смотрите сообщение https://boinc.progger.info/odlk/forum_thread.php?id=115&postid=3557#3557 Эта ромашковая прелесть - решение, найденное непосредственно от псевдоассоциативного ДЛК в линейке №51, и это тройка! Тройка единственная на данный момент - найденная непосредственно от псевдоассоциативного ДЛК в линейке №51. Все остальные решения в проекте ODLK в этой линейке - однушки и двушки. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Посмотрите для сравнения, какие решения находят Demis и XAVER в ручных экспериментах PADLS rule 15 и PADLS rule 51; это только от одной малюсенькой порции WUs (у Demis 100 WUs, у XAVER 50 WUs) От Demis Найдено марьяжных КФ: count[1] = 4628 count[2] = 362 count[3] = 11 count[4] = 14 count[6] = 1 count[8] = 1 Всего: 5017 Найдено соквадратов: 5455 КФ соквадратов: 5017 https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3628#3628 От XAVER Найдено марьяжных КФ: count[1] = 2764 count[2] = 674 count[4] = 23 Всего: 3461 Найдено соквадратов: 4204 КФ соквадратов: 3461 https://boinc.progger.info/odlk/forum_thread.php?id=107&postid=3612#3612 Подчеркну, что сейчас эти ветви эксперимента выполняются второй раз, с подключением генератора 2. Первый раз мы выполнили эти ветви с Demis, когда работал только генератор 1. По получаемым сейчас результатам видно, что большее количество решений и почти все солидные группы пар ОДЛК были получены от генератора 1. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Итак, думаю, что основная идея алгоритма PADLS TOTAL понятна. Уважаемый Progger! Паче чаяния вы сюда заглянете... С прошедшим вас Днём Рождения нашего проекта! Описываемый здесь алгоритм PADLS TOTAL планируется к запуску в BOINC-проекте Tomas Brada примерно через месяц. А вам не завидно? :) Ох, не прошу уже запустить, просто вот любопытно. Эксперимент, который вы могли бы запустить за пару часов в одном из BOINC-проектов (ODLK или ODLK1), уходит на сторону. И вам как бы всё равно? Линейки 15, 38, 51 в BOINC-проекте ODLK проверяются уже больше года. Надо только изменить программу проверки. И всё! И программа эта давно существует, это программа Белышева family_mar. PS. Писем вам давно уже не пишу, потому что вы перестали на них отвечать. Администратор проекта игнорирует научного руководителя проекта. Я не удивляюсь. В России и не такое бывает! |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Замечание 5. Очень важный момент: проверка программой family_mar найдёт все решения: и те, что получаются непосредственно от ДЛК линеек 15, 38, 51 проверкой их на наличие ортогональных ДЛК, и те, что получаются только сложной проверкой алгоритмом, реализованным в программе family_mar. Если запустить эксперимент PADLS TOTAL для линеек 15, 38, 51, обычную проверку этих линеек в BOINC-проекте ODLK можно остановить. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
Interesting. I subscribe. And I am still thinking how to remove duplicates to avoid repeated computations of the same data. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
And I am still thinking how to remove duplicates to avoid repeated computations of the same data. В эксперименте PADLS TOTAL нет и не может быть одних и тех же данных! Однако всё, что было найдено раньше от генераторов 1 и 2, обязательно будет повторено в эксперименте PADLS TOTAL. Этого невозможно избежать. Но доля всех ранее найденных решений очень мала. Множество всех псевдоассоциативных ДЛК огромное! Это миллиарды и миллиарды. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
I just analysed ASS_DLK10A_R38 generator for workunit 2 3 4 5 7 8 9 6 and 2 3 4 5 7 9 8 6. There are 64 duplicate CF DLS. The duplicates are listed below in format 3 to save space. 2 3 4 5 7 8 9 6 produced 20960 CF DLS. 2 3 4 5 7 9 8 6 produced 23376 CF DLS, of which 64 are same as 2 3 4 5 7 8 9 6. Then I checked first (approx) 100 rows, and found 362152 duplicate CF DLS, which is 12.2% !!! LNmuvfrNnDVUX6DyF5Yi4eAK4 LNmuvjN8iDVUX6DyF5Yi4eA9q LNmuvkp2vSjnHfFf3DXKs6JTt LNmuvpKnrSjnHfFf3DXKs6Hsq LNmvDaCgiSPNFhiMuJJ8rerP3 LNmvDLZdLJG7WUGqD7VaQ5sWB LNmvDQHNSJG7WUGqD7VaQ5sL5 LNmvDRXHUSPNFhiMuJJ8rerZ9 LNmvkbSBBHhHqe5UYQXNXuEE6 LNmvkbSBB7ZoB5WFMHopdsJaW LNmvkeXxmHhHqe5UYQXNXuE5w LNmvkeXxm7ZoB5WFMHopdsJSM LNmvkgbpVHoSNqCEaS7xMusWr LNmvkgbpV5sSySat5Hdhcypgi LNmvkoDN1HoSNqCEaS7xMusAH LNmvkoDN15sSySat5HdhcypL9 LNmvniBhbHCXzUGyB1CQiwBFy LNmvniBhbSPNZpvGwJJ8nxafd LNmvniBhb1CSSVz4VHCWGuUAf LNmvnomKFHCXzUGyB1CQiwB7n LNmvnomKFSPNZpvGwJJ8nxaXS LNmvnomKF1CSSVz4VHCWGuU2U LNmvnoMLuHCXu9Yby1CQiwBgo LNmvnoMLuJG5eu2dm7VaLPcFu LNmvnoMLu1CSMBFhHHCWGuUbV LNmvnrT8VHCXu9Yby1CQiwBLC LNmvnrT8VJG5eu2dm7VaLPbuJ LNmvnrT8V1CSMBFhHHCWGuUEt LNmvSataNEVG7o8wP5tza5EeH LNmvSataNS8iydoEeEbAMX4ZT LNmvSfeFLEVG7o8wP5tza5EUC LNmvSfeFLS8iydoEeEbAMX4PN LNmvShW7tEXSSAquu7aaC3PrM LNmvShW7tQWc7UDatEWoiRnv1 LNmvSv7FQEXSSAquu7aaC3PgG LNmvSv7FQQWc7UDatEWoiRnjv LNmvVzNfTEzLMvQa61HQWtkPK LNmvVzNfTSjnbn3bfDXKoQ29P LNmvVzNfT1HS8V9rzEzJkL16R LNmvWMFDsDVSfWZoP5YhzwtnQ LNmvWMFDsEzLKUEXE1HQWtkXv LNmvWMFDs1HS62yp8EzJkL1F2 LNmvW6aEdDVSfWZoP5YhzwuVT LNmvW6aEdEzLKUEXE1HQWtmEy LNmvW6aEd1HS62yp8EzJkL1x5 LNmvW8r5XEzLMvQa61HQWtkKW LNmvW8r5XSjnbn3bfDXKoQ25a LNmvW8r5X1HS8V9rzEzJkL12c LNmv762UrHnxNQmmN7aXvU9yu LNmv762UrS6oTtuFSHW24N3gP LNmv762USHX3D7Y4tS7cms4aw LNmv762US7ZqHs3CpHops5hZD LNmv762UZHnxNQmmN7aXxZTc7 LNmv762UZS6oTtuFSHW26TMJb LNmv762U9HX3D7Y4tS7coxND9 LNmv762U97ZqHs3CpHopuB1BR LNmv766XzJkXUCAwiRm3Gtk6w LNmv766Xz6rYApDX8Jh2xo6PV LNmv766YKJkXUCAwiRm3ErkFV LNmv766YK6rYApDX8Jh2vm6Y3 LNmv766YXJgF5Nawc6ubREEif LNmv766YXRk8fYQ7aJiVGHm8P LNmv766Z8JgF5Nawc6ubLdT95 LNmv766Z8Rk8fYQ7aJiVBgyYo |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
I just analysed ASS_DLK10A_R38 generator for workunit 2 3 4 5 7 8 9 6 and 2 3 4 5 7 9 8 6. There are 64 duplicate CF DLS. The duplicates are listed below in format 3 to save space. Я это знаю. Мои генераторы генерируют псевдоассоциативные ДЛК, а не КФ ДЛК!!! Многие из сгенерированных ДЛК оказываются изоморфными (изоморфными, а не совпадающими!). Отсюда дубликаты, дубликаты появляются после канонизации. Один ДЛК 10-го порядка может иметь 15360 изоморфов, включая его самого! В экспериментах с моими генераторами присутствует этап канонизации псевдоассоциативных ДЛК. Это исключает изоморфы, но только в данной порции ДЛК. В эксперименте PADLS TOTAL генерируются КФ. Среди КФ не может быть дубликатов! Все КФ уникальны. В этом эксперименте отсутствует этап канонизации. Зато в эксперименте PADLS TOTAL большие трудности с генерацией КФ. Смотрите тему "Задача". Я сейчас пытаюсь создать банк КФ в линейке №51. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Программа генерации КФ есть, это программа Белышева generator_kf. Однако в некоторых областях линейки №51 на несколько миллиардов СН ДЛК нет ни одной КФ! Сейчас у меня работает эта программа . . . . . . . . . . СНДЛК: 3218500000 КФ: 19952 время: 23825 сек СНДЛК: 3219000000 КФ: 19952 время: 23831 сек СНДЛК: 3219500000 КФ: 19952 время: 23836 сек СНДЛК: 3220000000 КФ: 19952 время: 23842 сек СНДЛК: 3220500000 КФ: 19952 время: 23846 сек СНДЛК: 3221000000 КФ: 19952 время: 23852 сек СНДЛК: 3221500000 КФ: 19952 время: 23858 сек СНДЛК: 3222000000 КФ: 19952 время: 23863 сек СНДЛК: 3222500000 КФ: 19952 время: 23869 сек СНДЛК: 3223000000 КФ: 19952 время: 23874 сек СНДЛК: 3223500000 КФ: 19952 время: 23879 сек СНДЛК: 3224000000 КФ: 19952 время: 23884 сек СНДЛК: 3224500000 КФ: 19952 время: 23888 сек СНДЛК: 3225000000 КФ: 19952 время: 23893 сек СНДЛК: 3225500000 КФ: 19952 время: 23898 сек СНДЛК: 3226000000 КФ: 19952 время: 23901 сек . . . . . . . . Идёт уже четвёртый миллиард СН ДЛК, сгенерировано всего 19952 КФ. Уже несколько часов новые КФ не появляются. Это может продолжаться очень долго! А в экспериментах с моими генераторами не было проблем с генерацией ДЛК, но там была проблема изоморфизма. |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
While you were writing I found a way to remove the isomorphs, but I must verify that is does not remove unique ones. I will check the other thread for how you solved the problem for TOTAL generator. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
I will check the other thread for how you solved the problem for TOTAL generator. TOTAL generator - это генератор Белышева generator_kf. Этот генератор генерирует КФ! Все КФ находятся в линейке №51, все они суть псевдоассоциативные ДЛК, и все они различны. Я показала выше пример работы этой программы. Все те СН ДЛК, которые не совпадают со своей КФ, программа пропускает; она собирает (генерирует) только те СН ДЛК, которые суть КФ. Это понятно? |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
My initial attempt to remove izomorphs did remove the duplicates, but it also removed a lot of unique CF. Either it was just wrong approach, or it was due to use of weak generator. The CF transform could have moved the violations of associativity to other rows and so they appear as unique. But I am not sure. We will see how it works in the PADLS TOTAL. I of corse meant PADLS TOTAL, not Belysev's total in my previous message. Does PADLS TOTAL really generate only CF? Or how does it work. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
We will see how it works in the PADLS TOTAL. Повторяю: в эксперименте PADLS TOTAL не будет изоморфов, не будет дубликатов. Поэтому ваша методика удаления изоморфов в этом эксперименте не пригодится. Does PADLS TOTAL really generate only CF? Or how does it work. Я уже объяснила, как это работает. Генератор Белышева generator_kf генерирует КФ! Все КФ находятся в линейке 51, все они являются псевдоассоциативными ДЛК, и все они различные. |
Send message Joined: 6 Apr 17 Posts: 14104 Credit: 0 RAC: 0 |
Вот как это работает . . . . . . . . СНДЛК: 4411000000 КФ: 19952 время: 30348 сек СНДЛК: 4411500000 КФ: 19952 время: 30351 сек СНДЛК: 4412000000 КФ: 19952 время: 30353 сек СНДЛК: 4412500000 КФ: 19952 время: 30356 сек СНДЛК: 4413000000 КФ: 19952 время: 30358 сек СНДЛК: 4413500000 КФ: 19952 время: 30361 сек СНДЛК: 4414000000 КФ: 19952 время: 30364 сек СНДЛК: 4414500000 КФ: 19952 время: 30366 сек СНДЛК: 4415000000 КФ: 19952 время: 30368 сек СНДЛК: 4415500000 КФ: 19952 время: 30371 сек СНДЛК: 4416000000 КФ: 19952 время: 30373 сек СНДЛК: 4416500000 КФ: 19952 время: 30375 сек СНДЛК: 4417500000 КФ: 19952 время: 30380 сек . . . . . . . У кого есть мощная техника, это не сложно, если технику можно заставить работать непрерывно. Для меня сложно. Это может работать много часов, пока сгенерируется заданная порция КФ - 50000 КФ. На данный момент сгенерировано всего 19952 КФ. Ещё хуже то, что программа не сохраняет последний проверенный СН ДЛК при прерывании. Конечно, вечером я программу прерву. А где остановилась проверка, я не знаю. И надо начинать всё сначала! |
Send message Joined: 14 Jan 19 Posts: 119 Credit: 574 RAC: 0 |
I ask for clarification. Are all CF DLS generated by generator_lk in lines 15, 38 and 51 pseudo associative? Is generator_lk THE generator for padls total? Why you want to use family_mar instead of the faster orthogonality test? |
©2024 (C) Progger