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

Насколько я знаю, ничего особо умного так и не придумано для сложных форм - один перебор (конечно со смысловой нагрузкой). Для отрезков может дело и проще обстоит, но Вы уж тогда поподробней задачку объясните - отрезки бывают разные...

Вообщем есть большие отрезки по 6 метров они должны быть оптимально нарезаны на нужные маленькие отрезки (1.2, 2.5 4, 5.6 вообщем любые естествено меньше или равные 6 ). Естественно с минимальной затратои больших отрезков. 

Перебрал все варианты в цикле (в данном случае это длиться долго не будет) и получил ответ. Задал размер отрезка (6 метров), задал несколько вариантов длин отрезков, которые должны быть нарезаны и пошел мучать процессор...  

Спасибо но при 300 разных кусках получится минимум на 3 часа я нашел оптимальный вариант каму интересно http://forum-okna.ru/lofiversion/index.php/t6516.html



Это сообщение отредактировал(а) WaReZMEN - 25.7.2007, 02:44

Это что с шагом в 2 см чтоли?

Вообще шаг мебше примерно в 5 мм. А 300 это кусков каторые нарезать нужно они разной длины не все конечно есть повторяющееся на за щет этих повторений  можно сократить почти в 2 раза но все арвно эти вичисления на 30-35 минут и сервак полностью грузит что не приемлемо так как это терминыльный сервер...

Тогда я не очень понимаю задачу. У Вас есть бросок длиной в 6 метров, его что не поделить точно на какое-то число кусков, при таком маленьком шаге? Напишите пример задачи хоть, которую надо решить...

Брусков бесконеное количество ограничено лиш количество получаемых маленьких бросков (распилов). Хочется как  можно меньше целых (по 6 метров) брусков израсходывать. Естествено маленький бруски разной длены они задаются пользователем постопенно к примеру за неделю а в конце недели нужно все расчитатью. У маленькитх  нет конкретного шага  тоесть маленький брусок любои длены но обязательно меньше 6 метров. К примеру:

Нужно 
1.2
3.4
2.9
4.7
5.7
1.1
1.2
3.3

Нужно наити такую последовательность распило было испрачено минимальное кол-во больших брусков. И запомнить последовательность в каторои нужно пилить к примеру юля выше приведеных данных:


1 2 3 4 5 6 7 8    - Это порядок приведеных цифр
1.2 3.4 2.9 4.7 5.7 1.1 1.2 3.3 
Кол-во распилов:5

Все это я посчитал методом передопра для 8 распилов это потребовалось меньше 1 секунды но уже при 12 нужно 8 сек. при 15 45сек. а мне нужно как минимум для 300 распилов методом перебора (даже  оптемизированым это заимет около 4^604 лет) что не приемлемо.

Завтра посмотрю, сегодня времени мало...

Нашел пару алгоритмов они считают быстро но не оптимально. Хочется оптимальный алгоритм  Я даже знаю формулы но не могу вычислить алгоритм если нужны формулы могу дать.

Это сообщение отредактировал(а) WaReZMEN - 27.7.2007, 08:30

Чтобы получить оптимальный алгоритм, надо сначала сформулировать оптимизационную задачу. Сразу видно, что это будет задача целочисленного/дискретного линейного программирования. 

Допустим, 


L - СУММА (ai*xi) => min

где L - размер заготовки, a - длина i-го отрезка, 
x - управляемые переменные, принимающие значения:
1, если i-й отрезок входит в оптимальный план
0, если не входит

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

Решается на "ура" методами целочисленного программирования: ветвей и границ, неявного (частичного) перебора. Да каким больше нравится.

Хорошо расписано в книге: Вагнер. Исследование операций, том то ли 1-й, то ли 2-й. 


Всё получится! 

Это сообщение отредактировал(а) podval - 27.7.2007, 16:56

podval Спасибо конечно но к сожелению методы  

У меня пока руки не дошли, если дойдут - отпишусь...

Всем спасибо сделал уже  Просто супер при 16000 кусков всего 1 минута 59 сеукунд. мне нужно было при 300 хотяб 1 секунду а ща за секунду делает около 1 тысачи . Вообщем все ОК. Тему можно закрывать.

А ну тогда молоток!  У меня просто на самом деле со временем запарка, хотя алгоритм я вроде как придумал, но не думаю, что он от твоего сильно отличается - все сводиться в умному перебору...

cardinal, там умного перебора не достаточно  Передором (умным) я делал но когда дохрена кусков каторые нарезать нужно один х долго. Ну а ща супер уже внидрили впроизводство  

Молодцы!  За самостоятельность +

А для тех кто тут будет рыться в будущем не плохо было бы выложить хотя бы ссылку на сайт, от информации которого стоит исходить при разработке...

Книжку я на шел "Раскрои произвотственых материалов" тока де скачал не помню... :(