сколько малых окружностей можно вписать в большую

[vvvv]

Родственная задача рассматривалась здесь
topic24235-30.html

[Дима Тишков]

Здесь можно посмотреть наилучшие известные упаковки до 20 единичных кругов, если кому-то интересно.

[age]

В моем случае упаковки для $20$ получилось $5,178>5,122$. Немного хуже.
Забавны случаи $17$ и $15$. Очень забавен случай $19$! Т.к. внутреннее кольцо, содержащее $6$ кругов попадает как раз во впадины внешнего кольца, содержащего $12$ кругов. Тем самым экономится масса пространства! Мой метод дал бы $5,178$ как и для $20$. Здесь же аж $4,863$.
Да и девятку кажется, можно сжать (на первый взгляд).

[mserg]

Математически задача выглядит так:
Найти такой минимальный радиус $r$ , чтобы выполнялись условия
$x_i^2+y_i^2 \le (r-1)^2$, где $1\le i \le n$,
$(x_i-x_j)^2+(y_i-y_j)^2 \ge 4$, где $1 \le i < j \le n$.
Здесь $n$-количество вписываемых кружков (это константа),
$x_i,y_i$ – координаты центров вписанных кружков.

Это задача нелинейного программирования. Берете качественный пакет оптимизации, случайно разбрасываете кружки относительно начала координат и запускаете оптимизацию. И так много раз. Это самый реальный путь нахождения оптимальных/субоптимальных решений задачи для $21<=n<=40$.

Одно из решений для $n=40$ приведено ниже.

7.17754138874064
Circle(x, y)
  1, 0, 4.390276505113
  2, 3.26493526656745, -2.74745828663341
  3, 6.14815633478522, 0.601064428713263
  4, 0.969914794315303, -2.63170219436339
  5, 6.01799394395454, -1.39472028783103
  6, -3.17870556476168, -2.76364105107039
  7, 5.63389857876293, 2.53384436333632
  8, -6.14724248159146, -0.610786680995056
  9, 1.11175236633765, 2.72764236470452
  10, -4.35547102113511, -4.38083024282989
  11, -4.06687571783909, 0.955617027495331
  12, -2.36648070217441, -4.59133564545259
  13, 0.17473966491548, 0.960620823659287
  14, -5.26188909874546, 3.23604203954025
  15, -1.99877744313408, 4.31845415523112
  16, -2.06693152078433, 0.973109579830369
  17, -5.51513329707553, -2.71954002392078
  18, 1.98513170658394, -4.35493603615537
  19, -4.19390081992091, -1.04040906794961
  20, 2.17386932628909, 1.02385048950595
  21, 1.00031996605008, -6.09591988181086
  22, -1.17870250463455, -2.74606740634916
  23, 4.21541112232374, 1.12309372266626
  24, -3.95223060910512, 4.74773489769063
  25, -0.193924673166822, -1.00515059453054
  26, 1.06082538983625, 6.08576641495962
  27, -2.19392301897422, -1.02286757142943
  28, 2.9495333499522, 5.42783184397211
  29, -1.06149038639856, 6.0855386547596
  30, -0.936915597607238, 2.6232933466528
  31, 4.08711753855909, -0.873091491449154
  32, 5.25696065637872, -3.244294910639
  33, 3.11083916411161, 2.79085629077821
  34, -3.30801159124956, 2.8062837816762
  35, -1.48105226736221E-02, -4.3725449824624
  36, 3.9449608802893, -4.75384933182949
  37, 4.52911919650879, 4.20104571220111
  38, -1.04109940844589, -6.08916811710185
  39, -6.02020072296927, 1.38526913735776
  40, 2.08959028052503, -0.974436342024506
End 

Вопрос о том, сколько кружков влезет в круг определенного радиуса, может быть решен с помощью дихотомии по $n$. Нижняя граница $1$, верхняя – ее, видимо, можно получить с помощью оценочных функций. Для случая $r=7$, вероятно, $n=38$. Пример приведен ниже:

Circle(x, y)
  1, 0, 3.99160219036685
  2, -1.09158174783061, -1.92596760064596
  3, -4.35022389530649, -4.11920876102882
  4, -2.75194244962724, -5.32156777866371
  5, 1.15254001704372, -5.87912413480362
  6, -5.4635833988747, -2.45770121850297
  7, -5.80755436516961, 1.47120638287307
  8, 0.666163135116352, -3.93915193475404
  9, -1.33366881331457, -3.91138096013408
  10, -0.846870313151005, -5.93066192481939
  11, 3.02346024532121, -5.17209504521649
  12, -2.93195210885879, -2.70902585693492
  13, -9.88397122888192E-02, -1.18512959790173E-02
  14, 0.234559586887297, 2.00486823643765
  15, -1.74047870314667, 1.68867146986364
  16, 1.96817675171418, 3.63581167164824
  17, -4.03681600973484, -1.04187531730224
  18, 6.72574736210544E-02, 5.99061757210455
  19, -3.79478795306791, 0.943479557049415
  20, 5.58352486764654, -2.17178707894738
  21, -3.67126051173147, 4.73436767287852
  22, -2.19636104211923, -0.258745231425907
  23, 3.93097625055194, 2.65662982722202
  24, 5.98709001289223, -0.212868853287454
  25, -1.90832737307565, 5.67891159169085
  26, 0.908249073463255, -1.95384200402288
  27, 4.06371210857334, 0.45091392013409
  28, -5.96820000339661, -0.522361926700486
  29, 2.10008753487687, -0.347737724636714
  30, -4.36797012044392, 2.85962333803661
  31, 2.20293952010507, 1.64962609041518
  32, 3.67155426344396, -1.58489811992369
  33, 2.03535675625387, 5.63469515861549
  34, 3.77662581438861, 4.6507081661895
  35, 4.55733279031813, -3.88853498445957
  36, 5.72363392062241, 1.76976015533315
  37, 2.53706397615233, -3.23205495166903
  38, -1.97483715559727, 3.67496399846191
End 

[AlekseyToro]

Цитата:

Это задача нелинейного программирования. Берете качественный пакет оптимизации, случайно разбрасываете кружки относительно начала координат и запускаете оптимизацию. И так много раз. Это самый реальный путь нахождения оптимальных/субоптимальных решений задачи для .

Можно про эту методику поподробнее?

Цитата:

Математически задача выглядит так:
Найти такой минимальный радиус , чтобы выполнялись условия
, где ,
, где .
Здесь -количество вписываемых кружков (это константа),
– координаты центров вписанных кружков.

И про условия не совсем понял....

[mserg]

Условие $x_i^2+y_i^2 \le (r-1)^2$ гарантирует, что кружок радиуса 1 с центром в $x_i,y_i$ будет внутри окружности радиуса $r$.
Условие $(x_i-x_j)^2+(y_i-y_j)^2 \ge 4$ гарантирует, что $i$-ый и $j$-ый кружки не пересекаются.
Переменные задачи это $x_i,y_i,r$, т.е. для $n=40$ будет 81 переменная. Вот и все условия.

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

[age]

mserg
$7,177$ для $40$ - внушительный результат. У меня получилось $7,392$, что согласитесь, гораздо хуже!