Комментарии 75
Пока читал статью, 4 раза сломал глаза об картинки
простите за невежество, но какое практическое применение может быть у знания, как раскрасить матрицу 17х17 и 18х18 четырьмя цветами без монохроматических прямоугольников? оно может лежать в основе другой математической теории? я попробовал сам представить и как-то ничего толком не смог придумать. только как предмет искусства наравне с визуальными иллюзиями на стену повесить.
Задача по раскраске матрицы позволяет разработать эффективные алгоритмы, которые уже с минимальными изменениями можно применять для серьезных задач, вроде упомянутого распределения частотных каналов.
Отметим, что раскраска графов имеет большое практическое значение и используется в составлении расписаний, распределении регистров в микропроцессорах, распределении исполняемого кода по кэшу, распределении частот в радиосвязи для максимизации пропускной способности каналов и минимизации интерференции, распараллеливании численных методов, вычислении производных, цифровых водяных знаках, кластерном анализе и многих других сферах.
капча?
выдается 3 матрицы — найти монохроматическую.пользователь, хереет, нажимает «отмена» — вуаля — вы не бот!
выдается 3 матрицы — найти монохроматическую.пользователь, хереет, нажимает «отмена» — вуаля — вы не бот!
Блин, я под кат зашол в надежде увидеть алгоритм, а его нет…
Я чего-то не понимаю в постановке задачи, или если существует такая раскраска для 18х18 (которую нашли), то автоматически появляется и для всех меньших матриц (присто отбрасыванием крайных столбцов и/или строк)?
Ну судя по всему да, к тому же и математики от меньшего к большему шли 17-18-21
Согласен. Взял эту картинку, убрал 5 столбцов справа и 5 строк снизу. Не нашел прямоугольников. Profit, не?
Посмотрите на таблицу. 18x18 — самая большая квадратная матрица из рассматриваемых. Её нашли после матрицы 17x17.
Возможные матрицы со стороной больше 18 — все прямоугольные. Из прямоугольника 20x16, например, никак не вырежешь кусок 17x17.
Возможные матрицы со стороной больше 18 — все прямоугольные. Из прямоугольника 20x16, например, никак не вырежешь кусок 17x17.
Есть речь про матрицу 21*21, но про20*20 и 19*19 речи нету, словно для них решение есть.
Может быть, в посте немного сумбурно написано, но в нем приводится ссылка (процитирую ее второй раз, чего уж там :) на pdf с табличкой.
Буква С в этой таблице означает, что для данной размерности решение есть.
Буква N говорит о том, что решения нет (и это доказано)
Буква U означает, что решение неизвестно, и неизвестно, есть ли оно вообще.
До недавнего момента было всего 4 таких случая: 17x17, 17x18, 18x18 и 12x21. Решения для первых трех из них теперь найдены, остался только прямоугольник 12x21.
Буква С в этой таблице означает, что для данной размерности решение есть.
Буква N говорит о том, что решения нет (и это доказано)
Буква U означает, что решение неизвестно, и неизвестно, есть ли оно вообще.
До недавнего момента было всего 4 таких случая: 17x17, 17x18, 18x18 и 12x21. Решения для первых трех из них теперь найдены, остался только прямоугольник 12x21.
Вы прочитали (как и я сначала) «21х12» как «21х21».
Одному мне захотелось набросать программу для нахождения 21*21?
21x12 только. Для матрицы 21x21 задача не имеет решения.
Ой, разумеется 12Х21
если бы этот алгоритм разбивал задачу на подзадачи можно было бы раздать желающим пользователям хабра с разными граничными условиями, глядишь и решили бы :) Возьмем 1000 компьютеров по 10 часов, 416 дней вычислений на вашем ПК! :)
Для этого лучше использовать BOINC.
Имеются в виду прямоугольники любого размера с рёбрами, параллельно осям x и y.
За такую формулировку с мех-мата сразу выгоняли. Например, размер 3x1 прямоугольника делает Ваше решение неверным.
За такую формулировку с мех-мата сразу выгоняли. Например, размер 3x1 прямоугольника делает Ваше решение неверным.
Кошмар любителя игры SPB Quads и ей подобных
там в конце все такой матрицой и кончалось
Можно написать игру 12х21 для Андроида, которая в случае несуществования решения будет прикольной, простой и бесконечной, а в случае существования поможет решить математическую проблему путём казуального гейминга, что тоже по-своему уникально.
кстати да, есть же похожая штука толи про сворачивание белков, толи про разбор ДНК.
другое дело, что таким образом можно доказать существование решения (в случае если оно будет найдено), но не его несуществование
другое дело, что таким образом можно доказать существование решения (в случае если оно будет найдено), но не его несуществование
Игра с небольшим полем, в которую можно играть вечно, это тоже по-своему здорово, наверное.
Тетрис? =)
В тетрис не получится играть вечно.
А на первый взгляд кажется что это вообще не проблема написать алгоритм и получить все возможные варианты расстановки ячеек простым перебором. А затем все проверить на монохроматические прямоугольники.
Хотя на самом деле всё не так просто.
Хотя на самом деле всё не так просто.
Простым перебором — это 4N2 вариантов!
Можно уменьшить в несколько раз путем учёта отражений/поворотов, но легче от этого не становится.
Я и говорил что на первый взгляд. На перекуре чуть ли не бросился писать алгоритм — хорошо что забросил. А то бы полдня точно ушло и ничего не получил.
Вот дали бы мне какой-нибудь суперкомпьютор, тогда намного интереснее делать.
а что на счет перебора с возвратом? на рекурсию много места не нужно (красим всего 21*12 клеток, по одной), при установке клетки с определенным цветом нужно проверить не образуются ли почти-прямоугольники (прямоугольник без одной вершины) этого же цвета (можно сделать быстрее, чем просмотром всех клеток; хотел написать «за линейное время», но здесь константы) и убрать из допустимого множества цветов для этой вершины текущий цвет. Здесь уже не 21^2*12^2*4^(21*12), а порядка 21*12*4^(21*12 / k). Затрудняюсь оценить точно.
«Можно сделать быстрее»: для каждой строки / столбца храним список уже раскрашенных ячеек в каждый цвет. Соответственно при попытке поставить ячейку (x,y) в цвет c смотрим foreach (a coloredX(x,c)) foreach (b in coloredY(y,c)) { считаем четвертую точку прямоугольника с вершинами a, b, (x,y), пусть это будет (x0,y0) и делаем exclude( c ) из availableColors(x0,y0). То есть время такой проверки даже не 21*12, а в худшем случае примерно (21/4)*(12/4) операций на каждую точку.
Написал по описанной схеме, матрицы 11x11 мгновенно раскалывает, 12x12 за пару минут, поставил 12x21, может повезет :)
если интересно, вот сорец: dl.dropbox.com/u/243445/ColorMatrix.cpp
если интересно, вот сорец: dl.dropbox.com/u/243445/ColorMatrix.cpp
Похоже, что это задача динамического программирования, не стоит всё перебирать.
И это только сгенерировать, а ещё надо каждый проверить на прямоугольники. А их там ещё больше, да ещё и в каждом варианте.
Примерно посчитал — на десктопе это будет больше 10^250 лет :)
Как говорится попробуй, может повезет и за 10 минут найдется нужное решение :)
Как-то многовато у вас получилось. 4 с 10 не перепутали?
Ну смотрите, очень грубое приближение, прямоугольник задаётся двумя точками, это значит что прямоугольников возможных (n^2)*(n^2), умножить на 4^(n^2) вариантов матриц, пусть это всё выполняется на 1 ГГц и каждый прямоугольник вычисляется за один такт (так как на самом деле несколько тактов, то приближение в 1 ГГц вполне нормальное). Вот и получается: (n^2)*(n^2)*4^(n^2)/10^9/3600/24/365, при n=21 ответ будет почти 2*10^254.
Так и представил Quadronix с таким игровым полем.
Что известно, если цветов != 4?
мне точно известно, что этот случай гораздо сложнее при N>4 :)
Для одного цвета могу угадать ответ. :-) Далее, для k-цветов.
Любой прямоугольник, содержащий какой-нибудь N(on-colorable), тоже очевидно N.
У любого C-прямоугольника все подпрямоугольники тоже C. Поэтому надо просто найти достаточно большие C-прямоугольники.
Для двух цветов:
2xM C(olorable)
aaa…
bbb…
3x3… 3x6 C
ababab
bbaabb
bababa
3x7 N
пусть в первой строчке больше цвета a — хотя бы четыре
в двух следующих строчках под каждой из a максимум одна a
значит есть два столбца, где во второй и третьей строчках только b
4x4… 4x6?
Любой прямоугольник, содержащий какой-нибудь N(on-colorable), тоже очевидно N.
У любого C-прямоугольника все подпрямоугольники тоже C. Поэтому надо просто найти достаточно большие C-прямоугольники.
Для двух цветов:
2xM C(olorable)
aaa…
bbb…
3x3… 3x6 C
ababab
bbaabb
bababa
3x7 N
пусть в первой строчке больше цвета a — хотя бы четыре
в двух следующих строчках под каждой из a максимум одна a
значит есть два столбца, где во второй и третьей строчках только b
4x4… 4x6?
вспомнилась игра Sbp Quads на Nokia
Мне только одному кажется что задача в такой постановке имеет тривиальное решение:
и т.д.
Тщательнее нужно задачу формулировать…
rgbyrgbyrgbyrgbyr
gbyrgbyrgbyrgbyrg
byrgbyrgbyrgbyrgb
yrgbyrgbyrgbyrgby
и т.д.
Тщательнее нужно задачу формулировать…
Вот там товарищ выше уже написал программу для перебора с учётом каких-то эвристик, а может и еще каких эвристик добавит для пущего ускорения. Если придумать, как упорядочить различные раскраски, то уже можно задачу разделять на кусочки и считать по отдельности.
А на каком основании эту матрицу называют уникальной? Разве доказано, что это единственная матрица такого размера, удовлетворяющая условиям задачи (с учетом поворотов, отражений и перестановки цветов)?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Раскраска матрицы 17х17 четырьмя цветами без монохроматических прямоугольников