| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > линейный раскрой ткани |
| Автор: Зинаида 9.3.2010, 16:54 |
| Подскажите, пожалуйста, быстрый ( программно) алгоритм для решения след. задачи: есть отрез материала длиной L и есть n заготовoк длиной li . Все числа целые. Для каждого целого k = { 0, 1, 2 … L } надо выбрать несколько вариантов ( если они есть) раскроя отреза, чтобы L -∑ li *x i =k где x i - количество заготовок длины li.. Нужно выбирать такие варианты, чтобы было Как можно больше заготовок одной длины . На x i наложены ограничения x i <= b i , b i целые положительные числа Число заготовок может быть до 20, длина отреза до 200 00, заготовки длиной от 50 до 500, Мне надо написать программу, с которой пользователь будет работать в интерактивном режиме, т.е. он вводит длину отреза , длины заготовок и их количество , далее нажимает на кнопку и ему на экран выдаются (желательно без видимой задержки ) варианты для выбора раскроя : варианты (когда остаток =к , к от 0, 1, 2 L). Пользователь сам (учитывая др. факторы ) выбирает вариант раскроя. Вообще раскраивается много отрезов и окончательный вариант для каждого отреза должен выбрать человек, а ему надо предложить выбор. Я видела работающую программу ( похоже на Клиппере, исходника нет,, написанная 15 лет назад) варианты предлагаются мгновенно с остатками от - 0 до L . Впечатление, что работет цикл по к, для каждого к идет расчет, но очень быстро. Конечно предлагаются не все варианты, а только те, где меньше разброса по заготовкам ( если это возможно), т.е. надо в один отрез положить как можно больше заготовок одного вида. Например, для L=32 заготовки длиной 17, 5, 3, 2 b1=b2=b3=b4=20 варианты 17 5 3 2 остаток ------------------------------- 1 3 - - 0 - 6 - 1 0 - - 10 1 0 - - - 1 6 0 1 - 5 - 0 1 2 - 2 1 - 5 2 - 1 - - 9 2 1 1 - - 7 1 1 - 4 1 1 т. д. |
| Автор: nworm 9.3.2010, 19:21 |
| Можно так делать. Составляется функция исходные данные: 1) длина без отреза - Line 2) длина и колличество 1-й заготовки - l1 и x1 выходные данные: 1) длина остатка - В 2) максимальное колличество заготовок которые можно вырезать - N Дальше составляется программа, использующая эту функцию Цикл по отрезу от 0 до L с шагом 1 в нём цикл по всем заготовкам, обращающийся к функции если получилось B=0 вывод ответа. если успешно отрезаны все заготовки - тоже вывод и конец |
| Автор: Akina 9.3.2010, 19:31 |
| Поскольку Вы желаете (судя по тому, что написано) получить ВСЕ варианты раскроя, да ещё в порядке сортировки по остатку - имеется типичная [censored] задача с полным перебором вариантов. И я лично не вижу ровным счётом никаких оснований к тому, чтобы заниматься оптимизацией. |
| Автор: Зинаида 10.3.2010, 12:54 |
| Мне не нужны все варианты. В принципе, можно ограничиться вариантами (если такие есть), которые дают нулевой остаток, и то не все такие варианты, а только те , у которых один или несколько видов заготовок входят по максимуму. Главная проблема в том, чтобы расчет был очень быстрым,за секунду. Перебор вешает комп. |
| Автор: Akina 10.3.2010, 13:04 |
| В общем - поиск по форуму или Гугль в помощь. Искать фразу "метод ветвей и границ". |
| Автор: nworm 10.3.2010, 22:22 | ||
Можете тогда просто запрограммировать мой вариант. |
| Автор: Akina 11.3.2010, 08:52 | ||
Твой вариант и есть частный случай метода ветвей и границ. Кстати, не самый оптимальный. |
| Автор: Зинаида 12.3.2010, 18:30 |
| Если я правильно поняла Ваш алгоритм, то ( рассматриваем вариант остаток после раскроя нулевой) надо сначала макс положить первую заготовку, в оставшийся отрез макс вторую и т. д. Если в конце остаток нулевой, то это решение, а если нет, то надо как-то перебирать варианты. Вот реальный пример. Отрез длиной 5859, заготовки длиной 324, 314, 314, 159,229,104,72 ( здесь две заготовки случайно одной длины , но это разные их нельзя объединять), ограничения по количеству соответственно 4,9,7,3,2,2,2 . попытки перебора вешают комп, а "старая" программа мгновенно выдала результаты 4, 9,3,1,2,1,2 4, 5,7,1,2,1,2 4, 9,2,3,2,1,0 |
| Автор: Akina 12.3.2010, 21:00 | ||
Это при том, что надо перебрать 5*10*8*4*3*3*3=43200 вариантов? Боюсь, что у Вас программа написана... ммм... с ошибками. |
| Автор: Зинаида 16.3.2010, 14:42 |
| Полный перебор для данного случая работает 10сек ( задача в 1С) ,Это долго и мне не нужен полный перебор, мне нужны решения близкие к вершинам многогранника, задающего множество допустимых значений. я пытаюсь построить алгоритм ограниченного перебора, который работал бы так же быстро и эффективно, как в старой программе. Пока не получается. |
| Автор: Akina 16.3.2010, 15:03 | ||
Значит, так криво запрограммировано. На VB6 все 8 вариантов находятся за 30 мс. Добавлено через 8 минут и 53 секунды На 1С 7.7 процедура генерит массив решений (точное попадание в 5859) за 150 мс. |
| Автор: Зинаида 16.3.2010, 16:19 |
| У Вас полный перебор за 150мс? |
| Автор: Akina 16.3.2010, 16:29 |
| Конечно... я же не в БД пишу результаты, а в таблицу в памяти. |
| Автор: Зинаида 16.3.2010, 16:35 |
| Это фрагмент моего кода Подскажите, как сделать лучше //=========================== Процедура ФФ (Сум,н) ц= мин(Цел(Сум/А.ПолучитьЗначение(н)),В.Получитьзначение(н) ); Для р1=0 по ц Цикл р=ц-р1; Реш.УстановитьЗначение(н,р); сум1=Сум-А.ПолучитьЗначение(н)*р; Если Сум1=0 Тогда Т.НоваяСтрока(); Для е=1 по н Цикл Т.УстановитьЗначение(Т.НомерСтроки,е,Реш.ПолучитьЗначение(е)); КонецЦикла; Т.УстановитьЗначение(Т.НомерСтроки,"Ост",Сум1); Возврат; КонецЕсли; Если н=МаксВым Тогда Т.НоваяСтрока(); Для е=1 по МаксВым Цикл Т.УстановитьЗначение(Т.НомерСтроки,е,Реш.ПолучитьЗначение(е)); КонецЦикла; Т.УстановитьЗначение(Т.НомерСтроки,"Ост",Сум1); Иначе ФФ(Сум1,н+1); КонецЕсли; КонецЦикла; КонецПроцедуры //================== Процедура Расчет() // перебор всех вариантов у которых сумма меньше Сум рекурсмя А=СоздатьОбъект("СписокЗначений"); В=СоздатьОбъект("СписокЗначений"); Сум=5859; МаксВым=7; А.ИзстрокиСРазделителями("324,314,314,229,159,104,72"); В.ИзстрокиСРазделителями("4,9,7,2,3,2,2"); // В.ИзстрокиСРазделителями("10,10,10,10,10,10,10"); Реш=СоздатьОбъект("СписокЗначений"); Т=СоздатьОбъект("ТаблицаЗначений"); Для р=1 по МаксВым цикл Т.НоваяКолонка(); Реш.ДобавитьЗначение(0); Конеццикла; Т.НоваяКолонка("Ост"); Час=0; Ми=0; Сек=0; ТекущееВремя(Час,ми,сек); Сообщить(Час*10000+ми*100+сек); ФФ(Сум,1); Час=0; Ми=0; Сек=0; ТекущееВремя(Час,ми,сек); Сообщить(Час*10000+ми*100+сек); Т.ВыбратьСтроку(); Т.Сортировать("Ост"); Т.ВыбратьСтроку(); Сообщить(Т.КоличествоСтрок()); КонецПроцедуры; // Добавлено через 7 минут и 9 секунд А как Вы в 1С пишите в таблицу в памяти, как в одномерный массив Т[к] =... ? |
| Автор: Зинаида 16.3.2010, 16:57 |
| А как долго ваша программа делает расчет при ограничениях для всех заготовок <=10 |
| Автор: Akina 16.3.2010, 17:41 |
| Пффф... я за 5 минут написал процедуру, убедился, что она даёт верные результаты, посмотрел время и шлёпнул её за ненадобностью. У вас немеряное время оттого, что Вы запоминаете ВСЕ варианты и ВСЕ промежуточные значение в таблицах - в результате у Вас фактически всё время работает чтение и присвоение колонке объекта. Зарезервируйте сразу массив необходимого размера и адресуйте свой двумерный массив результатов расчёта в одномерную переменную-массив, пересчёт индекса будет работать на порядок быстрее обращения к методу. А уже по окончании расчёта распихаете, буде надо, результаты куда-нить в таблицу. |
