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

[spamsink]

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

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

Comments

[zeinab-bint-ali.livejournal.com]

Baffling

[baramin.livejournal.com]

Круто!

[i_eron]

Да, красиво. Очевидно, что оптимальная сумма радиусов N+1 кругов будет не меньше, чем сумма радиусов N кругов. Для больших N она, наверное, пойдёт гладко, пропорционально корню из N. Но для меня удивительно, что эта функция очень близка к a*sqrt(N)+b прямо начиная с N=2. То ли значение граничных искажений для малых N преувеличивают, то ли оптимизация сравнительных размеров уложенных в тарелку яблок - великая сила. Я всегда подозревал и то, и другое.

Кстати, по ссылке оптимизируют сумму радиусов, а не диаметров.

[spamsink]

Действительно, что это я, тем более что слово "радиус" короче.

[i_eron]

Когда-то на курсе по квантовой химии я стал распинаться про диаметр атома. За это надо мной смеялись, говоря, что у атома радиус, и что атом не меряют штангенциркулем. Прошло чуть ли не тридцать лет, а я всё ещё ищу, где бы кулаками после драки помахать.

[spamsink]

Да они ж тупые, эти смеявшиеся! Если у чего есть радиус, то у того есть и диаметр.

[i_eron]

Не тупые, а просто жестокие. Сегодня я бы и сам смеялся, если б кто к атому со штангенциркулем подошёл. И наоборот, смутно припоминаю, что на уроке труда надо было вытачивать что-то круглое и я упомянул радиус, а учитель труда стал ругаться, что у дерева и алюминия - диаметр, а никакой не радиус.

[spamsink]

Тупые, потому что радиус и диаметр - это одно и то же с точностью до константы.

[raindog-2.livejournal.com]

...для шаров - да. Но, например, для графов это не так.

[spamsink]

Пожалуй, потому что для графов они, в сущности, "дискретный радиус" и "дискретный диаметр".

[spamsink]

А как называется величина минимакса расстояний между одной точкой и остальными у произвольной фигуры (аналог радиуса графа), я на mathworld.com не нашел.

[b0p0h0k.livejournal.com]

A slice of pizza comes to mind.

[spamsink]

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

[aerffadf.livejournal.com]

Эксцентриситет точки фигуры – максимальное расстояние от этой точки до любой другой точки этой фигуры.
Диаметр – максимальный эксцентриситет точки фигуры.
Радиус – минимальный эксцентриситет точки фигуры.

[spamsink]

Это для графов так, а для обычных геометрических фигур не применяется. http://mathworld.wolfram.com/Radius.html

[aerffadf.livejournal.com]

Есть такое, например
https://www.encyclopediaofmath.org/index.php/Chebyshev_radius

[spamsink]

Насчет великой силы не понял.

[i_eron]

Ну, обычная интуиция говорит, что если укладывать яблоки в тарелку, а потом рисовать график, сколько яблок поместилось в тарелке против размера тарелки, то зависимость должна в начале дёргаться, пока тарелки маленькие, а потом сгладиться, когда тарелки большие. А тут она практически гладкая с самого начала. И это потому, что мы можем выбирать яблоки чуть побольше или чуть поменьше, чтоб аккуратнее заполнить ими тарелку. То есть, влияние граничных условий, которое по интуиции вызывает дёрганное начало, нейтрализуется оптимизацией сравнительных размеров яблок, которая сглаживает.

[spamsink]

Это можно проверить с помощью http://www2.stetson.edu/~efriedma/cirincir/
Похоже, что гладкости не добиться (см 6-7, 18-19).

[i_eron]

Не только дёргается, но даже выглядит, что недостача у одинаковых кругов по сравнению с оптимизированными вообще не уменьшается. То есть, границы заставляют зависимость дёргаться, абсолютный размах этого дёрганья того же порядка, как и недостача, которую можно покрыть оптимизацией размеров, и обе эти штуки не стремятся к нулю при больших N (хотя относительное влияние границ, конечно, должно стремиться к нулю).

[spamsink]

Наглядно, спасибо.

[marco-polo-sf.livejournal.com]

Прикольно!

[galkao.livejournal.com]

Вот некоторым математикам заняться больше нечем, лишь бы зарплату оправдать:-)))

[spamsink]

Подобные задачи оптимизации могут приносить пользу в народном хозяйстве, минимизируя отходы.

[galkao.livejournal.com]

Боюсь, что в "народном хозяйстве" задача стоит ровно наоборот: как при конкретном наборе проводов с сечением разных диаметров минимизировать диаметр кабеля-оболочки":-)

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

[outputlogic.livejournal.com]

Например устройство для производства квадратных яиц - неплохой способ минимизировать отходы.
http://www.thegreenhead.com/imgs/egg-cuber-makes-square-eggs-1.jpg

[raindog-2.livejournal.com]

Интересно, спасибо.

[alexanderr.livejournal.com]

а еще есть задача про максимально плотную
упаковку одинаковых шаров в N-мерном пространстве.
для N=10 и N=24 есть доказанные максимально плотные
упаковки. для N=3 есть подозреваемые, но кажется они
еще не доказаны

[spamsink]

On 10 August 2014 Hales announced the completion of a formal proof using automated proof checking, removing any doubt.

[e-ponikarov.livejournal.com]

Красиво!
А картинки явно спонсировал M&Ms :)