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

[svb]

Nataly-Mak
Пристукнула нас цензура даже в "свободном" полете, поэтому попытаюсь вернуться к основной задаче. Я никак не могу найти ничего об алгоритме отжига, который вы часто упоминаете. Это секретно или он был на форуме?

[Nataly-Mak]

svb
метод отжига упоминаю не только я.
Например:

Zealint в сообщении #589168 писал(а):

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

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

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

-- Чт авг 02, 2012 22:03:05 --

Ещё пример:

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

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

Об алгоритме отжига в Сети полно статей.

Первая попавшаяся статья:
http://www.abashin.ru/conferences/stude ... ashov2.pdf

[svb]

Nataly-Mak

Цитата:

Об алгоритме отжига в Сети полно статей.

Спасибо. Вот нашел.

[Nataly-Mak]

В Википедии:
http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B3%D0%B0

[Nataly-Mak]

О! Порадовал Alexu007:

Цитата:

41 Neil Brewer 8.628870 07-27-2012 @ 10:46:45
42 Alexu007 8.223500 08-02-2012 @ 03:51:52
43 Victor Dimitriev 7.841180 07-21-2012 @ 00:50:36

Пока он выигрывает соревнование с украинцем Виктором Димитриевым.

А на 41-ой позиции администратор конкурса, если это не совпадение имени и фамилии (?)

[Pavlovsky]

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

[Alexu007]

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

О! Порадовал Alexu007

Переписал свой рэндом с использованием леммы Nataly-Mak - то есть с помощью рэндома получаем не весь квадрат NxN, а полоску CxN по требуемым правилам - сразу легко получил результаты 4х16 и 5х25. К сожалению на этом всё и остановилось, т.к. 6х36 и более не расчитывается. И что более обидно - никак не рассчитываются меньшие квадраты (6х35, 6х34 и т.д.). Чапай думает.

[whitefox]

Alexu007
Чтобы построить решение C6N36 достаточно найти 6-сильный прямоугольник 30х6, который расширите до 30х36 по указанной лемме.
Примеры добавления 6 строк в теме уже не раз приводились.

Когда я тестировал свою программу "вытряхивания блох", то взял случайный прямоугольник 30х6. Неожиданно для себя получил из него 6-сильный. Тоже ведь рэндом.

[Alexu007]

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

Alexu007
Чтобы построить решение C6N36 достаточно найти 6-сильный прямоугольник 30х6, который расширите до 30х36 по указанной лемме.
Примеры добавления 6 строк в теме уже не раз приводились.

Не стоит задачи получить 36х36 любой ценой, т.е ручной досборкой. Потому что следующим будет 49х49 и так далее - рук не напасёшься.

Я хочу, чтобы решения за меня находила программа.

Для 16х16 и 25х25 мой алгоритм сработал, а на 36х36 и далее уже не тянет. Но меньшие то прямоугольники должен находить легко (рэндом для всего квадрата нашёл 30х30), а этот не находит даже 6х25. Значит чё-то нужно менять... в мозгах программы.

(Оффтоп)

В настоящее время комп занят вычислением двух незаполненных у меня С20 и С21 - сперва там заберу своё, а потом буду работать над улучшением результата, которое ещё неизвестно, получится или нет. Пока прорыв удался только на 4 и 5.

[Nataly-Mak]

Alexu007 в сообщении #602658 писал(а):

Не стоит задачи получить 36х36 любой ценой, т.е ручной досборкой. Потому что следующим будет 49х49 и так далее - рук не напасёшься.

Я хочу, чтобы решения за меня находила программа.

Дык там смешная досборка-то
Ну, и вставьте её в программу сразу. Вы же расширяете полоску CxN? Вот и вставьте туда эту досборку, и будет она у вас не ручная, а программная

[whitefox]

Alexu007 в сообщении #602658 писал(а):

Не стоит задачи получить 36х36 любой ценой, т.е ручной досборкой. Потому что следующим будет 49х49 и так далее - рук не напасёшься.

Речь не идёт о ручной доработке.
Способ добавления 6 строк абсолютно регулярный и программируемый.
Этим же способом Вы можете потом добавить 7 строк к прямоугольнику 42х49, полученному расширением 7-сильного 42х7.

А получить 6-сильный 34х6 или даже 32х6 у Вас не получится.
Nataly-Mak уже писала о "магическом" числе 31 для С=6.
Получить 6-сильный 31х6 можно, а с большим числом строк - уже нет.

[Nataly-Mak]

Кстати, о птичках

Меня весьма интересует вопрос: существует ли 10-сильная раскраска 84х10?

dimkadimon писал, что решение C10N94 он нашёл, а 10-сильную раскраску 84х10 не нашёл.
А кто-нибудь нашёл такую раскраску?

У меня пока такая раскраска с 5 ошибками, и хоть застрелись - эти ошибки не уничтожаются.
Я уж нашла эти 5 ошибок визуально и заменила их "дырками", чтобы проанализировать. Но, увы, ничего не прояснилось для меня Да, ошибки, да запрещённые полу-прямоугольники. Но почему от них невозможно избавиться?

Дальше взяла эту раскраску с 5 ошибками и выполнила расширение. В результате получила прямоугольник 84х100 с 50 ошибками; при каждой репликации 5 ошибок повторяются. Из этого прямоугольника получила прямоугольник 94х100, в котором тоже 50 ошибок. Выделила из него квадрат 94х94, в нём осталось, кажется, 42 ошибки.

Ну и что? Трясти этот квадрат 94х94? А ну его в болото!

-- Пт авг 03, 2012 13:48:32 --

Показываю фрагмент прямоугольника 94х100 10-color с "дырками"; в раскраске 200 дырок, если окрасить "дырки", получится 50 ошибок.

Кстати, Pavlovsky, раскраска получена из вашей 85-символьной строки.

[Alexu007]

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

А получить 6-сильный 34х6 или даже 32х6 у Вас не получится.
Nataly-Mak уже писала о "магическом" числе 31 для С=6.
Получить 6-сильный 31х6 можно, а с большим числом строк - уже нет.

У меня до 6х36 не дотягивает немного - 195 из 216. Спасибо про магические числа, может действ. дело в них, а я на алгоритм грешу (впрочем, он и меньшие не составляет).

Ну и наконец - что точно означает n-сильный? Для леммы я составляю полоски, внутри которых нет прямоугольников "аааа" и "аавв" - может это избыточное требование?

[whitefox]

Alexu007 в сообщении #602698 писал(а):

Ну и наконец - что точно означает n-сильный? Для леммы я составляю полоски, внутри которых нет прямоугольников "аааа" и "аавв" - может это избыточное требование?

Давайте в начале разберёмся, что Вы понимаете под прямоугольником 6х36?
Это прямоугольник из 6 строк и 36 столбцов?

Если это так, то такой прямоугольник (а точнее его окраска) будет 6-сильным, если он окрашен в 6 цветов и не содержит полумонохромных прямоугольников, то есть прямоугольников вида:

a  a
b  b

у которых две верхние вершины одного цвета, и две нижние тоже одного цвета (возможно другого).

Но если под 6х36 Вы понимаете прямоугольник 36х6, состоящий из 36 строк и 6 столбцов, то он не должен содержать полумонохроматические прямоугольники вида:

a  b
a  b

[Alexu007]

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

Alexu007 в сообщении #602698 писал(а):

Ну и наконец - что точно означает n-сильный? Для леммы я составляю полоски, внутри которых нет прямоугольников "аааа" и "аавв" - может это избыточное требование?

Давайте в начале разберёмся, что Вы понимаете под прямоугольником 6х36?
Это прямоугольник из 6 строк и 36 столбцов?

Если это так, то такой прямоугольник (а точнее его окраска) будет 6-сильным, если он окрашен в 6 цветов и не содержит полумонохромных прямоугольников, то есть прямоугольников вида:

a  a
b  b

у которых две верхние вершины одного цвета, и две нижние тоже одного цвета (возможно другого).

Да, я имел ввиду то же самое.