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

смотри вот тут

http://forum.vingrad.ru/forum/topic-371801.html


Это сообщение отредактировал(а) Magistrus - 27.9.2013, 11:54

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

Shlit, что Вы вкладываете в понятие максимально выгодня раскладка? 

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

Ничего сложного нет, простая рекурсия, а предварительная сортировка деталей по размерам нужна только для улучшения результатов. 

ЗЫ Замечу, что этот алгоритм хорош только для прямоугольных деталей. 

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

Т.е. Вы хотете найти в этой теме все возможные алгоритмы раскроя? 


Однако программы  раскроя таки существуют  ;) 


приведите конкретный пример пожайлуста в каком случае будут не приемлимые результаты? 


Все программы в указаном Вами списке, платные или условно-бесплатные, а это значит, что алгоритма который используют они, в готовом виде Вам не найти.

Я не знаю для чего Вам эти алгоритмы, к сожелению Вы это не указали, но мой совет таков:  
- Если Вы собираетесь разработать свою программу, то придется брать какой-нибудь известный Вам алгоритм (не обязательно указанный мной) и дорабатывать его под свои условия. 
- Если же Вам важно просто понять, как работает конкретная программа, советую обратится к разработчику, возможно Вам помогут. 

Вот реальный пример работы одной из программ:



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

Я пользователь этих программ, и если я буду знать, как эти программы работают, то ИМХО, мне будет легче выбирать какую из них лучше использовать в конкретных случаях, также это облегчит мне настройку этих программ для получения приемлимых результатов.

Это сообщение отредактировал(а) Shlit - 30.9.2013, 23:13

Тогда остается только второй вариант. 

Чтение документации. Обращение на форум программы если он есть. Письмо к разработчику. 

Задачу о рюкзаке объяснить тут может каждый грамотный программист, но вот детали реализации в конкретной программе, может объяснить только тот кто ее разробатывал ;)  

Успеха Вам в этом нелегком деле!