?

Log in

No account? Create an account

Во-первых, это красиво - Общество дровосеков Бердичева по изучению Мишны

Feb. 19th, 2016

09:02 am - Во-первых, это красиво

Previous Entry Share Next Entry

Задача: Поместить без пересечений N кругов в круг единичного радиуса, максимизируя сумму радиусов кругов. Уже для N=5 решение неочевидно. Для N от 6 до 10 включительно наилучшим оказывается решение типа "шарикоподшипник". Для N=11 наилучшее известное решение такое:

Самое удивительное, что для некоторых N оптимальное решение совершенно несимметрично.
Да их там тыщи!
К примеру, как паковать стаканы в коробку.

Comments:

[User Picture]
From:zeinab_bint_ali
Date:February 19th, 2016 05:05 pm (UTC)
(Link)
Baffling
(Reply) (Thread)
[User Picture]
From:baramin
Date:February 19th, 2016 05:23 pm (UTC)
(Link)
Круто!
(Reply) (Thread)
[User Picture]
From:i_eron
Date:February 19th, 2016 06:50 pm (UTC)
(Link)
Да, красиво. Очевидно, что оптимальная сумма радиусов N+1 кругов будет не меньше, чем сумма радиусов N кругов. Для больших N она, наверное, пойдёт гладко, пропорционально корню из N. Но для меня удивительно, что эта функция очень близка к a*sqrt(N)+b прямо начиная с N=2. То ли значение граничных искажений для малых N преувеличивают, то ли оптимизация сравнительных размеров уложенных в тарелку яблок - великая сила. Я всегда подозревал и то, и другое.

Кстати, по ссылке оптимизируют сумму радиусов, а не диаметров.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 06:54 pm (UTC)
(Link)
Действительно, что это я, тем более что слово "радиус" короче.
(Reply) (Parent) (Thread)
[User Picture]
From:i_eron
Date:February 19th, 2016 07:07 pm (UTC)
(Link)
Когда-то на курсе по квантовой химии я стал распинаться про диаметр атома. За это надо мной смеялись, говоря, что у атома радиус, и что атом не меряют штангенциркулем. Прошло чуть ли не тридцать лет, а я всё ещё ищу, где бы кулаками после драки помахать.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 07:47 pm (UTC)
(Link)
Да они ж тупые, эти смеявшиеся! Если у чего есть радиус, то у того есть и диаметр.
(Reply) (Parent) (Thread)
[User Picture]
From:i_eron
Date:February 19th, 2016 09:06 pm (UTC)
(Link)
Не тупые, а просто жестокие. Сегодня я бы и сам смеялся, если б кто к атому со штангенциркулем подошёл. И наоборот, смутно припоминаю, что на уроке труда надо было вытачивать что-то круглое и я упомянул радиус, а учитель труда стал ругаться, что у дерева и алюминия - диаметр, а никакой не радиус.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 09:16 pm (UTC)
(Link)
Тупые, потому что радиус и диаметр - это одно и то же с точностью до константы.
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:February 19th, 2016 11:29 pm (UTC)
(Link)
...для шаров - да. Но, например, для графов это не так.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 11:56 pm (UTC)
(Link)
Пожалуй, потому что для графов они, в сущности, "дискретный радиус" и "дискретный диаметр".
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 20th, 2016 12:10 am (UTC)
(Link)
А как называется величина минимакса расстояний между одной точкой и остальными у произвольной фигуры (аналог радиуса графа), я на mathworld.com не нашел.

Edited at 2016-02-20 12:18 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:b0p0h0k
Date:February 20th, 2016 03:43 am (UTC)
(Link)
A slice of pizza comes to mind.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 20th, 2016 04:35 am (UTC)
(Link)
Диаметр есть у любой геометрической фигуры - это максимальное расстояние между точками фигуры. Обратное неверно, понятие "радиус" определено не для любой фигуры.
(Reply) (Parent) (Thread)
From:aerffadf
Date:February 24th, 2016 11:59 am (UTC)
(Link)
Эксцентриситет точки фигуры – максимальное расстояние от этой точки до любой другой точки этой фигуры.
Диаметр – максимальный эксцентриситет точки фигуры.
Радиус – минимальный эксцентриситет точки фигуры.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 24th, 2016 03:52 pm (UTC)
(Link)
Это для графов так, а для обычных геометрических фигур не применяется. http://mathworld.wolfram.com/Radius.html
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 06:58 pm (UTC)
(Link)
Насчет великой силы не понял.
(Reply) (Parent) (Thread)
[User Picture]
From:i_eron
Date:February 19th, 2016 07:08 pm (UTC)
(Link)
Ну, обычная интуиция говорит, что если укладывать яблоки в тарелку, а потом рисовать график, сколько яблок поместилось в тарелке против размера тарелки, то зависимость должна в начале дёргаться, пока тарелки маленькие, а потом сгладиться, когда тарелки большие. А тут она практически гладкая с самого начала. И это потому, что мы можем выбирать яблоки чуть побольше или чуть поменьше, чтоб аккуратнее заполнить ими тарелку. То есть, влияние граничных условий, которое по интуиции вызывает дёрганное начало, нейтрализуется оптимизацией сравнительных размеров яблок, которая сглаживает.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 07:44 pm (UTC)
(Link)
Это можно проверить с помощью http://www2.stetson.edu/~efriedma/cirincir/
Похоже, что гладкости не добиться (см 6-7, 18-19).
(Reply) (Parent) (Thread)
[User Picture]
From:i_eron
Date:February 19th, 2016 08:57 pm (UTC)
(Link)
Не только дёргается, но даже выглядит, что недостача у одинаковых кругов по сравнению с оптимизированными вообще не уменьшается. То есть, границы заставляют зависимость дёргаться, абсолютный размах этого дёрганья того же порядка, как и недостача, которую можно покрыть оптимизацией размеров, и обе эти штуки не стремятся к нулю при больших N (хотя относительное влияние границ, конечно, должно стремиться к нулю).


(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 09:18 pm (UTC)
(Link)
Наглядно, спасибо.
(Reply) (Parent) (Thread)
[User Picture]
From:marco_polo_sf
Date:February 19th, 2016 07:25 pm (UTC)
(Link)
Прикольно!
(Reply) (Thread)
[User Picture]
From:galkao
Date:February 19th, 2016 09:58 pm (UTC)
(Link)
Вот некоторым математикам заняться больше нечем, лишь бы зарплату оправдать:-)))
(Reply) (Thread)
[User Picture]
From:spamsink
Date:February 19th, 2016 10:41 pm (UTC)
(Link)
Подобные задачи оптимизации могут приносить пользу в народном хозяйстве, минимизируя отходы.
(Reply) (Parent) (Thread)
[User Picture]
From:galkao
Date:February 19th, 2016 10:58 pm (UTC)
(Link)
Боюсь, что в "народном хозяйстве" задача стоит ровно наоборот: как при конкретном наборе проводов с сечением разных диаметров минимизировать диаметр кабеля-оболочки":-)

А диаметр проводов диктуется не матическими данными, а потребностями потребителей. И им плевать на математику, и даже на статистику:-) Одна "деревня" потребляет одно количество, соседняя - другое.


(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:February 19th, 2016 11:30 pm (UTC)
(Link)
Интересно, спасибо.
(Reply) (Thread)
[User Picture]
From:alexanderr
Date:February 20th, 2016 03:24 am (UTC)
(Link)
а еще есть задача про максимально плотную
упаковку одинаковых шаров в N-мерном пространстве.
для N=10 и N=24 есть доказанные максимально плотные
упаковки. для N=3 есть подозреваемые, но кажется они
еще не доказаны
(Reply) (Thread)
[User Picture]
From:e_ponikarov
Date:February 20th, 2016 11:34 am (UTC)
(Link)
Красиво!
А картинки явно спонсировал M&Ms :)
(Reply) (Thread)