2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 78, 79, 80, 81, 82, 83, 84 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение31.07.2012, 12:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
И опять в работе решения для С=10,12,14,15,18,20,21 :D

Изображение

-- Вт июл 31, 2012 14:16:34 --

Слёзы ёжика :cry:

Бедный ёжик плачет :D А почему он плачет? Потому что он останется в третьем классе на второй год :D

Вот простой пример, который ёжик решил.
Есть 3-сильная раскраска 9х4.
Задача такая: добавить к этой раскраске 2 строки и один цвет, чтобы получилась 4-сильная раскраска 11х4.

Вот исходная 3-сильная раскраска 9х4:

Изображение

Эту задачу ёжик решает так:
первую строку приписывает из одного цвета 4 (одноцветная); получается 4-сильная раскраска 10х4. Теперь надо добавить ещё одну строку.
Ёжик загоняет раскраску 10х4 в программу Эда, добавляет рандомом 11-ую строку и удаляет все возникшие коллизии вручную

[хотя программа Эда не проверяет ошибки в С-сильной раскраске, ёжик делает это сам визуально]

Вот такая 4-сильная раскраска 11х4 получилась в результате этой процедуры:

Изображение

А теперь ёжику надо выполнить то же самое только для 17-сильной раскраски 289х18.
Ну, первую одноцветную строку (из цвета 18) ёжик, конечно, добавляет, получает 18-сильную раскраску 290х18.
А как добавить вторую строку, чтобы получить 18-сильную раскраску 291х18 :?:
Трюк с рандомом в программе Эда повторить невозможно.
Что же делать бедному ёжику? :D

Ёжику чрезвычайно интересно, существует ли красивый алгоритм для решения этой задачи?
Такой алгоритм, который можно формализовать и запрограммировать. Ну, не вручную же, в самом деле, удалять все возникшие коллизии!

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

Итак, решения для C=18,20,21 в третьем классе пока не поддаются ёжику :D

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #601450 писал(а):
Ёжику чрезвычайно интересно, существует ли красивый алгоритм для решения этой задачи?
Такой алгоритм, который можно формализовать и запрограммировать. Ну, не вручную же, в самом деле, удалять все возникшие коллизии!


Да такой алгоритм сушествует, он называется метод отжига. Но к сожалению он не всегда работает и он не очень красивый, не регулярный так сказать.

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


22/03/08

7154
Саратов
Ха! Про алгоритм отжига ёжик давным-давно знает :D

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


22/03/08

7154
Саратов
Ёжик продолжает эксперименты.
Пришла такая идея: что мешает добавить к 4-сильной раскраске 11х4 (которая принадлежит классу 3) ещё одну строку и получить 4-сильную раскраску 12х4, которая принадлежит уже классу 4? А ничего не мешает!
Загоняем 4-сильную раскраску 11х4 в программу Эда и вручную подбором делаем 4-сильную раскраску 12х4:

Изображение

Всё очень просто для маленьких С.
А теперь попробуйте-ка сделать то же самое для 9-сильной раскраски 81х10 :wink:

Алгоритм отжига пока дал 10-сильную раскраску 84х10 с 5 ошибками.

Красивого алгоритма для решения этой задачи ёжик не знает :D

-- Ср авг 01, 2012 13:00:22 --

Добавилась и четвёртая строка! Получена 4-сильная раскраска 13х4, это уже класс 5.
Эта раскраска даёт решение 17х16 4-coloring. Столбца не хватает до решения C4N17, которое не является очень простым, его искали долго.

Изображение

-- Ср авг 01, 2012 13:20:34 --

И... добавилась пятая строка! Получена 4-сильная раскраска 14х4:

Код:
4,14,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A

Эта раскраска даёт решение 18х16 4-coloring. Два столбца не хватает до максимального решения C4N18.

Так, это уже класс 6 :D
Ну и что что маленькое С, ёжик учится на простом примере :wink:

А 10-сильной раскраски 86х10 в классе 6 ни у кого нет (?)
Иначе было бы выложено решение C10N96.

-- Ср авг 01, 2012 13:31:59 --

Фантастика! Добавилась и шестая строка, вот 4-сильная раскраска 15х4:

Код:
4,15,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A,D,D,B,C


Эта раскраска даёт решение 19х16 4-coloring.
А какой максимальный прямоугольник 4-coloring? Где-то встречала при просмотре статей, но забыла. Как-то на прямоугльники почти не обращала внимание.

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


22/03/08

7154
Саратов
И последняя 4-сильная раскраска 16х4:

Код:
4,16,D,A,A,A,B,A,D,D,C,C,C,A,B,D,C,B,B,C,A,C,C,A,B,B,A,C,B,D,A,A,C,C,C,B,D,C,C,D,A,D,A,B,A,B
,B,B,B,A,D,C,D,B,A,D,D,A,D,D,B,C,D,B,C,D

Дальше у меня строки не добавляются уже так легко. Можно ли добавить ещё строку в принципе? Я этого не знаю.

Максимальный прямоугольник, полученный этим способом, 20х16 4-coloring.
Вроде есть больше прямоугольник 4-coloring? Что-то мне запомнилось число 21, вроде 21 строка максимум в прямоугольнике 4-coloring... А сколько столбцов максимум?

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


22/03/08

7154
Саратов
Такой вопрос возник: любому ли комплекту попарно ортогональных ЛК порядка n=C соответствует С-сильная раскраска? И наоборот.

Я раньше считала, что это так. Но сейчас что-то начала сомневаться.

-- Ср авг 01, 2012 20:54:19 --

Из прямоугольника 20х16 4-coloring получила оригинальное решение C4N18 с 4 дырками:

Изображение

Интересно, что окрашивание любой дырки в любой из 4 цветов даёт 4 ошибки, итого 16 ошибок при любой раскраске дырок.
Любопытное решение. Кстати, очень напоминает решение C5N30 с пустым подквадратом 5х5, который также расположен в правом нижнем углу квадрата.
А-а-а, так можно получить и аналогичное решение C4N20 с пустым подквадратом 4х4, причём это будет регулярное решение.
Ну, а у меня решение C4N18 с пустым подквадратом 2х2 нерегулярное.

Я тут давно просила показать оригинальные решение C4N18. Что-то не вижу :wink:

Есть первое решение, которое всем хорошо известно из Интернета, и второе оригинальное решение - решение Тома.

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


22/03/08

7154
Саратов
До кучи:

Изображение

Здесь тоже окрашивание любой дырки в любой из 4-х цветов даёт 4 ошибки.

-- Ср авг 01, 2012 21:38:15 --

Tom Sirgedas возглавляет большую группу джентльменов, причём уже очень давно:

Цитата:
10 Tom Sirgedas 19.638600 06-06-2012 @ 23:11:18
11 Il brigante Pennastorta 19.638600 06-08-2012 @ 08:28:33
12 Vladimir Chirkov 19.638600 07-10-2012 @ 07:04:16
13 Juha Saukkola 19.638600 07-31-2012 @ 03:06:51

Конкурсанты подтягиваются к этой группе довольно активно, на подходе конкурсант с 14-го места.
Интересно, кто первый потеснит Тома с 10-ой позиции.

-- Ср авг 01, 2012 22:08:39 --

6-сильная раскраска 27х6 (из 5-сильной раскраски 25х6) получается алгоритмом отжига мгновенно:

Изображение

Pavlovsky
как специалист по классу 3, оцените решение ёжика :wink:

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #601976 писал(а):
Я тут давно просила показать оригинальные решение C4N18. Что-то не вижу :wink:

Есть первое решение, которое всем хорошо известно из Интернета, и второе оригинальное решение - решение Тома.


Вот мои оригинальные решения для C4N18. Я не проверял насколько они отличаются от известных решений. Решения построены таким же методом как в статье Bernd Steinbach и Christian Posthoff, только вместо SAT solver я использовал метод отжига. Моя интуиция подсказывала что метод отжига гораздо легче запрограмировать и результат будет получен быстрее. Оказалось действительно так - каждое из этих решений я нашёл примерно через час/полтора (вместо 5-7 часов). Кстати вся программа достаточно маленькая, примерно 300 строчек в Java. В конце соревнования я её покажу.

(Оффтоп)

2,3,4,1,4,1,3,2,2,4,1,3,2,4,3,1,4,3,
3,3,3,4,1,2,1,4,1,1,3,2,2,2,2,1,4,4,
4,4,2,2,2,4,3,3,4,1,3,1,2,3,1,3,4,1,
2,1,4,2,3,4,2,4,3,1,1,4,1,2,3,3,1,2,
3,1,2,1,1,3,4,4,4,4,2,3,3,2,4,3,2,1,
1,1,1,4,2,2,3,2,4,3,2,4,3,4,1,1,3,2,
2,1,4,3,2,3,1,1,4,3,3,2,4,1,3,4,2,4,
4,2,2,4,1,1,2,2,3,4,3,2,3,1,1,4,1,3,
3,4,4,4,3,2,2,3,2,3,4,1,1,1,4,1,2,3,
1,4,3,2,3,3,3,2,1,4,1,4,4,1,2,2,2,1,
1,3,2,3,3,1,4,1,2,1,4,4,3,3,2,4,4,2,
2,4,2,1,3,2,4,1,1,2,3,3,1,4,1,2,3,4,
4,1,3,3,2,1,2,4,1,2,4,1,4,4,2,3,3,3,
3,4,1,2,4,1,1,4,2,2,2,2,1,3,3,4,3,1,
4,3,1,1,4,3,2,3,3,1,2,4,2,1,4,2,3,4,
3,2,1,3,1,4,3,1,3,2,1,1,2,4,4,4,2,2,
2,2,3,4,4,4,4,1,3,3,2,3,4,3,2,1,1,1,
1,2,3,1,2,4,1,3,2,4,4,1,3,2,3,2,1,4

2,1,1,4,1,4,2,1,4,4,1,3,2,3,3,2,4,3,
3,2,4,1,2,3,2,1,4,1,4,3,1,4,1,4,3,2,
1,3,1,3,4,1,4,4,4,3,2,4,1,3,2,2,1,2,
2,4,1,1,2,4,3,4,1,3,3,3,3,2,2,4,2,1,
2,3,2,1,3,1,3,4,2,4,1,2,4,4,3,1,3,2,
1,4,4,2,3,3,4,3,2,3,1,1,4,2,1,2,4,1,
2,2,3,2,1,4,4,2,3,3,2,1,1,4,4,1,3,3,
4,3,1,2,4,4,1,3,3,2,4,3,4,1,1,1,2,2,
3,4,2,2,3,2,2,1,3,4,4,4,3,3,2,1,1,1,
3,3,3,4,1,1,2,2,2,1,3,4,4,1,4,4,2,1,
4,4,3,3,3,2,1,2,4,1,1,3,2,2,4,3,1,2,
1,1,3,2,2,3,3,4,1,1,4,2,2,3,4,1,4,4,
3,2,4,3,4,2,3,3,1,4,1,2,1,1,4,2,2,3,
4,1,3,1,2,2,4,3,2,4,2,1,3,1,3,4,1,4,
3,4,2,4,4,1,1,1,1,3,2,1,2,4,3,3,2,4,
4,3,4,4,1,3,2,4,1,2,2,2,3,2,1,3,1,3,
4,1,2,3,2,3,1,2,3,2,3,4,1,4,3,2,4,1,
1,2,4,1,1,4,1,3,2,2,3,4,2,3,2,3,3,4

2,1,3,2,1,2,3,4,1,4,4,4,4,2,1,3,3,3,
2,3,3,1,1,3,4,3,2,1,4,2,2,1,4,1,4,2,
2,4,2,4,2,3,2,4,1,3,1,1,3,1,3,3,4,4,
4,3,2,4,4,1,1,2,3,3,4,3,2,4,1,1,2,3,
1,4,4,3,4,2,4,3,3,2,3,4,1,1,1,3,2,2,
3,1,2,1,4,2,1,3,4,4,1,2,3,3,2,4,4,3,
3,1,4,2,3,1,2,1,4,2,4,3,2,1,2,3,1,4,
3,3,4,3,2,4,3,1,1,2,2,2,4,4,3,1,4,1,
3,4,2,2,1,3,1,1,3,4,2,1,1,4,4,2,3,2,
4,1,4,2,2,3,3,4,2,1,3,3,1,3,4,4,2,1,
3,2,3,1,2,2,4,4,4,3,3,1,2,4,1,2,1,1,
2,3,1,4,3,4,1,2,4,2,3,4,3,1,4,2,3,1,
1,2,2,4,1,1,4,3,2,2,1,3,4,2,3,4,3,1,
4,4,1,3,3,3,2,1,4,1,1,2,4,2,1,2,2,3,
1,4,3,3,2,4,1,2,1,1,4,3,3,2,2,4,1,2,
2,2,1,1,3,1,3,3,1,3,2,4,1,4,2,4,2,4,
4,2,3,2,3,4,4,2,3,4,1,2,1,3,3,1,1,4,
1,1,1,3,4,2,2,2,2,3,2,1,4,3,4,1,3,4

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


19/12/10
1546
Nataly-Mak в сообщении #601976 писал(а):
Такой вопрос возник: любому ли комплекту попарно ортогональных ЛК порядка n=C соответствует С-сильная раскраска? И наоборот.
Если повернуть $C$-сильно окрашенный прямоугольник с числом строк $C^2$ на $90^{\circ}$ против часовой стрелки, то получится "ортогональная таблица" по Холлу.

В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lfloor N/C\rfloor\times C$, в которых последняя строка, может быть, заполнена не полностью.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #602138 писал(а):
Оказалось действительно так - каждое из этих решений я нашёл примерно через час/полтора (вместо 5-7 часов). Кстати вся программа достаточно маленькая, примерно 300 строчек в Java. В конце соревнования я её покажу.

Где-то на форуме конкурса, если ничего не путаю, было сообщение, что кому-то удаётся строить решения C4N18 за считанные секунды. Не напутала?

-- Чт авг 02, 2012 07:28:43 --

whitefox в сообщении #602139 писал(а):
Если повернуть $C$-сильно окрашенный прямоугольник с числом строк $C^2$ на $90^{\circ}$ против часовой стрелки, то получится "ортогональная таблица" по Холлу.

Спасибо.

Хотя Холла немного читала, но было это три года назад, когда занималась ЛК.
Поясните, пожалуйста, что такое "ортогональная таблица" по Холлу.

Я вчера запарилась с преобразованиями ЛК 17-го порядка.
Вроде построила полный комплект попарно ортогональных ЛК. Правда, проверить попарную ортогональноять всех ЛК не хватило терпения (программа проверки ортогональности у меня сохранилась с тех пор, когда занималась ортогональными ЛК, она много раз испытана и работает правильно), проверила только ортогональность со всеми ЛК для первых трёх ЛК.
Строю из этого комплекта ЛК 17-сильную раскраску и... она не получается 17-сильная.
Голова пошла крУгом :D

Много раз строила С-сильные раскраски из полных комплектов попарно ортогональных ЛК, несколько раз выполняла обратную процедуру: восстанавливала по С-сильной раскраске, содержащей N^2 строк и (С+1) столбцов, полный комплект из (С-1) попарно ортогональных ЛК порядка N. И была уверена, что между этими объектами существует взаимно-однозначное соответствие.
Но вчерашний эксперимент с ЛК 17-го порядка пошатнул мою уверенность :?
Что тут может быть? Не все ЛК у меня взаимно ортогональны?

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


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #602139 писал(а):
В общем случае $C$-сильно окрашенный прямоугольник $N\times M$ взаимно-однозначно соответствует комплекту из $M$ попарно ортогональных прямоугольников $\lfloor N/C\rfloor\times C$, в которых последняя строка, может быть, заполнена не полностью.


http://designtheory.org/library/encyc/mols/a/

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


22/03/08

7154
Саратов
dimkadimon в сообщении #602143 писал(а):

Эх-ма!
Эту бы ссылку да в самом начале конкурса :D
Тут как раз показано то самое "четвёртое разбиение", в поисках которого я много ночей не спала. И всё-таки нашла его сама!

-- Чт авг 02, 2012 07:51:39 --

Nataly-Mak в сообщении #589126 писал(а):
Итак, составляю разбиения:

1 группа, шаг (1,0):
{1,2,3}, {4,5,6}, {7,8,9}

2 группа, шаг (1,1):
{1,5,9}, {4,8,3}, {7,2,6}

3 группа, шаг (1,2):
{1,8,6}, {4,2,9}, {7,5,3}

Эти три группы я нашла в соответствии с описанием Pavlovsky.
О последнем разбиении я ничего не знаю, поэтому выбираю его наобум:

4 группа:
{1,4,7}, {2,5,8}, {3,6,9}

Это может быть неправильное разбиение.

Далее строю на основе этих разбиений прямоугольник 9х4 strong-3-coloring:

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

Прямоугольник получился strong-3-coloring, несмотря на то, что четвёртое разбиение я нашла не по теореме 4.12.

Это была моя маленькая победа, очень приятная! И это был всего только первый класс решений :?

Во втором классе я тоже нашла свой способ построения регулярных решений. Это была ещё одна победа.

А вот в третьем классе застряла :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #602141 писал(а):
Поясните, пожалуйста, что такое "ортогональная таблица" по Холлу.


http://www.natalimak1.narod.ru/arry.htm

Цитата:
Даже поняла, как Холл этот ортогональный массив строит.

post180671.html?sid=8afbdd961d1eab7db4e8c063d6a890a4#p180671

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


22/03/08

7154
Саратов
Ага, вот значит как :D
Было какое-то понимание ортогонального массива, когда "грызла" эти самые массивы по книге Холла :?

Надо свои статьи почитать, значит :D

Так "ортогональная таблица" это и есть тот самый ортогональный массив :?

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


21/02/10
1594
Екатеринбург
Ортогональный массив strength 2 and index 1 - это сильноокрашенный прямоугольник! Надо порыть эту тему.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 78, 79, 80, 81, 82, 83, 84 ... 130  След.

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



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

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


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

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