Comments 9
Кажется, бинарный поиск по R и перебор могли бы сработать быстрее для такого маленького количества кругов. Ключевое наблюдение: при упаковке кругов, можно рассматривать лишь варианты где каждый новый круг касется двух уже поставленных (включая касание внешнего круга изнутри). Первый круг можно разместить где угодно на краю большого круга.
Мне приходила такая мысль в голову, когда я реализовывала упаковку кругов в квадрат детерминированным методом и как раз там я применила условие касания двух существующих кругов. В данной задаче алгоритм уже выдавал верный результат, и я не задумалась его оптимизировать, спасибо за совет!
кажется, это не всегда работает. Например, для n=15 оптимальная упаковка не найдется
Облом. Вы правы. Действительно, в этой упаковке нельзя ничего никуда подвинуть. И хоть каждый круг касается двух других, но порядок, в котором их можно так построить начинается не с крайнего круга. Если зафиксировать один из 5 внутренних, то указанная процедура все восстановит, но его позицию нельзя заранее зафиксировать.
Кажется, вашу идею можно спасти, если добавить третью эвристику - для двух кругов, касающихся большого круга, добавить два круга сверху их симметрично, примерно так:
xx
O O
Это работает для n = 12 и 15 (единственные n до 20, на которых не работают ваши эвристики), но сломается на больших n (кажется, для n=29), там вообще начинается жесть, когда шары образуют несимметричную сеть "распорок". Но для таких n уже перебор будет слишком медленно работать.
Спасибо Вам, что занялись этим! Я очень нуждалась в чем-то подобном, когда думала над своим букетом невесты и пыталась объяснить флористу, что мне нужно
В конце нужно добавить отталкивание (а может лучше притягивание) кругов друг от друга.
Воу, какой кайф! Отличная подача материала, хороший разбор и красивое оформление! Как будто Мартина Гарднера почитал 😍
Создание интерактивного макета. Задача упаковки кругов в круг. Метод отжига