Полностью покрыть прямоугольник минимальным количеством кругов с фиксированным радиусом
У меня эта проблема уже несколько лет. Некоторое время назад это было на конкурсе по информатике в моем городе. Мне не удалось ее решить, и моему учителю не удалось ее решить. Я не встречал никого, кто мог бы это решить. Никто из моих знакомых не знает, как правильно дать ответ, поэтому я решил опубликовать его здесь:
Задача Ze
Для прямоугольника X на Y найти минимальное количество окружностей N с фиксированным заданным радиусом R, необходимо, чтобы полностью покрыть каждую часть прямоугольника.
Я думал о способах решения, но у меня нет ничего определенного. Если каждый круг определяет внутренний прямоугольник, то R ^ 2 = Wi ^ 2 + Hi ^ 2 , где Wi и Hi - ширина и высота практическая область, охватываемая каждым кругом и . Сначала я подумал, что должен сделать Wi равным Wj для любого i = j , то же самое для H ]. Таким образом, я мог упростить задачу, сделав соотношение ширины / высоты равным основному прямоугольнику ( Wi / Hi = X / Y ). Таким образом, N = X / Wi . Но это решение определенно неверно в случае, если X значительно превышает Y или наоборот.
Вторая идея заключалась в том, что Wi = Hi для любого заданного i . Таким образом квадраты наиболее эффективно заполняют пространство. Однако, если остается очень узкая полоса, гораздо оптимальнее использовать прямоугольники для ее заполнения, а еще лучше - использовать прямоугольники и для последней строки перед этим.
Затем я понял, что ни одна из идей не является оптимальной, поскольку я всегда могу найти лучшие способы ее реализации. Это всегда будет близко к финалу, но не окончательно.
Править
В некоторых случаях (большой прямоугольник) соединение шестиугольников кажется лучшим решением, чем соединение квадратов.
Дальнейшее редактирование
Вот сравнение двух методов: клеверный и шестиугольный. Шестиугольная, очевидно, лучше для больших поверхностей. Однако я думаю, что, когда прямоугольник достаточно мал, прямоугольный метод может быть более эффективным. Это догадка.Теперь на картинке вы видите 14 кругов слева и 13 кругов справа. Хотя поверхность отличается намного больше (вдвое), чем один круг. Это потому, что слева они меньше перекрываются, а значит, теряют меньше площади.
Остается вопрос:
- Оптимален ли сам по себе правильный шестиугольник? Или нужно внести определенные коррективы в части основного прямоугольника.
- Есть ли причины не использовать правильные формы в качестве «окончательного решения»?
- Есть ли ответ на этот вопрос? :)