2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение20.01.2017, 20:13 


25/08/12
89
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение21.01.2017, 13:37 


25/08/12
89
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.01.2017, 15:22 


25/08/12
89
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....

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение06.02.2017, 12:43 


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение06.02.2017, 13:13 


09/03/16
20
Цитата:
полученный прямым просчётом
- Что вы называете "прямым просчётом"?

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение07.02.2017, 13:25 


07/06/16
11
Омск
ctac в сообщении #1190267 писал(а):
Что вы называете "прямым просчётом"?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение09.02.2017, 10:35 


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение19.02.2017, 22:30 


25/08/12
89
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение20.02.2017, 02:42 


25/08/12
89
Herbert Kociemba в сообщении #1193903 писал(а):
For N=16, 17, 18 and 19 I found optimal minimal solutions
Now also for n=20, 21, 22 and 23.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.02.2017, 15:30 


25/08/12
89
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
Изображение

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение24.02.2017, 21:33 


09/03/16
20
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 :!:

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение09.03.2017, 12:00 
Аватара пользователя


01/06/12
755
Adelaide, Australia
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!

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.03.2017, 09:53 


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

(Оффтоп)

Изображение


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

(Оффтоп)

Изображение


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.03.2017, 10:41 


07/06/16
11
Омск
dmd в сообщении #1200505 писал(а):
Все минимальные треугольники площадью 1/2. При рассмотрении удвоиной площади - можно было можно было вообще исключить операцию деления в расчетах.

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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.03.2017, 14:54 


07/06/16
11
Омск
Я применял тупой подход оптимизации по целевой функции. Почти перебором.
Первый (он же основной) алгоритм сводился к перестановкам нескольких соседних точек. Частичные суммы площадей хранились в массиве, и, в случае совпадения точек с предыдущим решением, не рассчитывались заново. Повторные проверки отрезков, совпадающих с прошлым решением, также исключались.
В результате получалось за приемлемое время перебирать 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 раз большим, я бы продвинулся незначительно.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 100 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group