Алгоритм оптимального расположения отрезков

← →
Беспечный_Ангел © (2005-10-24 15:20) [0]

Здравствуйте, многоуважаемый All =)
Есть такая проблема - необходимо написать алгоритм для следующей задачи:
Даны отрезки заданной длинны в количестве n штук. Нужно найти оптимальную длинну (общуюю) на которой скомбинировать эти маленькие отрезки с минимальными потерями.
Если говорить простым языком, то проблема в следующем: есть прямоугольные отрезки металла, которые нам нужны. Но мы можем заказать полосы только одной длинны. Нужно найти оптимальную длинну полосы и для каждой полосы указать расположение наших "кусочков" с учетом минимальных потерь.
Заранее спасибо!

← →
Desdechado © (2005-10-24 15:43) [1]

типичная задача плотной упаковки в линейно-вырожденном варианте

← →
Беспечный_Ангел © (2005-10-24 15:50) [2]

> Desdechado © (24.10.05 15:43) [1]

А поподробней? Можно ссылочками в меня кинуть =)

← →
Юрий Зотов © (2005-10-24 16:07) [3]

> Беспечный_Ангел © (24.10.05 15:50) [2]

Ключевые слова для поиска: линейное программирование, симплекс-метод. Но можно и без теории, а тупым полным перебором (именно так когда-то и делал, при разумных N считается моментально). Полный перебор здесь сводится к серии вложенных циклов, а сложность в том, что уровень их вложенности заранее неизвестен и поэтому запрограммировать задачу именно вложенными циклами невозможно. Выход - рекурсивная процедура, содержащая один цикл (при вызове ею самой себя получаем вложенные циклы с любым уровнем вложенности, хоть переменным).

Только сначала определитесь с постановкой. Если длина полосы уже известна, то это одна задача (минимизация потерь в чистом виде), если же как раз ее и надо определить - немного другая (минимизация разности длин составных отрезков).

← →
Беспечный_Ангел © (2005-10-24 17:46) [4]

Пасиба =) Буду копать =) К сожалению, "тупым" перебором не получится, n достаточно большое :(

← →
oldman © (2005-10-24 17:49) [5]

Перечитал вопрос.
Не понял - ширина не учавствует вообще???

← →
Sam Stone © (2005-10-24 17:51) [6]

По-моему, тут должна подойти задача о ранце или ее аналог - задача о выкройке(если не ошибаюсь)

← →
Igorek © (2005-10-24 18:12) [7]

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

← →
Беспечный_Ангел © (2005-10-24 18:13) [8]

> oldman © (24.10.05 17:49) [5]

Нет. Тут просто длинны отрезков.

> Sam Stone © (24.10.05 17:51) [6]

хм.. В общем - да.. Вчера ночью я как-то пробежал мимо него, а сейчас посмотрел... Спасибо! =)

> Юрий Зотов © (24.10.05 16:07) [3]

К сожалению, найти удалось не очень много, но пища к размышлению есть =).
Еще раз Спасибо!

> Igorek © (24.10.05 18:12) [7]

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

http://delphibase.spb.ru/?action=viewfunc&topic=mathalg&id=10413
http://delphibase.spb.ru/?action=viewbook&book=10413&topic=mathalg

Алгоритм оптимального расроя в несколько измененном виде
Длина исходных листов - это не бесконечное множество =>
надо сделать просчет исходных листов с реальным шагом до получения
варианта с max коэфициентом заполнения

Приходилось делать на программе "Bars" нечто похожее

Алгоритм оптимального расположения отрезков Найти похожие ветки