Упаковка кругов в круге — это двумерная задача упаковки, целью которой является упаковка единичных кругов в как можно меньший круг.
История Эта задача упаковки была поставлена и исследовалась в 60-х годах 20-го века. Кравиц в 1967 опубликовал упаковки до 19 кругов без анализа оптимальности решений. Годом позже Грэм доказал, что найденные решения с числом кругов до 7 оптимальны, а Пёрл (Pirl), независимо от него, что оптимальны упаковки до 10 кругов. Лишь в 1994 Мелиссеном (Melissen) была доказана оптимальность решения с 11 кругами. Фодор (Fodor) показал между 1999 и 2003 годами, что решения с 12, 13 и 19 кругами оптимальны. В 2024 году Эканаяке (Ekanayake) и ЛаФонтен (LaFountain) доказали оптимальность решения с 14 кругами.
Грэм (Graham) и др. около 1998 предложили два алгоритма и нашли с помощью них упаковки до 65 кругов. Последний обзор задачи и приближённых решений до 2989 кругов (июнь 2014) дал Экард Спехт (Eckard Specht)Eckard Specht: The best known packings of equal circles in a circle (complete up to N = 2600). packomania.com..
Таблица первых 20 упаковок Минимальные решения (в случае существования нескольких минимальных решений показан только один вариант): Число единичных кругов Радиус вмещающей окружности Плотность Оптимальность Диаграмма 1 1 1.0000 Тривиально оптимальна. 2 2 0.5000 Тривиально оптимальна. 3 ≈ 2.154... 0.6466... Тривиально оптимальна. 4 ≈ 2.414... 0.6864... Тривиально оптимальна. 5 ≈ 2.701... 0.6854... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968 6 3 0.6667... Тривиально оптимальна. Доказана оптимальность также Грэмом в 1968 7 3 0.7778... Тривиально оптимальна. 8 ≈ 3.304... 0.7328... Доказана оптимальность Пёрлом (Pirl) в 1969 9 ≈ 3.613... 0.6895... Доказана оптимальность Пёрлом (Pirl) в 1969 10 3.813... 0.6878... Доказана оптимальность Пёрлом (Pirl) в 1969 11 ≈ 3.923... 0.7148... Доказана оптимальность Мелиссеном (Melissen) в 1994 12 4.029... 0.7392... Доказана оптимальность Фодором (Fodor) в 2000 13 ≈4.236... 0.7245... Доказана оптимальность Фодором (Fodor) в 2003 14 4.328... 0.7474... Доказана оптимальность Эканаяке (Ekanayake) и ЛаФонтеном (LaFountain) в 2024 году 15 ≈ 4.521... 0.7339... Гипотетически оптимальна. 16 4.615... 0.7512... Гипотетически оптимальна. 17 4.792... 0.7403... Гипотетически оптимальна. 18 ≈ 4.863... 0.7611... Гипотетически оптимальна. 19 ≈ 4.863... 0.8034... Доказана оптимальность Фодором (Fodor) в 1999 20 5.122... 0.7623... Гипотетически оптимальна.
См. также
Примечания
Литература
Ссылки "The best known packings of equal circles in a circle (complete up to N = 2600)" "Online calculator for "How many circles can you get in order to minimize the waste?" Packomania for up to 2600 circles.
Категория:Задачи упаковки