Архитектору и проектировщику|Тепло- и звукоизоляция URSA.RU
VetCAD

Программа сравнения двух алгоритмов линейного раскроя

    0 оценок

gumel

размещено: 08 Июня 2017
обновлено: 12 Января 2019
Замутил программу для составления карт раскроя каких либо хлыстов по исходной спецификации (длина-количество). Изначально был реализован простой алгоритм (его еще называют жадным) раскроя. Далее внедрил еще один более сложный алгоритм (облазил весь интернет, использовал разные источники), который зачастую дает более интересные (с точки зрения экономии материала) результаты.

Исходные данные: длина хлыста и ширина реза + спецификация.
Спецификацию можно вводить "ручками", а можно вставить из экселя, предварительно скопировав в буфер обмена пару столбцов с нужной информацией.

Хз, не стал убирать кнопки "1","2","3" (слева вверху окна приложения), нажимая на них, формируются тестовые спецификации. Оставил их для интереса.

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

Пользуйтесь на здоровье!
А также, интересны ваши замечания ))
Программа сравнения двух алгоритмов линейного раскроя1
Программа сравнения двух алгоритмов линейного раскроя2

Комментарии

Комментарии могут оставлять только зарегистрированные участники
Авторизоваться
Комментарии 1-7 из 7
Kaha251184 , 08 июня 2017 в 19:07
#1
Спасибо
Grant , 09 июня 2017 в 05:47
#2
Спасибо зща утилиту.

P.S. А в чем принципиальная разница второго алгоритма ? Ведь смысл т.н. упомянутого Вами гриди-алгоритма ("жадного алгоритма") или, иначе, "задаче рюкзака" - в максимально плотной "упаковке" из необходимых длин, в стандартной длине заготовки.
Staz , 13 июня 2017 в 17:29
#3
Спасибо!
Staz , 13 июня 2017 в 17:29
#4
Спасибо!
gumel , 14 июня 2017 в 07:13
#5
Цитата:
Сообщение #2 от Grant
Спасибо зща утилиту.

P.S. А в чем принципиальная разница второго алгоритма ? Ведь смысл т.н. упомянутого Вами гриди-алгоритма ("жадного алгоритма") или, иначе, "задаче рюкзака" - в максимально плотной "упаковке" из необходимых длин, в стандартной длине заготовки.


Разница огромна. Насколько я понимаю, реализация жадного алгоритма в моем исполнении не решает задачу насчет максимально плотной упаковке, поскольку алгоритм "пилит" заготовки не думая. Данный метод отрабатывает быстро, можно сказать моментально, пробегая одним единственным циклом по спецификации один раз.

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

Что еще могу сказать. Откатали эти алгоритмы на практике. Занимаемся изготовлением алюминиевых светопрозрачных конструкций. С точки зрения работника, который работает на пиле, простой алгоритм намного удобнее! Поскольку количество перестановок упора, в этом случае, минимально.
MichaelCH , 06 июня 2018 в 17:54
#6
Потестировал программу, ввод исходных данных удобный.
Про "жадный" алгоритм ничего не буду говорить и так понятно про его возможности и недостатки.
По "умному" алгоритму, не всегда стабильно работает, не получается раскроить задание если должно использоваться более 200 заготовок.
Кроме того по некоторым исходным данным результат "умного" алгоритма хуже "жадного".
Если интересно, могу поделится собственным алгоритмом линейного раскроя, результат получается лучше, но и считает как правило дольше.
gumel , 11 декабря 2018 в 04:45
#7
Цитата:
Сообщение #6 от MichaelCH
Потестировал программу, ввод исходных данных удобный.
Про "жадный" алгоритм ничего не буду говорить и так понятно про его возможности и недостатки.
По "умному" алгоритму, не всегда стабильно работает, не получается раскроить задание если должно использоваться более 200 заготовок.
Кроме того по некоторым исходным данным результат "умного" алгоритма хуже "жадного".
Если интересно, могу поделится собственным алгоритмом линейного раскроя, результат получается лучше, но и считает как правило дольше.


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

0.35 МБ