2014 dxdy logo

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

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




На страницу Пред.  1 ... 24, 25, 26, 27, 28, 29, 30 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 09:44 
Аватара пользователя
Pavlovsky в сообщении #587502 писал(а):
Zealint в сообщении #587477 писал(а):
Почему бы не добавить в программу возможность работать (c,c')-coloring? Или никому не нужно?

В свете леммы Макаровой-Беляева, понятие (c,c')-coloring становится не актуальным.

Пример (6,2)-coloring допускает half-прямоугольники с ракраской сторон (1,2). Тогда можем применять лемму 4.3

Лемма Макаровой-Беляева допускает half-прямоугольники у которых одна сторона имеет четный цвет, другая нечетный (в т.ч. 1,2). Как видите усиление по сравнению с леммой 4.3 колосальное!


Значит, если я правильно понял, лемма Макаровой-Беляева это лемма 4.3 только теперь полу-прямоугольники могут иметь одну чётную сторону и одну нечётную сторону?

Давайте дадим такое определение:

Макарова-Беляев (c,c')-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B

1) A!=B
2) 1<= A, B <= c'
3) A mod 2 != B mod 2

3) сильнее 1), поэтому получаем:

1) 1<= A, B <= c'
2) A mod 2 != B mod 2

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 09:50 
Аватара пользователя
dimkadimon в сообщении #587515 писал(а):
Значит, если я правильно понял, лемма Макаровой-Беляева это лемма 4.3 только теперь полу-прямоугольники могут иметь одну чётную сторону и одну нечётную сторону?


Верно когда c'=2.

-- Чт июн 21, 2012 11:53:05 --

dimkadimon в сообщении #587515 писал(а):
Макарова-Беляев (c,c')-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B

Не так

Макарова-Беляев (c,k)-coloring это когда в каждом полу-прямоугольнике с левой стороной цвета A и правой стороной цвета B. A и B дают различные остатки при делении на k. В частном случае, при k=2 имеют разную четность.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 09:59 
Аватара пользователя
Цитата:
Вот набор из 25 непересекающихся комбинаций из чисел 1,2,3,4,5:

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

Найден форумчанином на форуме nazva.net

Очень красивые комбинации! Закономерность и гармония!

И решение по базовому алгоритму №1 из этого набора получается элементарно.
Я даже нашла и изложила здесь два способа, как этот прямоугольник 25х5 strong-5-coloring превратить в квадрат 25х25 5-coloring. Оба способа очень простые в реализации.

Может быть, расскажете ваш четвёртый метод для С=5?
Научное любопытство :-)


Вот это очень красивое решение! Я написал программу которая генерирует такие strong c-coloring для С^2 х С для простых С.

Мой четвёртый метод для 25х25 5-coloring совершено другой. Он скорее ближе к методу из статьи Немцов. Кстати, а почему никто не обсуждает эту статью?

Удивительно что столько разных решений для простых С, но они все приводят к одному результату - ни один квадрат не получаеться увеличить!

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:06 
Аватара пользователя
dimkadimon в сообщении #587519 писал(а):
статьи Немцов

Это где? Чего то не видел этой статьи.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:10 
Аватара пользователя
Pavlovsky в сообщении #587521 писал(а):
dimkadimon в сообщении #587519 писал(а):
статьи Немцов

Это где? Чего то не видел этой статьи.


На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:14 
Аватара пользователя
Аааа! Немцов=НемцЕв!

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:22 
Аватара пользователя
Pavlovsky в сообщении #587523 писал(а):
Аааа! Немцов=НемцЕв!


Ах да... я просто плохо по Русски пишу...

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:24 
Аватара пользователя
dimkadimon в сообщении #587522 писал(а):
На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

Несколько раз просмотрел эти статьи. Ничего интересного, кроме конечного результата, не увидел. Надо будет еще раз внимательно прочитать эти статьи.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:31 
Аватара пользователя
dimkadimon в сообщении #587527 писал(а):
Pavlovsky в сообщении #587523 писал(а):
Аааа! Немцов=НемцЕв!


Ах да... я просто плохо по Русски пишу...

Вы довольно хорошо пишете по-русски. По крайней мере, я вас очень хорошо понимаю.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:40 
Аватара пользователя
Nataly-Mak в сообщении #587531 писал(а):
dimkadimon в сообщении #587527 писал(а):
Pavlovsky в сообщении #587523 писал(а):
Аааа! Немцов=НемцЕв!


Ах да... я просто плохо по Русски пишу...

Вы довольно хорошо пишете по-русски. По крайней мере, я вас очень хорошо понимаю.


Спасибо - это приятно. Я только до 4ого класса учился в России, а потом учился по Русским учебникам и писал письма бабушкам. Поэтому Русский язык у меня немного страдает и постепенно забывается :(

-- 21.06.2012, 16:28 --

Pavlovsky в сообщении #587528 писал(а):
dimkadimon в сообщении #587522 писал(а):
На главном сайте выложены 3 статьи немцов. Их зовут Bernd Steinbach и Christian Posthoff. После 2.5 года поиска они первые нашли 17х17 и 18х18 4-coloring.

Несколько раз просмотрел эти статьи. Ничего интересного, кроме конечного результата, не увидел. Надо будет еще раз внимательно прочитать эти статьи.


В принципе сам метод (через SAT solver) у них очень скучный и некрасивый. Но они изобрели один трюк который уменьшил количество комбинаций цветов от 4^(18х18) до 4^(18х18/4) и это очень красиво. Очень хотелось бы обсудить этот трюк.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 10:57 
Аватара пользователя
dimkadimon в сообщении #587534 писал(а):
количество комбинаций цветов от 4^(18х18) до 4^(18х18/4)


Если в C-coloring прямоуголньнике поменять две строки (колонки) местми, то полученный прямоугольник тоже будет C-coloring. То есть можно искать прямоугольники, где номера цветов в первой строке и в первой колонке составляют неубывающую последовательность. Не считал, но по первым прикидкам количество вариантов (для квадрата 18х18 С=4) получится гораздо меньше 4^(18х18/4).

Еще раз рекомендую книгу Ф.Кортеси "Введение в конечные геометрии". В ней описывается механизм Г-таблиц. Умелое использование этого механизма может дать катострофическое уменьшение узлов в дереве перебора.

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 11:10 
Аватара пользователя
Решение C=5, N=20x20, не максимальное, но очень изящное.
Тоже интернетовское.
Наверное, регулярное :?:

Изображение

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 12:23 
Аватара пользователя
Вот балда! Надо же было так долго мучиться, чтобы понять, откуда берутся уникальные перестановки :-)

Сейчас посмотрела в черновики. Решение C=5, N=25x25 я строила методом, описанным Pavlovsky в самом начале темы.
Искала разбиения, потом по этим разбиениям строила прямоугольник 25х5 strong-5-coloring, вот какой прямоугольник у меня получился:

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

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

Изображение

Бывает же такое затмение разума, когда не видишь очевидного :D

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 13:01 
Аватара пользователя
Nataly-Mak в сообщении #587539 писал(а):
Решение C=5, N=20x20, не максимальное, но очень изящное.
Аналогичное имеется и для C=5, N=25x25, и даже для C=6, N=36x36 :-)

 
 
 
 Re: Новый конкурс программистов
Сообщение21.06.2012, 13:25 
Аватара пользователя
svb
так и заставите меня придумать решение C=6, N=36x36 :D
а я уж решила остановиться на N=31x31.
Ну, не лезет мне в голову это "36" :?

 
 
 [ Сообщений: 1937 ]  На страницу Пред.  1 ... 24, 25, 26, 27, 28, 29, 30 ... 130  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group