2014 dxdy logo

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

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





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


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

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

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


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

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

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

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


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

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


01/06/12
758
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
89
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
758
Adelaide, Australia
dmd в сообщении #1179401 писал(а):
запоминание частичных сумм площадей, исключение ненужных проверок на наклон и пересечение, пропуск просчёта заведомо неприемлемых точек.

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

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


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

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

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


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

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

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


07/06/16
11
Омск
Кстати, на первых порах на регулярных многоугольниках можно хорошо продвинуться. :)
Сначала нарисовал алгоритм "Ёлочка": ...(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
33
Found this sequence:
http://oeis.org/A140466/b140466.txt

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


01/06/12
758
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
684
Вручную построил симметричное решение для N11, и на компе для N17 и N23. Симметричное в точках, линии одна-три ложатся без симметрии.

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


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

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


01/06/12
758
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
11
Омск
Мой рейтинг достиг 23.
До этого придумал несколько алгоритмов, которые ускоряли приближение к заветным 25. :)
Сейчас продвижение идёт со скоростью около 0.05 в сутки. А значит нужны новые идеи.

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

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

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



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

Сейчас этот форум просматривают: Andrey A


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

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