ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Fedotkin 2:5020/400 07 Jun 2001 13:14:05
To : All
Subject : Оптимизация раскроя
--------------------------------------------------------------------------------
Возникла острая необходимость в алгоритме сабжа.
Суть задачи - разместить на прямоугольнике (конкретно - рулон пленки)
прямоугольные заготовки. Поворачивать заготовки можно только на 90 градусов.
Hеобходимо минимизировать израсходованный погонный метраж (с некоторым
допущением можно сказать минимизировать отходы).
В настоящий момент реализован метод простого перебора всех возможных
вариантов, посильно оптимизирован, однако время его работы уже на 10-ти
заготовках ужасает.
Посему вопрос! Hет ли какого алгоритмика хитрого чтоб лбом об стену не
биться?
З.Ы. Слышал что-то про решение такой задачи на двудольной графовой модели
методом замещений, однако что это и как это не представляю :(
Sergey.
--- ifmail v.2.15dev5
* Origin: CFC (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
