Al Zimmermann's: AP Math

[Archimedes]

Привет, коллеги!

Херберт сейчас выше меня на 2 места. :)
Я использовал несколько подходов.
1. Тупое случайное заполнение с последующим удалением нескольких точек и попытки получить решение лучше текущего. Это неплохо работает для небольших размерностей, но уже для N=11 я пока так и не нашёл максимума.
2. Нахождение максимума незанятых полей при установке следующей точки. Это дало результаты лучше чем первый метод, но всё равно не очень.
3. Попробовал предыдущий алгоритм применить к окрестностям точки, а саму точку отсчёта двигать по спирали от краёв к центру. Получилось не очень - видно что алгоритм перегружает края точками, что потом ужасно сказывается на общем результате.
Пока нет других идей, попробую применить алгоритм 1 к результатам алгоритма 2.
Идеи о симметрии мне тоже приходили в голову, но пока не очень понимаю как это применить на практике.

[traffic_lights]

Складывается впечатление, что реально лидирует Jarek Wroblewski, т.к. в в последнее время он неоднократно обновлял рекорды для высших n. А т.к. гений Jarek'а проявляется прежде всего в задачах, не связанных со статистическими подходами, то шансов у соперников очень мало.

[Archimedes]

Я обогнал Херберта.
Использовал 6-илучевую симметрию и паттерны лучших из найденных решений на границах.
Но до лидеров всё ещё далеко.

[Archimedes]

Дам подсказку: 2,5,6,7,8,11,14,15,16...

[Herbert Kociemba]

I am on holidays since more than a week so I am not able to enter results in the moment. I suppose you refer to the base 3 method with your hint.
Another nice extension to the base 3 method is this:
If you have AP-free string of 0‘s and 1‘s, you can make the substitution
0 -> 000 and 1 -> 110. This gives an AP-free string of triple size and doubled number of 1‘s. You can strip off 0‘s at the end obviously.
Starting with 1 gives the standard base 3 method where your sequence shows the positions of the 0‘s.

[Archimedes]

Херберт, спасибо огромное! Так действительно намного проще чем вручную всё рисовать. :)

[Herbert Kociemba]

The usual way is to set a position to 1 if in the position written as number in base 3 only the digits 0 and 1 occur.

[dimkadimon]

Archimedes в сообщении #1535689 писал(а):

Дам подсказку: 2,5,6,7,8,11,14,15,16...

Ничего не понимаю...

[Archimedes]

В общем, коллеги геометры, давайте тогда вместе обсудим некоторые моменты.
Мы с Хербертом независимо друг от друга пришли к выводу что регулярное заполнение "ромбиками" по краю поля может дать неплохие результаты.
Предпосылками для этого было решение для размерности N=5 и наличие ромбов в решениях других размерностей.
Решение для N=5, чтобы было понятнее, выглядит так (могу это постить, так как правилами конкурса не запрещено размещать решения для не участвующих в конкурсе размерностей):

N=26
223220000     O O - O O
223322000    O O - - O O
333233300   - - - O - - -
233333320  O - - - - - - O
223333322 O O - - - - - O O
023233232  O - O - - O - O
003333333   - - - - - - -
000223322    O O - - O O
000022322     O O - O O
{0,1,3,4},{0,1,4,5},{3},{0,7},{0,1,7,8},{0,2,5,7},{},{0,1,4,5},{0,1,3,4}

Самые внимательные заметили цифры 3 в моём решении - это пустые поля, куда уже нельзя поставить точку.
Если проследить как на поле возникают эти места при добавлении новых точек, то можно заметить много интересного.
После ромбика возникает сначала "полоса отчуждения" шириной в 1 единицу, после второго ромбика - в 4 единицы. Более формально это описал Херберт, за что ему ещё раз огромное спасибо!

Скажу только что подобный подход вместе с 6-лучевой симметрией даёт общий рейтинг примерно 19. То есть это не самый оптимальный способ.
Я начал копать дальше, и заметил одну очевидную вещь: те точки, которые отстоят от исходной на нечётное расстояние, не прибавляют "точек отчуждения" между этими точками. Другими словами, если мы используем ромбики целиком, то получаем между двумя этими ромбиками максимальное число "точек отчуждения", так как ромб содержит все 4 комбинации точек (чётное-чётное, нечётное-четное, чётное-нечётное и нечётное-нечётное). Другие способы заполнения должны давать меньшую плотность в тех зонах где были точки ромбов, но они могут дать меньше "точек отчуждения", некоторые из которых дополнительно заполнятся точками.
Я пробовал некоторые варианты заполнения "ленточками" и "косичками", но пока не нашёл как это может помочь в увеличении числа точек в решении.
Ещё одна идея - порезать ромбы со сдвигом так, чтобы минимизировать число "точек отчуждения". Хотя скорее всего это то же самое что и первый подход.
В общем, можно попробовать вернуться к перебору паттернов по краям поля. Вот только вменяемую целевую функцию мне придумать не удалось. Просто максимизация незанятых мест, куда ещё можно поставить точку, эффекта не даёт.

[Archimedes]

Внимательно посмотрел на два решения, которые у меня есть для N=11.
В одном из них центральная симметрия (она же поворот на 180 градусов), в другой - осевая симметрия.
Видимо нужно не одну сторону шестиугольника выстраивать, а сразу три...

[traffic_lights]

traffic_lights в сообщении #1535130 писал(а):

Складывается впечатление, что реально лидирует Jarek Wroblewski, т.к. в в последнее время он неоднократно обновлял рекорды для высших n. А т.к. гений Jarek'а проявляется прежде всего в задачах, не связанных со статистическими подходами, то шансов у соперников очень мало.

Jarek перешел к рекордам в средней части (с высшими n он уже разобрался) и вплотную подобрался к Paulsen / Paulsen. Думаю, что вопрос с первым местом уже решен, хотя хотел бы очень ошибиться.

[traffic_lights]

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

With a quite stupid program I now can find the solutions for small N and took a look at the symmetry. The N=2 (6 cells) solution obviously has symmetry type 7, N=3 (12 cells) has symmetry type 8, my N=4 (18 cells) solution has symmetry type 4, the N=5 (27 cells) solution has symmetry type 9, the nice N=7 (42 cells) solution also has symmetry type 7, the full symmetry group D6 of the hexagon. My solutions to N=6 and N=11 also have some symmetry, but there are parts of the contest and so I will not give details here.
Nevertheless it is all but sure if for larger N the optimal solutions have some sort of symmetry.

Начинаю реализовывать свой алгоритм. Ясно, что тип симметрии для N=3 (type 8) связан с удалением угловых точек. А в случае N=2,7 угловые точки остаются на месте. Симметричные решения для N=3,4,5 являются секретом?

-- 28.11.2021, 22:05 --

Jarek переместился на первое место, с чем его от души поздравляю.

[traffic_lights]

Сайт Ала недоступен по 404-ой ошибке. Когда это случилось?

[traffic_lights]

За выходные допилил программу. Получил мгновенно оптимальные результаты для n=6, 11. На сайте Ала я публиковал результаты для этих n. Для n=11 у меня там 78 точек: надо было отражать от вертикальной оси, на которой расчет дал ни одной точки. Работаю с целыми числами: для этого мономорфно отобразил гексагональную структуру на квадратную матрицу. Сайт Ала по-прежнему в отрубе.

[traffic_lights]

traffic_lights в сообщении #1544317 писал(а):

Работаю с целыми числами: для этого мономорфно отобразил гексагональную структуру на квадратную матрицу.

На прямоугольную матрицу.