Необходимо вычислить, какое максимальное количество фигур вместится на прямоугольнике. Чем можно реализовать?

#python #алгоритм #математика #math

Необходимо написать мини-программку, которая рассчитывала бы наиболее экономичную
раскладку материала. Дано: фигура произвольной формы и прямоугольный лист материала.
Необходимо разложить максимально возможное количество данной фигуры на этом листе так,
чтобы между ними оставалось расстояние 2-3мм (можно регулировать).
В какую сторону копать? На чем можно реализовать? Хотелось бы на Python, так как
более-менее знаю только его.
    

Ответы

Ответ 1

В общем виде эта задача является труднорешаемой, и не имеет эффективного алгоритма
решения в принципе (его не существует в природе). Если материал Ваш имеет какую-то
особую форму, то ещё можно что-то сделать, а если форма произвольная, то можно попробовать
эвристики. Копайте по таким ключевым словам: "задача о плоскостном  раскрое" или "Cutting
stock problem". На русском, сразу говорю, - мало что полезного найдёте. На английском
ищите задачу Cutting stock problem на прямоугольных полосках с бесконечной длиной (или
высотой). Там суть почти всех эвристик в том, что делается попытка разместить N фигур
на прямоугольной полоске минимальной длиной (высотой) и с фиксированной высотой (длиной).
Соответственно, если у вас ширина (высота) уже заданы заранее, то задача о максимальном
числе N решается бинарным поиском. Сами же эвристики настолько объёмы по изложению,
что расписывать их здесь не смогу.

Отвечаю на второй вопрос: реализовать можно на чём угодно, когда знаешь алгоритм.
Готовые библиотеки мне лично не известны. Вообще, это серьёзная научная проблема, 
коей занимались разные институты (особенно в советское время), нужно довольно хорошо
владеть программированием, чтобы всё здесь правильно закодировать.