Минимальное количество цветов, предотвращающее равносторонний равномерно окрашенный подтреугольник

13

В Bundeswettberweb Infomatik 2010/2011 возникла интересная проблема:

Для фиксированного найдите минимальное k и отображение φ : { ( i , j ) | i j n } { 1 , , k } , так что не существует тройки ( i , j ) , ( i + l , j ) , ( i + l , j + l ) с φ ( iNКφ:{(я,J)|яJN}{1,...,К}(я,J),(я+L,J),(я+L,J+L) .φ(я,J)знак равноφ(я+L,J)знак равноφ(я+L,J+L)

А именно, мы ищем минимальное количество цветов для треугольника, чтобы не было равномерно окрашенного равностороннего подтреугольника (на следующем рисунке показана неправильная раскраска, поскольку выделенные вершины образуют такой равномерно окрашенный равносторонний подтреугольник):

                              пример

Фактически они попросили достаточно малое для n = 1000, и в решении (написанном на немецком языке) они отметили, что жадный подход дает раскраску с 27 цветами для n = 1000 , которую можно уменьшить доКNзнак равно100027Nзнак равно1000 путем рандомизации цветов до правильное решение найдено.15

Меня интересуют точные решения (для меньших ). В решении говорится, что для возврата требуется, чтобы 2 цвета были достаточными для n { 2 , 3 , 4 }, а 3 - для 5 n 17 , когда возврат уже очень медленный при n = 17 .N2N{2,3,4}35N17Nзнак равно17

Сначала я попытался использовать формулировку ILP и Gurobi, чтобы получить некоторые результаты для , но это было слишком медленно (уже для n = 17 ). Затем я использовал SAT solver , потому что заметил, что существует прямая формулировка в качестве SAT-экземпляра.N>17Nзнак равно17

При таком подходе я смог создать решение с цветами для n = 18 в течение 10 минут:3Nзнак равно1810

                              Решение с 3 цветами на 18 узлов

Но чтобы решить, достаточно ли цветов для n = 19, это уже слишком медленно. Есть ли другой подход, который дает точные решения для n 19 ? Конечно, мы не можем ожидать полиномиального алгоритма.3Nзнак равно19N19

Листинг
источник
интересный вопрос. почему вы говорите, что мы не можем ожидать алгоритм полиномиального времени?
Сашо Николов
@SashoNikolov это просто предположение, потому что это кажется сложнее, чем найти правильную раскраску вершин (сложнее с точки зрения большего количества ограничений), и раскраска вершин уже является очень сложной задачей.
Объявление

Ответы:

10

Просто расширенный комментарий:

Вы можете взглянуть на подход, использованный Штейнбахом и Постхоффом, чтобы найти 4-цветную сетку 18x18 (и 12x21) без монохроматических прямоугольников. :

Бернд Штайнбах и Кристиан Постхофф, Решение последней открытой четырехцветной сетки без прямоугольников - чрезвычайно сложная многозначная задача . В материалах 43-го Международного симпозиума IEEE 2013 года по многозначной логике (ISMVL '13)

сN×м

Еще одно замечание: я потратил недели циклов ЦП на проблему монохроматического без прямоугольника с 4-мя раскрасками, но я начал с неправильного частичного результата (неправильный предыдущий анализ, который ограничивал количество возможных одноцветных подконфигураций), и я использовал STP решатель ; Вы можете добиться значительных улучшений, если добавите ограничения, которые нарушают симметрию (например, упорядочение по раскраске стороны треугольника), и попытаетесь провести анализ возможных конфигураций, используя только один цвет.

РЕДАКТИРОВАТЬ: это результат программы STP для n = 19 (~ 1 мин.)

введите описание изображения здесь

Марцио де Биаси
источник
Nзнак равно19
4

N22Nзнак равно22Nзнак равно23Nзнак равно23Nзнак равно23

Nзнак равно19Nзнак равно23

Nзнак равно22

tri22-золь

Большое спасибо Марцио за создание изображения и за то, что он сообщил мне о проблеме! :-)

Юхо
источник