2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение22.12.2016, 11:06 
Аватара пользователя


10/11/12
121
Бобруйск
dmd в сообщении #1179152 писал(а):
максимальная "рамка" из 5-ти точек больше максимальной "рамки" из 6-ти точек на 3/2 для любого n.

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

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


07/06/16
45
Омск
"Кривые штаны" тоже уже получил.
Спасибо за симметричные примеры минимумов, по-моему этот метод может очень сильно помочь для больших n.

Сразу применил подходы по оптимизации из прошлых задач: запоминание частичных сумм площадей, исключение ненужных проверок на наклон и пересечение, пропуск просчёта заведомо неприемлемых точек.
Всё равно, перебором можно найти только 11х11.
Даже 17х17 перебрать нереально. (Может быть симметричный минимум получится).

Испытываю проблемы нахождения опорного (любого) решения для n>257. Меньшие уже нашёл, зарядил 3 4-хпоточных процессора перебирать варианты. Пока выше 31-го места не поднимался.

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


16/08/05
1146
Решение для N10 получилось преобразовать в решение для N11, не оптимальное конечно, но с сохранением симметрии точек.

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


01/06/12
1016
Adelaide, Australia
Vovka17 в сообщении #1179133 писал(а):
Вроде это максимумы для n=8, 9, 10. Гарантии на них не распространяются?

Я получил те же самые результаты, поэтому вероятно они оптимальные.

-- 23.12.2016, 17:48 --

Archimedes в сообщении #1179375 писал(а):
Испытываю проблемы нахождения опорного (любого) решения для n>257

Для этого у меня сработал вот такой метод. Начинаем с случайных двух точек. Добавляем первую точку которая создает легальный полигон. Повторяем пока не добавим все $n$ точек. Точки можно вставлять в любое ребро готового полигона. Есть хорошая вариация. Вместо "первой" точки находим ту точку которая дает наибольшую/наименьшую площадь. Если слишком медленно то можно не все варианты перебирать, а только часть, например $1/10$.

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


25/08/12
171
Germany
My program can brute force up to N=11 without problem. So indeed the results up to N=11 are optimal. In the moment I brute force N=12 just for fun because I still do not have the idea for a good approach for N=29 and larger.

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


01/06/12
1016
Adelaide, Australia
dmd в сообщении #1179401 писал(а):
запоминание частичных сумм площадей, исключение ненужных проверок на наклон и пересечение, пропуск просчёта заведомо неприемлемых точек.

Очень интересно. Спасибо за подсказки. Теперь надо подумать как вы это сделали.

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


20/03/16
5
Киев
Archimedes в сообщении #1179375 писал(а):
Испытываю проблемы нахождения опорного (любого) решения для n>257.

Существуют относительно простые решения с регулярной структурой (достаточно выч. мощности программируемого калькулятора) как для минимума, так и для максимума, дающие относительно неплохой результат.

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


07/06/16
45
Омск
erraen в сообщении #1179419 писал(а):
Существуют относительно простые решения с регулярной структурой (достаточно выч. мощности программируемого калькулятора) как для минимума, так и для максимума, дающие относительно неплохой результат.

Огромное спасибо! Нарисовал алгоритм.

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


07/06/16
45
Омск
Кстати, на первых порах на регулярных многоугольниках можно хорошо продвинуться. :)
Сначала нарисовал алгоритм "Ёлочка": ...(5,n-1)(4,4),(2,n),(1,1),(n,2),(3,3),(n-1,5)...
Результат близок к n*n/2, поэтому ни к минимуму, ни к максимуму он не близок.
Потом нарисовался алгоритм "Пила" в двух модификациях. На больших n это дало больше чем случайно просчитанные многоугольники. :)
Кроме того, обнаружил ошибку в своём алгоритме просчёта пересечений. Вроде исправил.

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


20/01/13
62
Found this sequence:
http://oeis.org/A140466/b140466.txt

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


01/06/12
1016
Adelaide, Australia
jcmeyrignac в сообщении #1180237 писал(а):

Looks like there are plenty of slopes to go around. Even for $n=17$ we have $C^{384}_{17} = 1.6*10^{29}$, which is actually larger than the total number of point placements: $(17!)^2=1.2*10^{29}$.

You are not competing JC?

-- 27.12.2016, 13:51 --

Кто нибудь пробовал генерировать симметричные решения? На вид у многих хороших решений есть симметрия, но воспроизвести эту симметрию автоматически оказалось не так просто. Если приглядеться то симметрия не совсем идеальная и именно это сложно оптимизировать. У меня симметричные решения больше $n=29$ не получаются.

-- 27.12.2016, 14:01 --

Для максимальных решений сколько лучше иметь "входов" внутрь? Можно ли всегда обойтись одним входом?

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


16/08/05
1146
Вручную построил симметричное решение для N11, и на компе для N17 и N23. Симметричное в точках, линии одна-три ложатся без симметрии.

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


01/06/12
1016
Adelaide, Australia
Минимальная площадь для выпуклых полигонов с целыми координатами: https://oeis.org/A070911

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


01/06/12
1016
Adelaide, Australia
Вот полезная под-задача. Даются точки в плоскости. Надо найти полигон минимальной площади который проходит через все точки. Оказывается задача NP-Hard:
http://mathoverflow.net/questions/19211 ... h-contains

Тут приведен приблизительный алгоритм нахождения такого полигона:
http://oa.upm.es/19287/1/INVE_MEM_2011_121744.pdf

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


07/06/16
45
Омск
Мой рейтинг достиг 23.
До этого придумал несколько алгоритмов, которые ускоряли приближение к заветным 25. :)
Сейчас продвижение идёт со скоростью около 0.05 в сутки. А значит нужны новые идеи.

Где-то тут раньше обсуждали что максимум - это тот же минимум, только с инверсией. Идея богатая :), но пока проверил её только на 12min -> 17max и 11min -> 17max. Ничего даже близкого к максимуму не получается: проигрыш найденному другими алгоритмами около 5 ед. Возможно этот подход даст больше на больших N.

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

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



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

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


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

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