Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Технологии: Разные > Какие алгоритмы могут использоваться

Автор: Shlit 26.9.2013, 19:26

Подскажите, гда можно найти информацию по алгоритмам, применяемых в программах по раскрою материалов, таких примерно, как здесь: http://c-a-m.narod.ru/computers/soft-raskroj.html

Автор: Magistrus 27.9.2013, 11:53

смотри вот тут http://forum.vingrad.ru/forum/topic-371801.html

Автор: Shlit 28.9.2013, 19:49

Magistrus, спасибо, уже что-то, но сдается мне, что дело намного сложнее, чем просто рекурсия и алгоритмы сортировки. Во-первых, ни одна из программ из ссылки не может найти максимально выгодную раскладку, все выдают просто "хорошую" раскладку. Во-вторых, все программы дают разную раскладку, даже при одинаковых заданных технологических ограничениях. Есть даже такие программы, которые генерируют разную раскладку просто при последовательных запусках! Мне вообще кажется, что сложность задачи сравнима с игрой в шахматы, если не еще сложнее.

Автор: Magistrus 30.9.2013, 11:33

Shlit, что Вы вкладываете в понятие максимально выгодня раскладка?  На основе этого алгоритма я разработал код,  который давал на выходе от 80 до 95% заполнения плит, в зависимости от размера плит и входных деталей. При повторном запуске результат всегда одинаков. У расматриваемых вами программ наверняка есть какой то случайный фактор, так как нужен не детерменированный результат, а просто подходящий результат.  Ничего сложного нет, простая рекурсия, а предварительная сортировка деталей по размерам нужна только для улучшения результатов.  ЗЫ Замечу, что этот алгоритм хорош только для прямоугольных деталей.

Автор: Shlit 30.9.2013, 17:38

Magistrus, с увеличением количества деталей и разброса размеров все становится не так просто. В реальных условиях производства количество деталей и типоразмеров измеряется сотнями. Число возможных вариантов раскладок растет быстрее, чем количество пресловутых пшеничных зерен на шахматной доске. Перебрать все компьютер не может, поэтому нужен алгоритм формирования "хороших" раскладок. Алгоритм, описаный вами, относится к таким, но он далеко не единственный, причем он даст приемлимые результаты далеко не во всех случаях заданий на раскладку. Задача раскладки в реальных условиях затруднена еще тем, что: 1) вводятся дополнительные ограничения по раскладке (гильотинные резы, запрет на поворот и многое дугое), 2) оптимизируется не заполнение плит, а стоимость детали, включающей в себя как расход материала, так и стоимость раскроя.

Автор: Magistrus 30.9.2013, 18:53

Цитата(Shlit @  30.9.2013,  17:38 ) Алгоритм, описаный вами, относится к таким, но он далеко не единственный Т.е. Вы хотете найти в этой теме все возможные алгоритмы раскроя?  Цитата(Shlit @  30.9.2013,  17:38 ) Перебрать все компьютер не может, Однако программы  раскроя таки существуют  ;)  Цитата(Shlit @  30.9.2013,  17:38 ) Причем он даст приемлимые результаты далеко не во всех случаях заданий на раскладку. приведите конкретный пример пожайлуста в каком случае будут не приемлимые результаты?  Цитата(Shlit @  26.9.2013,  19:26 ) /computers/soft-raskroj.html  Все программы в указаном Вами списке, платные или условно-бесплатные, а это значит, что алгоритма который используют они, в готовом виде Вам не найти. Я не знаю для чего Вам эти алгоритмы, к сожелению Вы это не указали, но мой совет таков:   - Если Вы собираетесь разработать свою программу, то придется брать какой-нибудь известный Вам алгоритм (не обязательно указанный мной) и дорабатывать его под свои условия.  - Если же Вам важно просто понять, как работает конкретная программа, советую обратится к разработчику, возможно Вам помогут.

Автор: Shlit 30.9.2013, 23:05

Цитата(Magistrus @  30.9.2013,  18:53 ) приведите конкретный пример пожайлуста в каком случае будут не приемлимые результаты?  Вот реальный пример работы одной из программ: Цитата(Magistrus @  30.9.2013,  18:53 ) Однако программы  раскроя таки существуют  ;)  Именно по этой причине мне кажется, что там используются более замысловатые алгоритмы, чем методы сортировки и перебора. Цитата(Magistrus @  30.9.2013,  18:53 ) для чего Вам эти алгоритмы, Я пользователь этих программ, и если я буду знать, как эти программы работают, то ИМХО, мне будет легче выбирать какую из них лучше использовать в конкретных случаях, также это облегчит мне настройку этих программ для получения приемлимых результатов.

Автор: Magistrus 1.10.2013, 09:24

Цитата(Shlit @  30.9.2013,  23:05 ) Я пользователь этих программ Тогда остается только второй вариант.  Чтение документации. Обращение на форум программы если он есть. Письмо к разработчику.  Задачу о рюкзаке объяснить тут может каждый грамотный программист, но вот детали реализации в конкретной программе, может объяснить только тот кто ее разробатывал ;)   Успеха Вам в этом нелегком деле!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)