Al Zimmermann's: Summertime

[Archimedes]

19.06.2021 объявлен старт нового конкурса от Al Zimmermann'а.
На момент создания этой темы конкретики нет, есть только название.
Предлагаю, как и раньше, делиться в этой теме своими соображениями, если, конечно, вы готовы к этому.
И ещё, если вы собираетесь участвовать в конкурсе, советую побеспокоиться о компьютере, программном обеспечении и свободном времени.
Всем удачи!

[dimkadimon]

 Конкурс стартовал, но такое впечатление что он уже закончился так как 3 человека набрали 25.00 :(

[dmd]

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

Тогда сразу стоит подумать - а как бы Вы предложили модифицировать задачу, чтоб она стала сложнее.

[dimkadimon]

Уже не остается сомнений что эта задача решена полностью. Я уже спросил у Ала о модификации. Он написал что он будет усложнять задачу, но пока не знает как. Либо больше вершин, либо больше цветов или крупнее клики (правильное слово?).

[dmd]

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

А что подразумевается под кликами (cliques) в данном контексте?

[kotenok gav]

dmd в сообщении #1523524 писал(а):

А что подразумевается под кликами (cliques) в данном контексте?

Если я правильно понял - треугольники. Т.е. dimkadimon предлагает рассматривать не монохроматические треугольники, а монохроматические $K_4$, $K_5$, и другие.

[dimkadimon]

kotenok gav в сообщении #1523525 писал(а):

dmd в сообщении #1523524 писал(а):

А что подразумевается под кликами (cliques) в данном контексте?

Если я правильно понял - треугольники. Т.е. dimkadimon предлагает рассматривать не монохроматические треугольники, а монохроматические $K_4$, $K_5$, и другие.

Верно. Или можно рассматривать четырехугольники.

Можно вообще монохроность убрать. Например можно максимизировать количество четырехугольников где все стороны разного цвета :)

[dimkadimon]

Оказывается не так просто найти оптимальные решения...

[Vovka17]

dimkadimon, попробуйте подумать в таком направлении:
1) Предположим, что у нас есть идеальное решение для $N$ (в котором нет монохроматических треугольников). Это возможно только при $N\leqslant16$, но это не важно.
2) Что нам надо сделать, чтобы получить из него идеальное решение для $N-1$? (Это элементарно!)
3)Далее подумайте как из какого-нибудь текущего наилучшего решения для $N$(с минимально возможным числом треугольников, но уже не нулевым) сделать минимально возможное число ошибок для $N-1$...
Эти рассуждения должны натолкнуть вас на ключ к решению.
Удачи!

[dimkadimon]

Vovka17 спасибо за советы.

Я наконец нашел все оптимальные решения. Первые 22 нашел методом отжига, а вот последние три никак не мог найти. Потом увидел статью (https://doi.org/10.1016/j.jctb.2013.05.002) и ее обсуждение и последние решения нашлись очень легко - буквально несколько строчек кода.

Теперь начал думать о более интересной задачи. Найдите самой большой граф $K_n$ раскрашенный в $C$ цвета чтобы в нем не было монохромный треугольников.

[Herbert Kociemba]

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

Теперь начал думать о более интересной задачи. Найдите самой большой граф $K_n$ раскрашенный в $C$ цвета чтобы в нем не было монохромный треугольников.

Hi Dmitry, welcome to the Club 25! I think there already has been much research on the subject you intend to study now so I do not think there is a big chance to find improvements there.
I preferred trying to find the solution for N=19 with only 15 monochromatic triangles and finally managed to find it today. Simple annealing by swapping edges did not do the job, I needed a little extra idea. My solution has 57 edges of each color but since some edges can be recolored without changing the number of triangles this surely is not mandatory.

[dmd]

Существует ли решение N16=1?

Мой способ построения решения был добавление/удаление точки (вершины) в текущем графе. Начинаю с графа с рандомной расцветкой рёбер. Ищу в нём точку, которая даёт наибольшее число одноцветных треугольников, удаляю ее, и на её место добавляю точку с произвольными (или одноцветными) рёбрами, затем запускаю перебор только над добавленными ребрами, и затем снова в полученном графе ищу точку с наибольшим числом одноцветников для ее удаления. Другой способ - построение серии всех решений начиная с минимального и оптимального, который легко построить, выполняя только добавления точки, тоже с перебором только над добавленными рёбрами, т.к. остальные рёбра уже локально-оптимальны. Таким образом получилось построить все текущие решения (кроме N17=5), стартуя с графа N19=17, который легко построить первым способом.

Способом добавления точки у меня легко строится серия N16=0 => N17=5 => N18=10 => N19=15 => N20=20 => N21=25 => N22=33 => N23=41 =>...

Легко могу найти все стартовые графы N16>=2, а также любые N15, N14, N12, N11, N10. Но вот N16=1 почему то никак не поддаётся.

[Vovka17]

dimkadimon, не сомневался, что у Вас получится!

Думаю, можно рассказать вкратце мой алгоритм, несмотря на продолжающийся конкурс.
Если честно, то я так и не добрался ни до отжига, ни до других алгоритмов, ни до изучения вопроса более глубоко.
Всё, что я сделал:
1) Строил первоначальное случайное решение для небольшого N (у меня 15)
2) Затем случайным образом старался его перекрашивать при этом принимая только перекрашивания, которые не ухудшают значение ошибки.
3) Когда попытки перекрашивания не улучшают решение в течение длительного времени, то считаем, что нашли наилучшее решение для текущего N, и переходим к N+1 - добавляем ещё одну вершину к текущему решению и переходим к пункту №2.
Таким образом, каждый более сложный граф строился на основе предыдущего.
Мне очевидно, что мой метод ужасен в плане оптимизации и используемого алгоритма нахождения минимума. Однако это работает, и работает почему-то хорошо. Программа находит все оптимальные решения за несколько проходов от N=15 до N=215. Также нашел все оптимальные значения для малых N<25 (там, говорят, какое то отклонение от теории). И для 4 цветов нашел решения без ошибок до N=48 включительно. Должен признать, что добавление цветов осложняет задачу чрезвычайно. Если бы Al сделал задачу нахождения максимального графа без ошибок в треугольниках, например, для 4-27 цветов, то это было бы по настоящему жестко и на три месяца. Но он всё равно молодец, и я буду ждать от него новых задач!

dmd, думаю, что решения N16=1 не существует. Я покрутил свою программу с пол часика на эту задачу - ничего! Думаю этого достаточно, так как все остальные решения в этом диапазоне находятся относительно быстро.

[dimkadimon]

Herbert Kociemba в сообщении #1525167 писал(а):

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

Теперь начал думать о более интересной задачи. Найдите самой большой граф $K_n$ раскрашенный в $C$ цвета чтобы в нем не было монохромный треугольников.

Hi Dmitry, welcome to the Club 25! I think there already has been much research on the subject you intend to study now so I do not think there is a big chance to find improvements there.
I preferred trying to find the solution for N=19 with only 15 monochromatic triangles and finally managed to find it today. Simple annealing by swapping edges did not do the job, I needed a little extra idea. My solution has 57 edges of each color but since some edges can be recolored without changing the number of triangles this surely is not mandatory.

You may be right - there has been a lot of research in this area. So it would be hard to find improvements, but I still have hope. I managed to find N=19 with "simple annealing" after about 30 minutes. Maybe I got lucky.

-- 03.07.2021, 22:50 --

Vovka17, у вас отличный метод если даже для четырех цветов находит хорошие решения! Я понял по вашей подсказке выше что вы именно это делаете - добавляете точки одну за другой. Я так и не закодил этот метод, но немного удивлен что он настолько хорошо работает. Мне все время казалось что для такого большого пространства решений обязательно нужен отжиг, но видимо это не так.

-- 03.07.2021, 22:59 --

dmd в сообщении #1525185 писал(а):

Существует ли решение N16=1?

Я тоже такое решение не нашел.

[Herbert Kociemba]

Btw, if you draw only the 15 monochromatic triangles of the N=19 solution you can arrange the 19 vertices such that the resulting image shows reflectional symmetry and rotational symmetry by 120° if you simultaneously swap the colors. There are 5 triangles of each color. 18 vertices are the edges of a regular 18-gon, one vertex is the center. The center vertex is the only vertex which is not the corner of any monochromatic triangle.
Deleting one or two vertices from the N=19 solution directly gives the N=18 and N=17 best known solutions without any other modifications.