Блог

У меня была эта проблема в течение нескольких лет. Некоторое время назад это было на конкурсе по информатике в моем городе. Я не смог решить эту задачу, и мой учитель не смог ее решить. Я не встречал никого, кто смог бы это решить. Никто из моих знакомых не знает правильного способа дать ответ, поэтому я решил опубликовать его здесь:

Проблема Ze

Учитывая прямоугольник, X по Y, найдите минимальное количество кругов N с фиксированным заданным радиусом R, необходимое для полного покрытия каждой части прямоугольника.

Я думал о способах ее решения, но у меня нет ничего определенного. Если каждый круг определяет внутренний прямоугольник, то R^2 = Wi^2 Hi^2 , где Wi и Hi — ширина и высота практической области, охватываемой каждым кругом i . Сначала я подумал, что должен сделать Wi равным Wj для любого i = j , то же самое для H . Таким образом, я мог бы упростить проблему, сделав соотношение ширины и высоты равным основному прямоугольнику ( Wi/Hi = X/Y ). Таким образом, N=X/Wi . Но это решение, безусловно, неверно в случае X , если значительно превышает Y или наоборот.
Вторая идея заключалась в том, что Wi = Hi для любого заданного i . Таким образом, квадраты заполняют пространство наиболее эффективно. Однако, если остается очень узкая полоса, гораздо более оптимально использовать прямоугольники для ее заполнения, или еще лучше — используйте прямоугольники для последней строки перед этим.
Затем я понял, что ни одна из идей не является оптимальной, поскольку я всегда могу найти лучшие способы сделать это. Он всегда будет близок к окончательному, но не окончательный.

Редактировать
В некоторых случаях (большой прямоугольник) объединение шестиугольников кажется лучшим решением, чем объединение квадратов.

Дальнейшее редактирование
Вот сравнение 2 методов: clover vs hexagonal. Шестиугольник, очевидно, лучше для больших поверхностей. Однако я думаю, что, когда прямоугольник достаточно мал, прямоугольный метод может быть более эффективным. Это догадка. Теперь на картинке вы видите 14 кругов слева и 13 кругов справа. Хотя поверхность отличается намного больше (вдвое), чем один круг. Это потому, что слева они меньше перекрываются, что приводит к уменьшению площади.

Вопросы все еще остаются:

1. Является ли сам шаблон правильного шестиугольника оптимальным? Или необходимо внести определенные коррективы в части основного прямоугольника.
2. Есть ли причины не использовать обычные формы в качестве «окончательного решения»?
3. Есть ли вообще ответ на этот вопрос? 🙂

Для X и Y, больших по сравнению с R, гексагональный (ячеистый) шаблон близок к оптимальному. Расстояние между центрами окружностей в направлении X равно sqrt(3)*R . Расстояние между строками в направлении Y равно 3*R/2 , поэтому вам нужны примерно X*Y/R^2 * 2*/(3*sqrt(3)) круги.

Если вы используете квадратный шаблон, расстояние по горизонтали больше ( 2*R ), но расстояние по вертикали намного меньше ( R ), поэтому вам понадобится около X*Y/R^2 * 1/2 кругов. Поскольку 2/(3*sqrt(3) < 1/2 шестиугольный шаблон является лучшим вариантом.

Обратите внимание, что это только приближение. Обычно можно немного изменить обычный шаблон, чтобы что-то подходило там, где стандартный шаблон не подходит. Это особенно верно, если X и Y малы по сравнению с R.

С точки зрения ваших конкретных вопросов:

1. Шестиугольный узор является оптимальным покрытием всей плоскости. Я бы подумал, что при конечных значениях X и Y часто можно получить лучший результат. Тривиальный пример — когда высота меньше радиуса. В этом случае вы можете перемещать круги в одном ряду дальше друг от друга, пока расстояние между точками пересечения каждой пары кругов не станет равным Y.

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

3. Все примеры на той же странице являются конкретными решениями. Решения с большим количеством кругов несколько напоминают шестиугольный шаблон. Тем не менее, похоже, что решения в закрытой форме не существует.

Этот сайт решает проблему под несколько иным углом: учитывая n единичных кругов, какой самый большой квадрат они могут покрыть?

Как вы можете видеть, с изменением количества кругов меняется и шаблон покрытия.

Для вашей проблемы, я полагаю, это означает: разные размеры прямоугольника и размеры окружности будут определять разные оптимальные схемы покрытия.

Шестиугольник лучше, чем ромб. Рассмотрим процентную площадь единичного круга, покрытого каждым:

 #!/usr/bin/env ruby

include Math

def diamond
  # The distance from the center to a corner is the radius.
  # On a unit circle, that is 1.
  radius = 1

  # The edge of the nested diamond is the hypotenuse of a
  # right triangle whose legs are both radii.
  edge = sqrt(radius ** 2   radius ** 2)

  # The area of the diamond is the square of the edge
  edge ** 2
end

def hexagon
  # The hexagon is composed of 6 equilateral triangles.
  # Since the inner edges go from the center to a hexagon
  # corner, their length is the radius (1).
  radius = 1

  # The base and height of an equilateral triangle whose
  # edge is 'radius'.
  base = radius
  height = sin(PI / 3) * radius

  # The area of said triangle
  triangle_area = 0.5 * base * height

  # The area of the hexagon is 6 such triangles
  triangle_area * 6
end

def circle
  radius = 1
  PI * radius ** 2
end

puts "diamond == #{sprintf "%2.2f", (100 * diamond / circle)}%"
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon / circle)}%"
  

И

 $ ./geometrons.rb 
diamond == 63.66%
hexagon == 82.70%
  

Кроме того, правильные шестиугольники являются многоугольниками с наивысшей вершиной, которые образуют правильную мозаику плоскости.

По моим расчетам, правильный ответ:

 D=2*R; X >= 2*D, Y >= 2*D,
N = ceil(X/D)   ceil(Y/D)   2*ceil(X/D)*ceil(Y/D)
  

В частном случае, если остаток для X / D и Y / D равен 0, то

 N = (X   Y   X*Y/R)/D

Case 1: R = 1, X = 2, Y = 2, then  N = 4

Case 2: R = 1, X = 4, Y = 6, then  N = 17

Case 3: R = 1, X = 5, Y = 7, then  N = 31
  

Надеюсь, это поможет.

Когда круги расположены как клевер с четырьмя листьями с пятым кругом посередине, круг будет покрывать площадь, равную R * 2 * R . При таком расположении возникает вопрос: сколько кругов, которые покрывают область R * 2 * R , будут покрывать область W * H ?, или N * R * 2 * R = W * H . Итак N = W * H / R * 2 * R .