Новый конкурс программистов

[whitefox]

Pavlovsky в сообщении #626778 писал(а):

Думаете такое преобразование найти легко? Будет время поищу. А может и не буду искать.

Раз Pavlovsky не хочет, поищу я.

Имеем базовое множество перестановок:

1: 1 2 3 4 5 6
2: 2 3 4 5 6 1
3: 3 4 5 6 1 2
4: 4 5 6 1 2 3
5: 5 6 1 2 3 4
6: 6 1 2 3 4 5

и базовую матрицу:

1 1 1 1 1
1 2 3 4 5
1 3 6 2 4
1 4 2 5 3
1 6 5 3 2

Умножим справа все перестановки базового множества на перестановку:

5 3 2 6 4 1

(умножение перестановок я выполняю слева направо)
Получим новое базовое множество перестановок:

1: 5 3 2 6 4 1
2: 3 2 6 4 1 5
3: 2 6 4 1 5 3
4: 6 4 1 5 3 2
5: 4 1 5 3 2 6
6: 1 5 3 2 6 4

при этом базовая матрица не изменилась, хотя номера обозначают уже совсем другие перестановки.

Переупорядочим базовое множество в соответствии с перестановкой:

5 3 2 6 4 1

Получим:

1: 1 5 3 2 6 4   
2: 2 6 4 1 5 3   
3: 3 2 6 4 1 5   
4: 4 1 5 3 2 6   
5: 5 3 2 6 4 1   
6: 6 4 1 5 3 2

При этом также изменится и базовая матрица:

5 5 5 5 5
5 3 2 6 4
5 2 1 3 6
5 6 3 4 2
5 1 4 2 3

Теперь умножим слева каждую перестановку базового множества на перестановку:

1 4 3 6 2 5

Получим:

1: 1 2 3 4 5 6
2: 2 1 4 3 6 5
3: 3 4 6 5 2 1
4: 4 3 5 6 1 2
5: 5 6 2 1 3 4
6: 6 5 1 2 4 3

Базовая матрица не меняется.

Можно легко убедиться, что матрица:

5 5 5 5 5
5 3 2 6 4
5 2 1 3 6
5 6 3 4 2
5 1 4 2 3

является базовой для множества перестановок:

1: 1 2 3 4 5 6
2: 2 1 4 3 6 5
3: 3 4 6 5 2 1
4: 4 3 5 6 1 2
5: 5 6 2 1 3 4
6: 6 5 1 2 4 3

Осталось проверить изоморфна ли эта матрица одной из восьми (а точнее шести) матриц Pavlovsky
для ЛК №1.

[Pavlovsky]

В главе 12.4 Холл вводит понятия почти-поле и полу-поле. Хотя это позволяет строить все теже решения первого класса. Но при этом получаются недезарговы геометрии. Я так понимаю, что пока все наши регулярные решения были дезарговыми геометриями. Чисто эстетический вопрос, чем они отличаются?

[whitefox]

whitefox в сообщении #626886 писал(а):

Осталось проверить изоморфна ли эта матрица одной из восьми (а точнее шести) матриц Pavlovsky
для ЛК №1.

Множество перестановок:

1: 1 2 3 4 5 6
2: 2 1 4 3 6 5
3: 3 4 6 5 2 1
4: 4 3 5 6 1 2
5: 5 6 2 1 3 4
6: 6 5 1 2 4 3

является группой, с таблицей умножения:

1 2 3 4 5 6
2 1 4 3 6 5
3 4 6 5 2 1
4 3 5 6 1 2
5 6 2 1 3 4
6 5 1 2 4 3

Применим к базовой матрице:

5 5 5 5 5
5 3 2 6 4
5 2 1 3 6
5 6 3 4 2
5 1 4 2 3

умножим справа все элементы всех строк базовой матрицы на перестановку №4, то есть выполним преобразование №3 всех строк. Получим:

1 1 1 1 1      
1 5 3 2 6      
1 3 4 5 2      
1 2 5 6 3      
1 4 6 3 5   

Выполним нормализацию:

1 1 1 1 1
1 2 3 5 6
1 3 2 4 5
1 4 5 6 3
1 5 6 3 2

Эта матрица есть одна из матриц Pavlovsky.

[Nataly-Mak]

whitefox
грандиозное исследование!
Мне не хватает знаний, чтобы всё понять.
Поняла только: вы нашли очень сложное преобразование (являющееся комбинацией преобразований), переводящее базовую матрицу alexBlack №1 (она же и ваша матрица) в одну из матриц Pavlovsky.
Хорошо вы разобрались в теории Pavlovsky, не хуже автора

К сожалению, ни теория Pavlovsky, ни теория svb, ни матричный метод в общем виде не продвинулись дальше решений C6N36 (имею в виду С<>p^k, p - простое число, k>=1).
В частности недосягаемой остаётся жар-птица - решение C10N100.
Перебор огромный, да. Но можно было бы объединить все силы. Для начала нужна хорошая программа, максимально оптимизированнная. Если бы был такой проект по поиску решения C10N100, думаю, никто из участников темы не отказался бы принять в нём участие.
Кстати, не так уж и страшен перебор для С=10. Ведь alexBlack выполнил его для блоков с циклическим сдвигом! К сожалению, для таких блоков максимальная базовая матрица 8х8. А если бы объединёнными силами, то совсем не страшный

Никто похоже не занимается и не строго диагональными решениями. А почему, к примеру, не может существовать не строго диагональное решение C5N26?
У меня заканчивается поиск не строго диагонального решения C5N25; программа работает уже 115 часов. Скорее всего, это решение не существует. Потом собираюсь прогнать программу для не строго диагонального решения C5N26. Если и этого решения не существует, тогда вопрос с диагональными решениями для С=5 будет закрыт. Но только для С=5!

Сейчас уже не за горами новый конкурс. Это может отвлечь внимание на новую задачу.
А я ещё не дописала книгу Написано всего 6 глав, ещё как минимум 2-3 главы надо написать.

Подводя общие итоги обсуждения задачи, хочется заметить, что слаженной работы не было. По мнению svb во время конкурса были ограничения, накладываемые правилами конкурса. Что ограничило слаженную работу после конкурса? Некоторые участники обсуждения вообще ушли из темы. Оставшиеся участники по-прежнему работают каждый сам по себе, нет совместных действий по решению ни одной подзадачи! И это очень плохо.

Могу отметить только огромную помощь whitefox в работе с диагональными решениями.
Отличная программа, хорошо оптимизированная и (по моей просьбе) с возможностью прерывать программу в любой момент с сохранением текущего положения в переборе, позволила мне выполнить поиск не строго диагонального решения C5N25, а может, ещё поищу и не строго диагональное решение C5N26.
Кроме того, с помощью его программы сделана большая база данных не строго диагональных решений (в двух частях, 342 решения).

Это у меня единственный пример совместной работы в решении одной подзадачи.

Как правильно тут заметил dimkadimon, "вместе мы сильнее". Ну, истина сия стара как мир. Увы, в конкурсе мы соревнуемся, и каждый сам по себе и сам за себя.
Хотя я всегда была сторонницей командного участия в конкурсе. К сожалению, моя команда от меня разбежалась. Говорят, я очень строгий капитан

[dimkadimon]

Nataly-Mak в сообщении #627095 писал(а):

Это у меня единственный пример совместной работы в решении одной подзадачи.

Мне кажется вы глубоко ошибаетесь. Мне даже обидно что вы так говорите. Не знаю как другие, но я старался участвовать во всех под-задачах которые меня интересовали:

* Вместе с вами искал строго и не строго диагональные решения
* Вместе с вами искал базовые матрицы для C10N100
* Вместе с вами искал сильное 84х10
* Искал решения для некоторых под-задач Pavlovsky
* Искал решения с единичками вместе с Tom Sirgedas и Roland Postle

В этом конкурсе не было групповой работы, потому что не было никакой универсальной идеи которая гарантировала бы хороший результат. Может у кого то были хорошие идеи, но остальные не видели в них потенциала, а может они их толком не понимали. Многие идеи (особенно с базовами матрицами) были совершено одинаковами, просто подходы были немного разные. Практически последние 10 страниц этого форума обсуждают одну и ту же идею. Мою самую оригинальную идею (где я разбиваю квадрат на 1хC строчки и их заполняю единичками) никто даже не прокоментировал. Может её не поняли? А может поняли но не увидели в ней ничего полезного. Если честно, то я тоже не вижу в ней пользы. Когда я стал улучшать результаты C=15 и 21 методом отжига, никто ко мне не присоединился хотя они явно были наиболее близки к улучшению. Мне пришлось самому найти эти решения после долгих мучений - мой компьютер безпрерывно работал почти месяц.

[Nataly-Mak]

dimkadimon в сообщении #627101 писал(а):

Не знаю как другие, но я старался участвовать во всех под-задачах которые меня интересовали:

* Вместе с вами искал строго и не строго диагональные решения
* Вместе с вами искал базовые матрицы для C10N100
* Вместе с вами искал сильное 84х10
* Искал решения для некоторых под-задач Pavlovsky
* Искал решения с единичками вместе с Tom Sirgedas и Roland Postle

dimkadimon
да, соглашусь: вы были активным участником темы. Я выразила вам благодарность на форуме конкурса. Заметили?

Однако и вы не участвовали в каком-то большом совместном проекте решения отдельной подзадачи.
Да, немного помогали с диагональными решениями. Но... это уже после того, как почти завершила работу над базой данных. А в самом начале, вспомните-ка... Когда я предложила всем заняться диагональными решениями, вы что тогда ответили? Напомнить? Вы ответили, что вас диагональные решения не интересуют. Разве не так?
Поэтому не надо обижаться.
О 10-сильном прямоугольнике 84х10... Пришлось спрашивать вас раза три, что именнно вы имеете по этому решению. Напомнить? Или сами помните?
Я выложила целый файл с материалами к этой подзадаче. Хоть кто-нибудь заглянул в этот файл??? Поднять руки, кто заглянул
Создала даже отдельную тему на форуме по этой задаче. Кто-нибудь заглянул в эту тему?
svb заглянул и написал тут, что ничего не понял. А что конкретно не понял, так и не сказал Я бы разъяснила всё, что непонятно, всем, кто захотел бы это понять. Но желающих понимать не нашлось
А между прочим, в этой подзадаче содержится не только поиск решения C10N94, которое уже и не актуально, как результат для конкурса. В этой подзадаче содержится и поиск следующих решений: C10N95, C10N96 и т.д.

Цитата:

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

Э-э-э-э... Гарантировать хороший результат в сложных задачах (типа решения C10N100) очень трудно. Никто не может гарантировать.
Мне (и не только мне!) приходилось решать такие задачи по магическим квадратам, когда процесс поиска решения растягивался на месяцы и даже годы. Не верите? Загляните в тему "Магические квадрыты", убедитесь в правоте моих слов. О существовании решения заранее никто и не знал. Создавали совместными усилиями алгоритмы, писали программы и искали решение. Это были счастливые для меня годы совместной работы! У меня были замечательные коллеги: Макс Алексеев (maxal), Валерий Павловский (Pavlovsky), Сергей Беляев (svb), Алексей Чернов (alexBlack), Сергей Зоркин (12d3), Stefano Tognon и др. Теперь это в прошлом

Цитата:

Когда я стал улучшать результаты C=15 и 21 методом отжига, никто ко мне не присоединился хотя они явно были наиболее близки к улучшению. Мне пришлось самому найти эти решения после долгих мучений - мой компьютер безпрерывно работал почти месяц.

Вот то-то и оно!
Я попыталась вам помочь, но моя программа не работает с такими большими квадратами, точнее, работает, но очень и очень медленно, одна итерация выполняется около минуты. Поэтому бесполезно было искать эти решения по моей программе.
Кроме того, у меня был свой большой проект - я работала с диагональными решениями, и сейчас ещё продолжаю работать.
Вам могли бы помочь, например, alexBlack, Zealint, но их похоже эта задача уже не интересует.

[Pavlovsky]

Пошло окончательное подведение итогов?
Активный обмен идеями. Это самое главное для исследований.
Лично я очень доволен обсуждением в этой теме. Ветка получилась шикарной. В своих исследованиях я использовал идеи всех участников обсуждения. Если чью то идею не стали обсуждать, это не значит что она была не интересна. Это всего лишь означает, что нечего было добавить в ее развитие.

Всем спасибо за участие в обсуждении. Отдельное спасибо порталу dxdy.

-- Пт окт 05, 2012 09:15:23 --

dimkadimon в сообщении #627101 писал(а):

Когда я стал улучшать результаты C=15 и 21 методом отжига, никто ко мне не присоединился хотя они явно были наиболее близки к улучшению.

Кстати вы обещали опубликовать особенности своей реализации метода отжига. Впрочем это касается всех. Ведь я так поянл отжигали все! Тема отжига не расскрыта в этой ветке! Меня останвливало реализовать метод отжига, непонимание почему он должен работать эффективно. Почему он не сваливается в локальный максимум?

-- Пт окт 05, 2012 09:25:43 --

dimkadimon в сообщении #627101 писал(а):

Когда я стал улучшать результаты C=15 и 21 методом отжига, никто ко мне не присоединился хотя они явно были наиболее близки к улучшению.

Кстати вы обещали опубликовать особенности своей реализации метода отжига. Впрочем это касается всех. Ведь я так поянл отжигали все! Тема отжига не расскрыта в этой ветке! Меня останвливало реализовать метод отжига, непонимание почему он должен работать эффективно. Почему он не сваливается в локальный максимум?

[whitefox]

Pavlovsky в сообщении #627115 писал(а):

Меня останвливало реализовать метод отжига, непонимание почему он должен работать эффективно. Почему он не сваливается в локальный максимум?

Попав в локальный минимум, метод отжига не сидит в нём, а пытается перепрыгнуть через барьер и попасть в соседний локальный минимум.
Так можно допрыгаться и до глобального минимума.

[Zealint]

Nataly-Mak в сообщении #627108 писал(а):

Вам могли бы помочь, например, alexBlack, Zealint, но их похоже эта задача уже не интересует.

У меня с сентября началась работа, и уже не до этих задач, так как появились более сложные и они же оказались более значимыми для университета. Могу дать задачу одному очень умному школьнику, он скорее всего продвинется дальше нас к концу года, но не уверен, что захочет.

-- Пт окт 05, 2012 08:59:26 --

whitefox в сообщении #627126 писал(а):

Pavlovsky в сообщении #627115 писал(а):

Меня останвливало реализовать метод отжига, непонимание почему он должен работать эффективно. Почему он не сваливается в локальный максимум?

Попав в локальный минимум, метод отжига не сидит в нём, а пытается перепрыгнуть через барьер и попасть в соседний локальный минимум.
Так можно допрыгаться и до глобального минимума.

Действительно, когда температура высокая, метод отжига пытается как можно дальше выпрыгнуть из этого локального решения. В моей модификации этого метода температура вообще прыгала возле высоких значений, а не уменьшалась монотонно, как требуется в классическом подходе. Фактически, я не строил квадраты, а выпекал их : ) Печка работала, не выключаясь.

[Pavlovsky]

При высокой темпереатуре алгоритм прыгает из зоны одного локального минимума в зону другого. Может даже заскочить в зону глобального минимума. Но так как температура высокая он легко выскакивает из зоны глобального минимума. Когда температура станет достаточно низкой. Алгоритм остается в зоне минимума, где его застала низакая температура. Получается какой то абсурд.

Не проще ли делать так. Случайным образом выбираем начальную точку оптимизации. А затем перебором спускаемся в локальный минимум. Повторяем эту процедуру, пока не повезет и мы не попадем в относительно глубокий минимум.

[whitefox]

Pavlovsky в сообщении #627141 писал(а):

Но так как температура высокая он лег выскакивает из зоны глобального минимума.

Отнюдь, не легко. Чем глубже минимум, тем выше барьер, и не так-то просто через него перепрыгнуть.

А в целом Вы правы -- выбор температуры целое искусство.
В своём варианте метода отжига я реализовал возможность задавать разные значения начальной температуры.

-- 05 окт 2012, 09:33 --

Pavlovsky в сообщении #627141 писал(а):

Случайным образом выбираем начальную точку оптимизации. А затем перебором спускаемся в локальный минимум. Повторяем эту процедуру, пока не повезет и мы не попадем в относительно глубокий минимум.

Но это и есть ещё одна разновидность метода отжига.

[dimkadimon]

Pavlovsky в сообщении #627115 писал(а):

dimkadimon в сообщении #627101 писал(а):

Когда я стал улучшать результаты C=15 и 21 методом отжига, никто ко мне не присоединился хотя они явно были наиболее близки к улучшению.

Кстати вы обещали опубликовать особенности своей реализации метода отжига. Впрочем это касается всех. Ведь я так поянл отжигали все! Тема отжига не расскрыта в этой ветке! Меня останвливало реализовать метод отжига, непонимание почему он должен работать эффективно. Почему он не сваливается в локальный максимум?

Я не использовал стандартный метод отжига и у меня не было никакой температуры. Конечно часто попадаешь в локальный минимум, но из него можно выбраться. Вот мой метод:

1. Выбираем случайное решение
2. Делаем какое то количество случайных ходов. Ход это перемена цвета одной клетки. Для больших C я использовал от 1 до 20, а для остальных от 1 до 10.
3. Пробуем все возможные ходы. Принимаем ход только если он уменьшает количество ошибок
4. Можно сохранять лучшие решения и их заново загружать, но как оказалось это не обязательно
5. Повторяем от 2

Часть 3 я делаю так чтобы не пересчитывать количество ошибок для каждого хода. Для этого у меня есть счётчик ошибок X(r,c) для каждой клетки (r,c). При одном ходе A(r,c):=k, могут измениться ошибки только в колонках c и рядах r. X обновляется для каждого хода. Этот метод во много (1000?) раз быстрее обычного метода, который каждый раз считает ошибки заново. Кстати если не менять клетки (r,c) в которых нет ошибок (то есть X(r,c)=0) тогда метод можно ускорить в 3 раза не теряя ничего в качестве.

Ну и последнее. Я одновремено запускал несколько (до 6) програм. Как только одна из них делала большой прогресс (например снижала количество ошибок от 2 до 1) то я останавливал остальные програмы и запускал их с этим новым решением.

[whitefox]

dimkadimon в сообщении #627150 писал(а):

1. Выбираем случайное решение

dimkadimon в сообщении #627150 писал(а):

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

То есть выбор на первом шаге не всегда был случайным?

dimkadimon в сообщении #627150 писал(а):

3. Пробуем все возможные ходы. Принимаем ход только если он уменьшает количество ошибок

А как Вы выбирали ячейку в которой пытались изменить цвет?

dimkadimon в сообщении #627150 писал(а):

При одном ходе A(r,c):=k, могут измениться ошибки только в колонках c и рядах r.

Пример:
1 1
1 2
Поменяем цвет в ячейке (2, 2) на 1. При этом ошибки появятся не только в колонке 2 и строке 2, но и в ячейке (1, 1).
Что я понял неправильно?

[dimkadimon]

whitefox в сообщении #627157 писал(а):

То есть выбор на первом шаге не всегда был случайным?

Я сделал так что можно было запускать с случайным решением либо загружать из файла

whitefox в сообщении #627157 писал(а):

как Вы выбирали ячейку в которой пытались изменить цвет?

Тут я пробовал все возможные ходы. Значит все r, c, и k. Чтобы все было равномерно я выбирал случайный порядок для расмотра ходов.

whitefox в сообщении #627157 писал(а):

Пример:
1 1
1 2
Поменяем цвет в ячейке (2, 2) на 1. При этом ошибки появятся не только в колонке 2 и строке 2, но и в ячейке (1, 1).
Что я понял неправильно?

Вы всё правильно поняли, это я неправильно объяснил. Допустим мы поменяли клетку (r1,c1) на цвет k. Теперь ищем клетку (r2,c2) чтобы A(r2,c2)=A(r2,c1)=A(r1,c2)=k. Если такая клетка есть, значит ошибки появились в клетках (r1,c1), (r1,c2), (r2, c1) и (r2,c2). Кстати таких (r2,c2) может быть несколько. Вот код:

//score это общeе количество ошибок до хода
//X[r][c] это количество ошибок в которых участвует клетка (r,c)
//Мы думаем делать ли нам ход a[r1][c1]=k или нет?
//Здесь мы подсчитаем сколько будет ошибок (newScore) если мы сделаем ход 

int newScore=score-X[r1][c1];
for (int r2=0; r2<height; r2++)     
{
  if (r2==r1) continue;
  if (a[r2][c1]!=col) continue;
  for (int c2=0; c2<width; c2++)
  {
    if (c2==c1) continue;
    if (a[r2][c2]==k && a[r1][c2]==k) newScore++;
  }
}

Теперь если newScore<score (количество ошибок уменьшилось) тогда мы делаем ход и обновляем Х:

//убираем старые ошибки (этих ошибок больше нет)
for (int r2=0; r2<height; r2++)
{
  if (r2==r1) continue;
  if (a[r2][c1]!=a[r1][c1]) continue;
  for (int c2=0; c2<width; c2++)
  {
    if (c2==c1) continue;
    if (a[r2][c2]==a[r1][c1] && a[r1][c2]==a[r1][c1])
    {
      Х[r2][c2]--;
      Х[r2][c1]--;
      Х[r1][c2]--;
      Х[r1][c1]--;
    }
  }
}

a[r1][c1]=k;   //делаем ход

//прибавляем новые ошибки
for (int r2=0; r2<height; r2++)
{
  if (r2==r1) continue;
  if (a[r2][c1]!=a[r1][c1]) continue;
  for (int c2=0; c2<width; c2++)
  {
    if (c2==c1) continue;
    if (a[r2][c2]==a[r1][c1] && a[r1][c2]==a[r1][c1])
    {
      X[r2][c2]++;
      X[r2][c1]++;
      X[r1][c2]++;
      X[r1][c1]++;
    }
  }
}

[whitefox]

dimkadimon в сообщении #627170 писал(а):

Вы всё правильно поняли, это я неправильно объяснил. Допустим мы поменяли клетку (r1,c1) на цвет k. Теперь ищем клетку (r2,c2) чтобы A(r2,c2)=A(r2,c1)=A(r1,c2)=k. Если такая клетка есть, значит ошибки появились в клетках (r1,c1), (r1,c2), (r2, c1) и (r2,c2). Кстати таких (r2,c2) может быть несколько.

Спасибо, теперь понятно.
Я тоже использовал этот метод.

dimkadimon в сообщении #627170 писал(а):

Я сделал так что можно было запускать с случайным решением либо загружать из файла

И это у меня тоже было реализовано.

dimkadimon в сообщении #627170 писал(а):

Тут я пробовал все возможные ходы. Значит все r, c, и k. Чтобы все было равномерно я выбирал случайный порядок для расмотра ходов.

А вот здесь нет.
Ячейки я выбирал тоже случайно, но только из числа содержащих ошибки, причём вероятность выбора была пропорциональна числу ошибок. И уже для выбранной ячейки проверял все цвета.