|
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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/9104d1ebb656.html, оценка из 5, голосов 10
|