2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 120, 121, 122, 123, 124, 125, 126 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 11:21 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #627178 писал(а):
dimkadimon в сообщении #627170 писал(а):
Тут я пробовал все возможные ходы. Значит все r, c, и k. Чтобы все было равномерно я выбирал случайный порядок для расмотра ходов.
А вот здесь нет.
Ячейки я выбирал тоже случайно, но только из числа содержащих ошибки, причём вероятность выбора была пропорциональна числу ошибок. И уже для выбранной ячейки проверял все цвета.

Фактически я тоже самое делал, потому что я не менял клетки в которых нет ошибок. А вот с пропорциональностью вы хорошо придумали.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 13:21 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Все 10 базовых матриц, приведённых alexBlack, изоморфны.

Например, возьмём матрицу №1:
Код:
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
И выполним над ней следующие изоморфные преобразования:
1. ко всем элементам второй строки прибавим по модулю 6 число 5;
2. ко всем элементам третьей строки прибавим по модулю 6 число 4;
3. ко всем элементам четвёртой строки прибавим по модулю 6 число 3;
4. ко всем элементам пятой строки прибавим по модулю 6 число 1.
(вместо 0 используем 6)

Получим:
Код:
1 1 1 1 1
6 1 2 3 4
5 1 4 6 2
4 1 5 2 6
2 1 6 4 3
Переместим первый столбец на последнее место:
Код:
1 1 1 1 1
1 2 3 4 6
1 4 6 2 5
1 5 2 6 4
1 6 4 3 2
Получили матрицу №7.

Аналогично и для остальных матриц.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 13:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #627213 писал(а):
Все 10 базовых матриц, приведённых alexBlack, изоморфны.

Интересный вывод.
Я сократила количество базовых матриц alexBlack вдвое, а вы сократили ещё в 5 раз. В результате осталась всего одна базовая матрица :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 14:04 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #627222 писал(а):
Интересный вывод.
Я сократила количество базовых матриц alexBlack вдвое, а вы сократили ещё в 5 раз. В результате осталась всего одна базовая матрица :D

Возможно, что и базовые матрицы Pavlovsky тоже изоморфны.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 17:45 
Заслуженный участник
Аватара пользователя


19/12/10
1546
whitefox в сообщении #627229 писал(а):
Возможно, что и базовые матрицы Pavlovsky тоже изоморфны.
Так и есть все базовые матрицы Pavlovsky для ЛК №1 изоморфны.

Например, возьмём матрицу №1:
Код:
1,1,1,1,1
1,2,3,4,5
1,3,2,5,4
1,4,5,2,6
1,5,4,6,2
И выполним над ней следующие изоморфные преобразования:
1. все элементы второй строки умножим справа на перестановку №5 (5 6 2 1 3 4);
2. все элементы третьей строки умножим справа на перестановку №4 (4 3 5 6 1 2);
3. все элементы четвёртой строки умножим справа на перестановку №2 (2 1 4 3 6 5);
4. все элементы пятой строки умножим справа на перестановку №3 (3 4 6 5 2 1).

Получим:
Код:
1,1,1,1,1
5,6,2,1,3
4,5,3,1,6
2,3,6,1,5
3,2,5,1,4

Нормализуем:
Код:
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
Получили матрицу №5.

Аналогично и для остальных матриц.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 20:35 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #627276 писал(а):
Так и есть все базовые матрицы Pavlovsky для ЛК №1 изоморфны.

Наверное, оба автора совсем не рассматривали изоморфизм базовых матриц.

Впрочем, изоморфизм (базовых матриц да и самих решений) в обсуждении задачи, по-моему, очень слабое место.
Изоморфизм решений для меня всегда был интересным и важным вопросом. Однако я в нём так и не разобралась. А вот Tom Sirgedas и Roland Postle хорошо знают, как определять изоморфны ли раскраски.
dimkadimon тоже это знает, но только теоретически.

Когда я составляла базу данных диагональных решений, изоморфность двух решений определяла полу-интуитивно :D
Пока никто не прислал мне замечание, что я поместила в БД два изоморфных решения, хотя это не исключено.
Правда, БД смотрели, насколько мне известно, всего 2 человека.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 21:36 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #627335 писал(а):
Когда я составляла базу данных диагональных решений, изоморфность двух решений определяла полу-интуитивно :D

Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.
http://dxdy.ru/post621749.html#p621749

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 21:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А это два строго диагональных решения C3N8:

Изображение

Изоморфны ли эти решения? Я думаю, что изоморфны.

whitefox
я знаю, что вы просматривали БД не строго диагональных решений в процессе её создания. А окончательный вариант БД вы смотрели? Есть ли там изоморфные решения?
Много раз меня интуиция подвела? :D

-- Пт окт 05, 2012 23:00:43 --

whitefox в сообщении #627369 писал(а):
Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.
http://dxdy.ru/post621749.html#p621749

А для строго диагональных решений этот критерий не годится?

-- Пт окт 05, 2012 23:36:36 --

Выкладываю вторую часть книги "Monochromatic Squares или Математическая раскраска":
http://narod.ru/disk/62073950001.269e0b ... 2.rar.html

Здесь:
Глава 5. Метод использования ортогональных латинских квадратов
Глава 6. Расширение области применения теоремы 3.3

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

Мне пришло письмо в ЛС, автор пишет, что книга понятна только тем, кто участвовал в обсуждении задачи. Так ли это?
Он считает, что книгу надо писать так, чтобы не приходилось идти, скажем, в статью [1] за подробностями (это главная статья, которую участники темы хорошо знают). Да, я не поместила ссылки на статьи, виновата. Но это, разумеется, будет сделано в конце книги. К тому же ссылка на статью [1] есть на главной странице конкурса, а на эту страницу я указала ссылку во Введении.

Выложила вторую часть в формате doc (в этом формате намного лучше качество картинок).

dimkadimon
если файл у вас опять не откроется, сообщите. Я тогда выложу и в формате pdf.
Как всегда, прошу присылать замечания. Ценные замечания постараюсь учесть.

Сейчас меня вытащили на ПЕН, там в одной теме ссылаются на наши (с alexBlack и svb) работы по маршрутам коня. Заглянула, автору ЛС ответила. Заодно заглянула в свою тему "Играют все!"
Там в гордом одиночестве работает svb :D
Если кто интересуется задачей, загляните в эту тему. Он выложил там новую статью.
Данную тему он игнорирует. Что ж, игнор иногда вещь полезная (для обеих сторон!) :wink:

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение05.10.2012, 23:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #627369 писал(а):
Для нестрого диагональных решений критерий изоморфности простой: два нестрого диагональных решения изоморфны тогда и только тогда, когда их канонические базовые вектора равны.

Вот два не строго диагональных решения C4N8:

Изображение

whitefox
в вашем решении базовый вектор канонический.

Решение Herbert Kociemba я получила модификацией его строго диагонального решения C5N21 путём удаления строк и столбцов. Поэтому в решении нестандартное обозначение цветов, но это легко исправить, заменив цвет 5 (Е, розовый) на цвет 1 (А, голубой). Далее ещё раз сделала замену цветов: 2 -> 1, 1 -> 2.
У меня получился такой базовый вектор в этом решении:

Код:
1 3 4 2 2 3 1 2 1 2 3 3 4 3 1

Как преобразовать этот базовый вектор к каноническому виду? Что-то не соображу :-(

Добавлено

Кажется, получилось. Сделала сначала замену цветов: 2 -> 3, 3 -> 2, а потом замену цветов: 3 -> 4, 4 -> 3.

Получила такой вектор:

Код:
1 2 3 4 4 2 1 4 1 4 2 2 3 2 1

Это канонический вектор?
Значит, приведённые решения неизморфные?

Это решение Herbert Kociemba с преобразованным базовым вектором (ещё изменила направление диагоналей):

Изображение

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 05:02 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Красивая раскраска? :roll:

Изображение

Построена ходом коня на основе строго диагонального решения C3N9 (Herbert Kociemba).

Пусть метод не даёт рекордов, плюс ему за красоту.
Сейчас построю аналогичное решение C8N26 на основе своего строго диагонального решения C4N13.
Вот:

Изображение

И ещё хочу шедевр dimkadimon C5N25 (диагональное строго "ход конём") так же сделать. Получится 10-цветная раскраска всего 50х50, но... красиво.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 06:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот последняя раскраска - C10N50 (из решения dimkadimon) :?

Изображение

-- Сб окт 06, 2012 07:48:25 --

Herbert Kociemba в сообщении #610748 писал(а):
Diagonal solutions exist for C4N16, C5N25, C6N36 and C7N49, but *not* for C8N64, C9N81, C11N121 and presumably not for any C>11.

Здесь речь идёт о строго диагональных решениях.
Итак, утверждается, что строго диагональных решений C8N64, C9N81, C11N121 не существует. Дальше было сказано, что строго диагональное решение C10N100 тоже не существует.
А что можно сказать о строго диагональных решениях C12N144 и C15N225?

Если эти решения есть строго диагональные, то есть и строго "ход конём". Вот красивые должны быть решения :-) Если они существуют.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 08:16 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Решение C12N24 не строго "ход конём", сама не знаю, как умудрилась построить :D
За основу взято решение C12N12 не строго "ход конём", это решение расположено в левом верхнем квадранте 12x12.
Нельзя ли как-нибудь исхитриться аналогично построить решение C12N144 :?:

Изображение

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 08:22 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #627379 писал(а):
Изоморфны ли эти решения? Я думаю, что изоморфны.
Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую. :D

Nataly-Mak в сообщении #627379 писал(а):
whitefox
я знаю, что вы просматривали БД не строго диагональных решений в процессе её создания. А окончательный вариант БД вы смотрели? Есть ли там изоморфные решения?
Много раз меня интуиция подвела? :D
Извините, ещё не смотрел.

Nataly-Mak в сообщении #627379 писал(а):
А для строго диагональных решений этот критерий не годится?
Нет, для строго диагональных решений существует свой критерий изоморфности. Тоже сравниваются канонические базовые вектора, только построение их более сложное.

Nataly-Mak в сообщении #627429 писал(а):
Как преобразовать этот базовый вектор к каноническому виду? Что-то не соображу :-(
Выпишем из базового вектора первые появления всех чисел в том порядке, в котором они идут в базовом векторе:
Код:
1 3 4 2
Получили перестановку чисел от 1 до 4.
Применим перестановку цветов 1 4 2 3 (обратную к полученной) к исходному базовому вектору, получим канонический базовый вектор:
Код:
1 2 3 4 4 2 1 4 1 4 2 2 3 2 1

Nataly-Mak в сообщении #627429 писал(а):
Это канонический вектор?
Значит, приведённые решения неизморфные?
Да, и да.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 09:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #627487 писал(а):
Nataly-Mak в сообщении #627379 писал(а):
Изоморфны ли эти решения? Я думаю, что изоморфны.
Верно, они изоморфны.
Примените ко второй раскраске перестановку цветов 3 1 2, и Вы получите первую. :D

Да, действительно, просто; могла бы и сама догадаться :oops:
Как-то плохо у меня с перестановками получается, могу только по порядку делать замены цветов друг на друга.

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

И как? На простеньком примере можете показать?

Спасибо за разъяснения, что-то начинает проясняться с изоморфностью диагональных решений :?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение06.10.2012, 09:46 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #627493 писал(а):
Как-то плохо у меня с перестановками получается, могу только по порядку делать замены цветов друг на друга.
По известной теореме любую перестановку можно представить в виде произведения транспозиций. В частности, перестановка 3 1 2 равна последовательному выполнению замен:
1<->3, 1<->2.

Nataly-Mak в сообщении #627493 писал(а):
И как? На простеньком примере можете показать?
Покажу, но чуть позже. Сейчас занят.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 120, 121, 122, 123, 124, 125, 126 ... 130  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group