2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 33, 34, 35, 36, 37, 38, 39 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 03:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #588914 писал(а):
dimkadimon в сообщении #588905 писал(а):
А что значит ход конем? Не понимаю как вы составили ето решение.

Вы не играете в шахматы? :-)

-- Пн июн 25, 2012 17:22:36 --

dimkadimon
а почему же вы не ответили на мой вопрос о прямоугольниках C^2x(C^2+C) C-coloring, которые я построила и показала? :D
Вы не знаете ответ?

Вот сейчас построила четвёртый вариант прямоугольника 9х12 3-coloring.
Показываю:

Изображение

Этот вариант правильный? То есть соответствует ли он алгоритму теоремы 4.12?

Он мне нравится больше первых трёх вариантов :D


Я не играю в шахматы, но знаю что такое ход конём. Я понимаю что от одной к клетке к следующей мы делаем ход конём, но как сделать это для всех цветов и построить весь квадрат?

Я ваши построения 9х12 не проверял. Для С^2 х С^2 мы находим разбиения использую ходы (1,а), где 0<=а<С. Чтобы получить С^2 х (С^2+С) надо найти ещё одно разбиение, то есть найти ещё один ход (б,а).

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


22/03/08

7154
Саратов
dimkadimon в сообщении #589118 писал(а):
Для С^2 х С^2 мы находим разбиения использую ходы (1,а), где 0<=а<С. Чтобы получить С^2 х (С^2+С) надо найти ещё одно разбиение, то есть найти ещё один ход (б,а).

Вы вчера это уже писали :D

Цитата:
Построение прямоугольника С^2+С основано на построении С^2. Если вы поняли как строить С^2 по 4.12 то остался всего лишь один шаг до (С^2+С) х С^2. Если точнее то вам осталось найти ещё одно разбиение...

Вам не надоело повторяться?

Точно так же, как вы не видите очевидный ход конём в построенном мной квадрате, я не вижу "ещё одно разбиение".
Я просто о нём ничего не знаю. Какие должны быть (б,а) в последнем разбиении? (это я уже сама себя спрашиваю :-) ). Как можно что-то найти, совершенно не зная, как это надо искать???
В первых разбиениях шаги у нас такие: (1,0), (1,1), ... (1,С-1). Об этом писал Pavlovsky, и это я знаю. Вы это ещё раз написали. А зачем, если это уже давно известно по сообщению Pavlovsky?!

Давайте уже оставим мои прямоугольники!
А то вы в третий раз будете писать, как их строить, вместо того, чтобы ответить на вопрос: правильно ли я их строю? И если неправильно, в чём моя ошибка.

Понимаете, я ведь решаю задачу! Но не знаю, в чём мои ошибки. Прямоугольники у меня все получаются C-coloring. Но они могут быть не такие, какие получаются по теореме 4.12. Я их могу очень много построить, но всё это будет неправильно. А как правильно, не знаю.

Так, всё, хватит! Надоели ваши повторения. Как попугай твердите: "разбиения, разбиения, разбиения..."
Похоже, вас эти разбиения тоже сильно "достали" :D

Я накладываю вето на этот вопрос. Прошу вас не писать о нём больше, в смысле ответов на мои вопросы.

-- Вт июн 26, 2012 06:58:54 --

И напоследок... пример.
Как я построила тот прямоугольник 9х12 3-coloring, который вы только что здесь продублировали из моего вчерашнего сообщения.

Итак, составляю разбиения:

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.

Наконец, превращаю этот прямоугольник в прямоугольник 9х12 3-coloring. Это можно сделать двумя способами. Я выбираю замены по схеме:

1 -> 2
2 -> 3
3 -> 1

Готовый прямоугольник 9х12 3-coloring:

Код:
12,9,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,B,C,A,B,C,A,B,C,A,B,C,
A,A,B,C,B,C,A,A,B,C,C,A,B,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,C,A,B,C,A,B,A,B,C,C,A,B,B,C,A,A
,B,C,C,A,B,C,A,B,A,B,C,B,C,A,B,C,A

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


21/02/10
1594
Екатеринбург
Zealint в сообщении #588966 писал(а):
Pavlovsky в сообщении #588744 писал(а):
По лемме есть возможность построить диагональное решение 10х10 для С=3, 18х18 для С=4, 28х28 для С=5. Есть над чем поразмыслить.

А что-то у меня diag-10x10 для C=3 не построилось : ( Вроде все варианты перебрал. А кто-нибудь построил?


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

-- Вт июн 26, 2012 08:07:55 --

Nataly-Mak в сообщении #588993 писал(а):
Zealint
Pavlovsky в сообщении #588417 писал(а):
Пример
G(3,9) 6 > 17/3 решение может существовать
G(3,10) 6 < 19/3 решение не существует

Как я поняла, здесь утверждается, что диагональное решение C=3, N=10x10 не существует.

Хотя в более поздних исследованиях Pavlovsky оно вроде как и может существовать :-)


В более поздних исследованиях, перебором установил, что F(10)=7, а не 6. Тогда получается что существует возможность построить диагональное решение C=3, N=10x10 . Вчерашние более точные исследования подтвердили эту оценку.

-- Вт июн 26, 2012 08:10:42 --

Nataly-Mak в сообщении #589014 писал(а):
Да тут вроде не так много всех вариантов, даже если рассматривать характеристическую строку (по терминологии Pavlovsky) длины 2n-1, всего строка из 19 элементов получается.Далее, если не ошибаюсь (мозги уже набекрень от прямоугольников ) число сочетаний из 19 по 3 равно 969.


3^19 вариантов

-- Вт июн 26, 2012 08:22:06 --

Цитата:
И напоследок... пример.
Как я построила тот прямоугольник 9х12 3-coloring, который вы только что здесь продублировали из моего вчерашнего сообщения.

Итак, составляю разбиения:

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.

Наконец, превращаю этот прямоугольник в прямоугольник 9х12 3-coloring. Это можно сделать двумя способами. Я выбираю замены по схеме:

1 -> 2
2 -> 3
3 -> 1

Готовый прямоугольник 9х12 3-coloring:

Код:
12,9,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,B,C,A,B,C,A,B,C,A,B,C,
A,A,B,C,B,C,A,A,B,C,C,A,B,C,A,B,B,C,A,C,A,B,A,B,C,B,C,A,C,A,B,C,A,B,C,A,B,A,B,C,C,A,B,B,C,A,A
,B,C,C,A,B,C,A,B,A,B,C,B,C,A,B,C,A


Ну наконец то вы нашли что надо. А то больно смотреть как вы мучаетесь. А подсказать нельзя.

-- Вт июн 26, 2012 08:26:52 --

svb в сообщении #589109 писал(а):
thesis.pdf - только что нашел.

-- Вт июн 26, 2012 01:20:57 --

rectangle-free-grid-coloring-21x12-grid



Хорошие ссылки. Во второй ссылке увидел Г-таблицы (по Картеси). Пока отложил исследования Г-Таблиц, ради поиска диагональных решений.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #589133 писал(а):
Ну наконец то вы нашли что надо. А то больно смотреть как вы мучаетесь. А подсказать нельзя.

(Оффтоп)

Ах, Pavlovsky!
Где же вы были, когда я впервые задала этот вопрос?
Гораздо позже меня этот же вопрос задал dimkadimon, и тут вы сразу выложили подсказку! Это было очень красиво! Я восхищена вашим поступком! :wink:
Ещё более красивым был взлёт dimkadimon после вашей подсказки, с 24-го места на 2-ое! Такое бывает редко.

Вам не больно смотреть, как я мучаюсь, вы наслаждаетесь этим :D

Кстати, мне последний вариант прямоугольника 9х12 3-coloring очень понравился. Но я ещё не пыталась его достраивать до квадрата. Прямо боюсь начинать, вдруг опять не получится достраивание :-) Так что, "мучения" мои ещё не закончились.

Удивил перенос на торе диагонального решения C=5, N=17x17.
Вопреки моему предположению квадрат остался 5-coloring, только диагональность в нём несколько нарушилась:

Изображение

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #589134 писал(а):
"мучения" мои ещё не закончились.

Творческие мучения полезны для поддержания формы серых клеточек. (с) Эркюль Пуаро

-- Вт июн 26, 2012 09:16:44 --

Nataly-Mak в сообщении #589134 писал(а):
Удивил перенос на торе диагонального решения C=5, N=17x17.Вопреки моему предположению квадрат остался 5-coloring,


Перенос на торе эквивалентен перестановкам строк и колонок квадрата. Очевидно, что при этих перестановках свойство C-coloring сохраняется.

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


22/03/08

7154
Саратов
Вот-вот! Так что же "больно смотреть"? :-)
Восхищайтесь моими "творческими мучениями"!

Что лучше?
а) прочитать готовую теорему и по ней всё построить;
б) не читать готовую теорему, и хоть что-то построить.

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

Правда, я ещё не сделала последний шаг (достраивание прямоугольника до квадрата), может, и не сделаю. Но мне вполне достаточно того, что уже сделала.

-- Вт июн 26, 2012 08:27:06 --

Pavlovsky в сообщении #589133 писал(а):
Nataly-Mak в сообщении #589014 писал(а):
Да тут вроде не так много всех вариантов, даже если рассматривать характеристическую строку (по терминологии Pavlovsky) длины 2n-1, всего строка из 19 элементов получается.Далее, если не ошибаюсь (мозги уже набекрень от прямоугольников ) число сочетаний из 19 по 3 равно 969.


3^19 вариантов

Ого!

Zealint
и вы перебрали все эти варианты?

-- Вт июн 26, 2012 08:29:41 --

Pavlovsky в сообщении #589136 писал(а):
Перенос на торе эквивалентен перестановкам строк и колонок квадрата. Очевидно, что при этих перестановках свойство C-coloring сохраняется.

Действительно! А я как-то об этом не подумала.
Ну, то-то же - открыла Америку :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #589137 писал(а):
Ого! Zealint и вы перебрали все эти варианты?

Эта задача отличается от предыдущих, тем что перебор практически мгновенно достигает астрономического количества вариантов. Как люди перебором что то находят - не понятно. Даже достраивание одной строки требует перебора огромного количства вариантов. Интересно как Алексей Чернов смог найти рекордное решение для С=21?????

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #589143 писал(а):
Как люди перебором что то находят - не понятно. Даже достраивание одной строки требует перебора огромного количства вариантов. Интересно как Алексей Чернов смог найти рекордное решение для С=21?????

Zealint в самом начале темы писал о своей "переборной" программе для C=21.
Очень её хвалил :-)
Потом добавил, что, конечно, это не совсем тупой перебор.
Вот именно! Это не совсем тупой перебор и даже совсем не тупой перебор.

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

У меня тоже в самом начале выявился некий метод наращивания решения для C=21. Я о нём здесь писала. Этот метод основан на циклическом сдвиге.
Я вручную этим методом построила довольно много квадратов для С=21, сейчас не помню, до какого квадрата дошла.
Но программно метод не реализовала. Возможно, он мог бы дать неплохие результаты.

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #589143 писал(а):
Nataly-Mak в сообщении #589137 писал(а):
Ого! Zealint и вы перебрали все эти варианты?

Эта задача отличается от предыдущих, тем что перебор практически мгновенно достигает астрономического количества вариантов. Как люди перебором что то находят - не понятно. Даже достраивание одной строки требует перебора огромного количства вариантов. Интересно как Алексей Чернов смог найти рекордное решение для С=21?????


Я предполагаю что Алексей нашёл метод который даёт почти-решения (с маленьким количеством ошибок) для С+2, где С простое. Я думаю этот метод похожий на тот который описал Herbert. Потом он эти решения доводит до правильных. Полный перебор конечно невозможен, но есть другие методы типа генетических алгоритмов. Я теперь пытаюсь сделать что-то похожее.

-- 26.06.2012, 14:16 --

Nataly-Mak в сообщении #589046 писал(а):
Цитата:
1 Alex Chernov 19.953100 06-24-2012 @ 09:12:15
2 Dmitry Kamenetsky 19.900100 06-22-2012 @ 07:14:03
3 Herbert Kociemba 19.886500 06-20-2012 @ 19:23:52
4 Nick Gardner 19.850900 06-21-2012 @ 07:41:06
5 Artem Karavaev 19.823400 06-24-2012 @ 06:23:02
6 Tom Sirgedas 19.777600 06-06-2012 @ 23:11:18
7 Il brigante Pennastorta 19.777600 06-08-2012 @ 08:28:33
8 Valery Pavlovsky 19.777600 06-15-2012 @ 03:02:58
9 Michael van Fondern 19.362900 06-13-2012 @ 16:27:57
10 Jim Gillogly 19.221000 06-18-2012 @ 04:45:09
11 Jarek Wroblewski 19.119200 06-04-2012 @ 00:14:00
12 Anton Voropaev 19.119200 06-04-2012 @ 07:38:59
13 Wes Sampson 18.958500 06-09-2012 @ 23:54:57
14 Sigi S 18.922900 06-21-2012 @ 13:36:50
15 Natalya Makarova 18.887100 06-23-2012 @ 04:02:34
16 Juha Saukkola 18.824800 06-24-2012 @ 18:24:30
17 Roy van Rijn 18.560600 06-24-2012 @ 05:29:15
18 Martin Richardt 18.547400 06-23-2012 @ 11:12:50
19 Aicke Hinrichs 18.410900 06-21-2012 @ 16:52:34
20 Markus Egli 18.408700 06-11-2012 @ 07:51:59

Пока в первой двадцатке пятеро россиян.


А можно я тоже буду считаться россиянином? Всё таки я родился в Москве и говорю по русски :)

-- 26.06.2012, 14:23 --

Nataly-Mak в сообщении #589148 писал(а):
Pavlovsky в сообщении #589143 писал(а):
Как люди перебором что то находят - не понятно. Даже достраивание одной строки требует перебора огромного количства вариантов. Интересно как Алексей Чернов смог найти рекордное решение для С=21?????

Zealint в самом начале темы писал о своей "переборной" программе для C=21.
Очень её хвалил :-)
Потом добавил, что, конечно, это не совсем тупой перебор.
Вот именно! Это не совсем тупой перебор и даже совсем не тупой перебор.


Оригинально мы с Нилом хотели сделать С=2 до 26. Хорошо что решили сбавить до 21ого. Самое смешное что я тогда не знал про решения С^2 х С^2. Мой самый лучший результат для С=21 был 219х219. Я был почти уверен что С=21 не будет намного больше чем 250... но моё мнение быстро изменилось после первого дня :)

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #589157 писал(а):
А можно я тоже буду считаться россиянином? Всё таки я родился в Москве и говорю по русски :)


Австралийцем быть прикольнее. Хочу в Австралию. Ведь там живут антиподы (Алиса в стране чудес).

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


02/05/10
26
У меня нет ни одного решения, полученного перебором. По крайней мере для одного вида решений для простых C очевидно, что при добавлении одного цвета можно увеличить размер на (C+1). Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу. При добавлении двух цветов размер можно увеличить уже на (C+1)+k. На текущий момент я знаю как
сделать k=8.

Что касается диагональных решений, то G(3,10) у меня тоже не нашлось. Если нигде не ошибся, можно заполнить максимум 13 диагоналей :13: 0 0 1 0 2 2 1 2 1 1 0 0 2

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 09:19 


26/01/10
959
Pavlovsky в сообщении #589133 писал(а):
"Возможность" не означает, что такое решение существует. Лема гарантированно может выдать только отрицательный результат. К тому же я писал, что оценка по лемме слишком оптимистичная.

Я имел в виду, что возможности нет, так как я перебрал все варианты. Либо ошибся в программе, хотя лет 5 назад ещё помню, что никогда не ошибался при написании кода (даже не отлаживал).

Nataly-Mak в сообщении #589148 писал(а):
Zealint в самом начале темы писал о своей "переборной" программе для C=21.
Очень её хвалил :-)
Потом добавил, что, конечно, это не совсем тупой перебор.
Вот именно! Это не совсем тупой перебор и даже совсем не тупой перебор.


Метод отжига там. Отжигаю по-полной : )

Nataly-Mak в сообщении #589137 писал(а):
Ого!

Zealint
и вы перебрали все эти варианты?


Их там не 3^19 вовсе, а гораздо меньше. Ведь запрещены 3 одинаковых диагонали подряд. Тем более, что 3^19 разве лишь немногим больше миллиарда - детское число. Но повторюсь, что мог ошибиться при наложении фильтров.

alexBlack в сообщении #589166 писал(а):
Что касается диагональных решений, то G(3,10) у меня тоже не нашлось. Если нигде не ошибся, можно заполнить максимум 13 диагоналей :13: 0 0 1 0 2 2 1 2 1 1 0 0 2

Да, у меня такое же решение. Так что двое нас. Надо усиливать лемму.

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


21/02/10
1594
Екатеринбург
Zealint в сообщении #589168 писал(а):
Надо усиливать лемму.

Этим сейчас и занимаюсь. Вечером напишу код и постараюсь, в качестве тестового, найти решение 18х18 для С=4. Сейчас у меня есть решение раскраски в два цвета по 9 диагоналей для каждого цвета. Получается, что пусть в притык, такое решение возможно. Если все получится, буду искать решение 40х40 для С=6. В квадрате 40х40 раскрасить 28 диагоналей в два цвета возможно. Остается окрасить оставшиеся 79-28=51 диагонали в четыре цвета.

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


22/03/08

7154
Саратов
alexBlack в сообщении #589166 писал(а):
У меня нет ни одного решения, полученного перебором.

Zealint
Вот вам блестящее подтверждение того, что не все, кто вышел за пределы джентльменского набора решений, являются "достраивателями" в смысле простого переборного достраивания, хотя бы и с отжигом.

Я так и предполагала. Помните, писала о рекордах alexBlack: "Если это и достраивание, то очень хитрое достраивание". И при таком достраивании получается нечто вполне регулярное.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.06.2012, 09:51 


26/01/10
959
Цитата:
Zealint
Вот вам блестящее подтверждение того, что не все, кто вышел за пределы джентльменского набора решений, являются "достраивателями" в смысле простого переборного достраивания, хотя бы и с отжигом.

Ну и хорошо. Но все равно это достраивание имеющегося решения, а не уникальное новое решение. Пусть и не переборное.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 33, 34, 35, 36, 37, 38, 39 ... 130  След.

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



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

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


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

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