Pull to refresh

Comments 75

Можно было бы уменьшить в 2 раза и поместить все одной картинкой в ряд по горизонтали.
Если быстро скроллить страницу — будет одна сплошная :) Вот она и четвертая.
UFO just landed and posted this here
Комбинаторика, значит… исправил.
Наука на стыке кибернетики и математики — кибениматика :)
простите за невежество, но какое практическое применение может быть у знания, как раскрасить матрицу 17х17 и 18х18 четырьмя цветами без монохроматических прямоугольников? оно может лежать в основе другой математической теории? я попробовал сам представить и как-то ничего толком не смог придумать. только как предмет искусства наравне с визуальными иллюзиями на стену повесить.
Задача по раскраске матрицы позволяет разработать эффективные алгоритмы, которые уже с минимальными изменениями можно применять для серьезных задач, вроде упомянутого распределения частотных каналов.
Спасибо, за пояснение. Теперь буду знать. Вобще конечно если у результата много областей применения, а сам результат не так просто найти, то такого рода «готовые решения» весьма полезны. Я по работе с такого рода задачами не сталкивался, потому и решил уточнить. Чтобы расширить кругозор.
UFO just landed and posted this here
Отметим, что раскраска графов имеет большое практическое значение и используется в составлении расписаний, распределении регистров в микропроцессорах, распределении исполняемого кода по кэшу, распределении частот в радиосвязи для максимизации пропускной способности каналов и минимизации интерференции, распараллеливании численных методов, вычислении производных, цифровых водяных знаках, кластерном анализе и многих других сферах.
Спасибо КО. :) Я дочитал уже.
капча?
выдается 3 матрицы — найти монохроматическую.пользователь, хереет, нажимает «отмена» — вуаля — вы не бот!
Блин, я под кат зашол в надежде увидеть алгоритм, а его нет…
Присоединяюсь. Неплохо было бы и алгоритм описать, а не просто ссылаться на работу.
Остается дожидаться мая. Как я понимаю, раньше мы его не увидим.
Я чего-то не понимаю в постановке задачи, или если существует такая раскраска для 18х18 (которую нашли), то автоматически появляется и для всех меньших матриц (присто отбрасыванием крайных столбцов и/или строк)?
Ну судя по всему да, к тому же и математики от меньшего к большему шли 17-18-21
Согласен. Взял эту картинку, убрал 5 столбцов справа и 5 строк снизу. Не нашел прямоугольников. Profit, не?
Посмотрите на таблицу. 18x18 — самая большая квадратная матрица из рассматриваемых. Её нашли после матрицы 17x17.
Возможные матрицы со стороной больше 18 — все прямоугольные. Из прямоугольника 20x16, например, никак не вырежешь кусок 17x17.
Есть речь про матрицу 21*21, но про20*20 и 19*19 речи нету, словно для них решение есть.
Может быть, в посте немного сумбурно написано, но в нем приводится ссылка (процитирую ее второй раз, чего уж там :) на pdf с табличкой.
Буква С в этой таблице означает, что для данной размерности решение есть.
Буква N говорит о том, что решения нет (и это доказано)
Буква U означает, что решение неизвестно, и неизвестно, есть ли оно вообще.
До недавнего момента было всего 4 таких случая: 17x17, 17x18, 18x18 и 12x21. Решения для первых трех из них теперь найдены, остался только прямоугольник 12x21.
Вы прочитали (как и я сначала) «21х12» как «21х21».
Одному мне захотелось набросать программу для нахождения 21*21?
21x12 только. Для матрицы 21x21 задача не имеет решения.
Ой, разумеется 12Х21
если бы этот алгоритм разбивал задачу на подзадачи можно было бы раздать желающим пользователям хабра с разными граничными условиями, глядишь и решили бы :) Возьмем 1000 компьютеров по 10 часов, 416 дней вычислений на вашем ПК! :)
Имеются в виду прямоугольники любого размера с рёбрами, параллельно осям x и y.

За такую формулировку с мех-мата сразу выгоняли. Например, размер 3x1 прямоугольника делает Ваше решение неверным.
в моей вселенной прямоугольник должен иметь 4 не совпадающих попарно между собой вершины. в случае 3х1 это не выполняется
Кошмар любителя игры SPB Quads и ей подобных
там в конце все такой матрицой и кончалось
Можно написать игру 12х21 для Андроида, которая в случае несуществования решения будет прикольной, простой и бесконечной, а в случае существования поможет решить математическую проблему путём казуального гейминга, что тоже по-своему уникально.
кстати да, есть же похожая штука толи про сворачивание белков, толи про разбор ДНК.
другое дело, что таким образом можно доказать существование решения (в случае если оно будет найдено), но не его несуществование
Игра с небольшим полем, в которую можно играть вечно, это тоже по-своему здорово, наверное.
А на первый взгляд кажется что это вообще не проблема написать алгоритм и получить все возможные варианты расстановки ячеек простым перебором. А затем все проверить на монохроматические прямоугольники.

Хотя на самом деле всё не так просто.
Простым перебором — это 4N2 вариантов!
Можно уменьшить в несколько раз путем учёта отражений/поворотов, но легче от этого не становится.
Я и говорил что на первый взгляд. На перекуре чуть ли не бросился писать алгоритм — хорошо что забросил. А то бы полдня точно ушло и ничего не получил.
Вот дали бы мне какой-нибудь суперкомпьютор, тогда намного интереснее делать.
UFO just landed and posted this here
Я боюсь вас огорчить… но для расчета этой задачи не хватит и всех вычислительных мощностей планеты за много-много лет (если говорить про переборный алгоритм).
а что на счет перебора с возвратом? на рекурсию много места не нужно (красим всего 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
я не думаю, что сильно удивлю, что «никак», но на всякий случай перебор так и оставил на работе запущенным, пока лучшее решение — это матрица где 19 (из 252) клеток не удалось заполнить. матрицы 13x13 и 14x14 удалось раскрасить полностью, хотя это уже давно было сделано.
Похоже, что это задача динамического программирования, не стоит всё перебирать.
И это только сгенерировать, а ещё надо каждый проверить на прямоугольники. А их там ещё больше, да ещё и в каждом варианте.
Примерно посчитал — на десктопе это будет больше 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.
Ну раз уж считать, так считать. Прямоугольник 12х21, 144*441*4^252/10^9/3600/24/365 ~ 4^252/10^12. 4^252 ~ (10^3)^50 = 10^150. Итого примерно 10^140. Но даже если брать 21х21 будет ближе к 10^200.
мне точно известно, что этот случай гораздо сложнее при 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?
Мне только одному кажется что задача в такой постановке имеет тривиальное решение:
rgbyrgbyrgbyrgbyr
gbyrgbyrgbyrgbyrg
byrgbyrgbyrgbyrgb
yrgbyrgbyrgbyrgby

и т.д.
Тщательнее нужно задачу формулировать…
а, только сейчас понял, что имел в виду автор.
У вас там 100500 четырёхугольников можно нарисовать
Вот там товарищ выше уже написал программу для перебора с учётом каких-то эвристик, а может и еще каких эвристик добавит для пущего ускорения. Если придумать, как упорядочить различные раскраски, то уже можно задачу разделять на кусочки и считать по отдельности.
А на каком основании эту матрицу называют уникальной? Разве доказано, что это единственная матрица такого размера, удовлетворяющая условиям задачи (с учетом поворотов, отражений и перестановки цветов)?
UFO just landed and posted this here
Sign up to leave a comment.

Articles