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

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

 На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 Печатать страницу | Печатать всю тему Пред. тема | След. тема

 Re: Al Zimmermann - Polygonal Areas20.01.2017, 20:13

25/08/12
113
 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 Areas21.01.2017, 13:37

25/08/12
113
 Последний раз редактировалось Herbert Kociemba 21.01.2017, 14:21, всего редактировалось 1 раз. 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 Areas22.01.2017, 15:22

25/08/12
113
 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 Areas06.02.2017, 12:43

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

 Re: Al Zimmermann - Polygonal Areas06.02.2017, 13:13

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

 Re: Al Zimmermann - Polygonal Areas07.02.2017, 13:25

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

 Re: Al Zimmermann - Polygonal Areas09.02.2017, 10:35

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

 Re: Al Zimmermann - Polygonal Areas19.02.2017, 22:30

25/08/12
113
 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.5So 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 Areas20.02.2017, 02:42

25/08/12
113
 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 Areas22.02.2017, 15:30

25/08/12
113
 Последний раз редактировалось Herbert Kociemba 22.02.2017, 15:35, всего редактировалось 2 раз(а). 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 Areas24.02.2017, 21:33

09/03/16
29
 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 solutionIt's beautiful

 Re: Al Zimmermann - Polygonal Areas09.03.2017, 12:00

01/06/12
799
 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 Areas15.03.2017, 09:53

16/08/05
718
 Последний раз редактировалось dmd 15.03.2017, 10:11, всего редактировалось 1 раз. Моя лучшая находка - симметричная ёлочка N29, которую искал в полу-ручном режиме.(Оффтоп) Для сравнения оптимум N29(Оффтоп) В голове не укладывается - как такое можно было найти методом pen&paper?!-- Ср мар 15, 2017 12:11:43 --Моя лучшая идея была - пытаться собирать фигуру из минимальных треугольников. Все минимальные треугольники площадью 1/2. При рассмотрении удвоиной площади - можно было можно было вообще исключить операцию деления в расчетах.

 Re: Al Zimmermann - Polygonal Areas16.03.2017, 10:41

07/06/16
11
Омск
 Последний раз редактировалось Archimedes 16.03.2017, 10:41, всего редактировалось 1 раз. dmd в сообщении #1200505 писал(а):Все минимальные треугольники площадью 1/2. При рассмотрении удвоиной площади - можно было можно было вообще исключить операцию деления в расчетах.Ну, я думаю многие до этого додумались. Я тоже использовал целочисленную арифметику с удвоенными данными площадей.dmd в сообщении #1200505 писал(а):Моя лучшая идея была - пытаться собирать фигуру из минимальных треугольников.Там не всё так просто. Иногда получается вписать один "выступ" в "вогнутость" противоположной стороны.

 Re: Al Zimmermann - Polygonal Areas16.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 раз большим, я бы продвинулся незначительно.Спасибо всем, кто во время конкурса делился информацией! Некоторые подсказки были очень полезны.

 Показать сообщения за: Все сообщения1 день7 дней2 недели1 месяц3 месяца6 месяцев1 год Поле сортировки АвторВремя размещенияЗаголовок по возрастаниюпо убыванию
 Страница 4 из 7 [ Сообщений: 102 ] На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

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

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

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

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

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