Al Zimmermann - Polygonal Areas

[Herbert Kociemba]

Up to now I have only entered min/max solutions for 5, 7, 11, 17, 23, 47, 59, 71 and 83 which except N=5 are of the type N=4*k+3. The next number of this type in the contest is 131 and it seemes that my current algorithm does not find a minimal area solution within a reasonable time here. I looked for some pencil and paper method and I think I have found a method which works for numbers N=4*k+3. I found a nice solution for N=131 with an area of 111.5 . The points lie completely symmetrical to the diagonal, 65 points on the diagonal and 33 to each side of the diagonal. In general, the area should be O(N) with this kind of construction.

[Herbert Kociemba]

In the same way I now manually constructed a symmetrical solution for N=127 with area 101.5 and used it to construct a maximal solution for N=131 with area 16538. This gave me a score of 0.996. Considering the fact that the minimal areas 111.5 for N=137 and 101.5 for N=127 are far away from optimal I think the score 0.996 does not reflect the mediocre quality of the solution and is too high. A scoring system which reflects the quality better could use for example MaxArea-MinArea-(N-3)^2 for the raw score.

[Herbert Kociemba]

The manuel method also worked for N=163,167,187 and 191 and gives minimal areas about 0.8N. But it gets more and more difficult to fix some identical slopes in the default configuration manually....

[Archimedes]

Максимум при n=29, полученный прямым просчётом, удалось улучшить на 2 единицы с помощью минимума n=25.
Но всё это пока далеко от рекорда.

[ctac]

Цитата:

полученный прямым просчётом

- Что вы называете "прямым просчётом"?

[Archimedes]

ctac в сообщении #1190267 писал(а):

Что вы называете "прямым просчётом"?

Прогон через алгоритм 29 точек на поиск максимума.

[Archimedes]

Мда. Нашёл в своём алгоритме ошибку, которая значительно урезала варианты перебора.
Исправил, и сразу чуть продвинулся по нескольким N. Теперь нужно заново прогонять все примеры для всех N.

[Herbert Kociemba]

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

Due to Pick's theorem the theoretical minimum for all N for the area is N/2-1. I wonder for which N - independent from the N's given in the contest - this minimum is reached.

New ideas led me to a much more powerful algorithm. For N=16, 17, 18 and 19 I found optimal minimal solutions with area 7, 7.5, 8 and 8.5
So in the moment I tend to the opinion that eventually for sufficiently large N a solution with area N/2-1 always can be reached.

[Herbert Kociemba]

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

For N=16, 17, 18 and 19 I found optimal minimal solutions

Now also for n=20, 21, 22 and 23.

[Herbert Kociemba]

I gave symmetrical optimal minimal solutions a try but only found one for N=20 (apart from N=10) with area 9. As you can see it is a really nice solution

[ctac]

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

I gave symmetrical optimal minimal solutions a try but only found one for N=20 (apart from N=10) with area 9. As you can see it is a really nice solution

It's beautiful

[dimkadimon]

Nice work Herbert. Sadly I lost interest in this contest a long time ago and it is hard to get back. Only a few days left and I've noticed that Tomas finally took the lead!

[dmd]

Моя лучшая находка - симметричная ёлочка N29, которую искал в полу-ручном режиме.

(Оффтоп)

Для сравнения оптимум N29

(Оффтоп)

В голове не укладывается - как такое можно было найти методом pen&paper?!

-- Ср мар 15, 2017 12:11:43 --

Моя лучшая идея была - пытаться собирать фигуру из минимальных треугольников. Все минимальные треугольники площадью 1/2. При рассмотрении удвоиной площади - можно было можно было вообще исключить операцию деления в расчетах.

[Archimedes]

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

Все минимальные треугольники площадью 1/2. При рассмотрении удвоиной площади - можно было можно было вообще исключить операцию деления в расчетах.

Ну, я думаю многие до этого додумались. Я тоже использовал целочисленную арифметику с удвоенными данными площадей.

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

Моя лучшая идея была - пытаться собирать фигуру из минимальных треугольников.

Там не всё так просто. Иногда получается вписать один "выступ" в "вогнутость" противоположной стороны.

[Archimedes]

Я применял тупой подход оптимизации по целевой функции. Почти перебором.
Первый (он же основной) алгоритм сводился к перестановкам нескольких соседних точек. Частичные суммы площадей хранились в массиве, и, в случае совпадения точек с предыдущим решением, не рассчитывались заново. Повторные проверки отрезков, совпадающих с прошлым решением, также исключались.
В результате получалось за приемлемое время перебирать 7-9 точек и находить минимальный вариант.
Расчёт был на то, что при последовательном сдвиге рассчитываемого "окна", многоугольник будет как-то приходить к экстремальному значению целевой функции. На деле оказалось что это не так. Один найденный экстремум "кусочка" не ориентировался относительно других локальных экстремумов. В результате перебор прекращал продвигать решение примерно за 5-10% до достижения экстремума.

Пробовал ограничивать перебор областью около диагонали квадрата. Но по какой-то причине отказался от этого на ранних стадиях. Видимо потому что статистики было слишком мало, и я не понимал как должно выглядеть экстремальное решение.

Потом добавил ещё два метода:
м1. взять кусок многоугольника и переставить его между двумя другими соседними точками этого многоугольника. Пересчитывается при этом не более 9 отрезков.
м2. взять две произвольные точки и проверить перестановки их координат.
Сделал два уровня вложенности этих проверок, т.е. последовательно методы (м1;м1), (м1;м2), (м2;м1) и (м2;м2).
Применение этих методов позволило ускорить продвижение к экстремуму на ранних стадиях, но почти не помогало при достижении этих самых 5-10% от оптимума.

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

Была ещё идея проверять перестановки координат случайных точек, а не последовательных. Объём вычислений в этом случае рос просто неприлично и более 5-6 точек просчитывать не удавалось. Видимо я что-то написал неоптимально, но разбираться было уже некогда. Немножко пошатнулось здоровье и всё моё время с начала февраля было отдано здоровью и основной работе. :) Я успел в самом конце времени конкурса посидеть с линейкой и клетчатой бумажкой, но в алгоритмы это не успело воплотиться.

Использовал в своих вычислениях 4 компьютера с числом потоков 3-4. Их вполне хватало для моих алгоритмов. Имей я доступ к 10 компьютерам с быстродействием в 10 раз большим, я бы продвинулся незначительно.

Спасибо всем, кто во время конкурса делился информацией! Некоторые подсказки были очень полезны.