В Bundeswettberweb Infomatik 2010/2011 возникла интересная проблема:
Для фиксированного найдите минимальное k и отображение φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , так что не существует тройки ( i , j ) , ( i + l , j ) , ( i + l , j + l ) с φ ( i .
А именно, мы ищем минимальное количество цветов для треугольника, чтобы не было равномерно окрашенного равностороннего подтреугольника (на следующем рисунке показана неправильная раскраска, поскольку выделенные вершины образуют такой равномерно окрашенный равносторонний подтреугольник):
Фактически они попросили достаточно малое для n = 1000, и в решении (написанном на немецком языке) они отметили, что жадный подход дает раскраску с 27 цветами для n = 1000 , которую можно уменьшить до путем рандомизации цветов до правильное решение найдено.
Меня интересуют точные решения (для меньших ). В решении говорится, что для возврата требуется, чтобы 2 цвета были достаточными для n ∈ { 2 , 3 , 4 }, а 3 - для 5 ≤ n ≤ 17 , когда возврат уже очень медленный при n = 17 .
Сначала я попытался использовать формулировку ILP и Gurobi, чтобы получить некоторые результаты для , но это было слишком медленно (уже для n = 17 ). Затем я использовал SAT solver , потому что заметил, что существует прямая формулировка в качестве SAT-экземпляра.
При таком подходе я смог создать решение с цветами для n = 18 в течение 10 минут:
Но чтобы решить, достаточно ли цветов для n = 19, это уже слишком медленно. Есть ли другой подход, который дает точные решения для n ≥ 19 ? Конечно, мы не можем ожидать полиномиального алгоритма.
источник
Ответы:
Просто расширенный комментарий:
Вы можете взглянуть на подход, использованный Штейнбахом и Постхоффом, чтобы найти 4-цветную сетку 18x18 (и 12x21) без монохроматических прямоугольников. :
Бернд Штайнбах и Кристиан Постхофф, Решение последней открытой четырехцветной сетки без прямоугольников - чрезвычайно сложная многозначная задача . В материалах 43-го Международного симпозиума IEEE 2013 года по многозначной логике (ISMVL '13)
Еще одно замечание: я потратил недели циклов ЦП на проблему монохроматического без прямоугольника с 4-мя раскрасками, но я начал с неправильного частичного результата (неправильный предыдущий анализ, который ограничивал количество возможных одноцветных подконфигураций), и я использовал STP решатель ; Вы можете добиться значительных улучшений, если добавите ограничения, которые нарушают симметрию (например, упорядочение по раскраске стороны треугольника), и попытаетесь провести анализ возможных конфигураций, используя только один цвет.
РЕДАКТИРОВАТЬ: это результат программы STP для n = 19 (~ 1 мин.)
источник
Большое спасибо Марцио за создание изображения и за то, что он сообщил мне о проблеме! :-)
источник