[Shpur]

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

[Do$]

Вы бы поподробнее задачу описали, да еще бы с примерами...

[Shpur]

Извольте. Допустим мне нужно сделать металлический ящик, ну можно сказать что то типа сейфа. Задаются Параметры ящика: длина, ширина, выоста, сиречь a,b,c
Итак, в самом просто варианте без у чета всяких наворотов сие выглядит так
у ящика 6 стенок - передняя, задняя (a*c), дно/верх (a*b), боковые (b*c).
Есть лист металла с поределенными параметрами l -длина, h- ширина.
Мне нужно написать прогу расчета оптимального раскроя данного листа, и посчитать сколько металла уйдет на 1 ящик. Резка гильотинная

[Do$]

Сообщение от Shpur Резка гильотинная

То есть, разрез может быть только прямолинейным и от края до края?

Сообщение от Shpur метод долбления листа на карты, мне не подходит

А это что за метод?

[Shpur]

1. Да. От края до края листа
2. Везде где я смотрел там именно алгоритм раскроя на максимальное кол во элементов равных по площади.

[Елпанов Евгений]

странный у вас вопрос.
Что значит, вам нужен алгоритм?
По сути, задача решается любым из алгоритмов, применимых для любых задач.

например:
1. жадный алгоритм
берем самую большую деталь и кладем на лист, потом лист тех же размеров или меньший и так же размещаем на листе... Само собой, размещение возможно только с учетом гильотинной резки.

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

3. абсолютный раскрой - создаем квадратную матрицу, с размерностью равной удвоенному количеству всех деталей и решаем, если нет решений, убираем из матрицы одну деталь и решаем заново. Данный путь, я бы не рекомендовал для большого количества деталей...

ps. а чем не подходят готовые решения?

[Shpur]

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


Вот это мне и надо реализовать. Готовые решения не подходят за невозможностью расковырять сам алгоритм

[Елпанов Евгений]

Тема называется:

Сообщение от Shpur; Алгоритм оптимального гильотинного двумерного раскроя

Сообщение от Shpur Вот это мне и надо реализовать. Готовые решения не подходят за невозможностью расковырять сам алгоритм

Если алгоритм ясен, то не понятно, в чем же вопрос...

[Shpur]

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

[Елпанов Евгений]

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

[Shpur]

Блин((( Влип я.. Спасибо всем за внимание и участие

[hwd]

Сообщение от Shpur Блин((( Влип я.. Спасибо всем за внимание и участие

А вариантов листов/ящичков много? Если пару десятков, то может их побыстрому вручную оформить, сохранить и потом из списка выбирать готовые варианты?

[Shpur]

Вариантов? Ну -.. Надо блин еще предусмотреть возможность добавления новых ,но это не проблема.. Так весь прикол в том, что прога высчитывать должна сколько на энное кол во ящиков уйдет листов металла, и наоборот сколько из энного колва металла получится ящиков. За этим и нужен оптимальный раскрой

[hwd]

стенки ящика все прямоугольные? или возможны ящики в виде "сердечка", "цилиндра"?

[Shpur]

Все прямогольные. Это в условии сразу обговаривается

[hwd]

Сообщение от Shpur Я уже неделю парюсь над оптимальным алгоритмом гильотинного раскроя.

Покажешь, чего уже "напарил"?

[Shpur]

Только голую математику. Как ее применить в программном виде не приложу ума. Итак, как я понимаю.
n- кол во деталей всего
ищем деталей с максимальной длиной
max:=l[1];
For i:=2 to n do
begin
if l[i]> max then max:=l[i];
end;
Нашли детальку с максимальной длиной.. потом надо как то ее разместить сиречь сразу показать границу обреза ну тут тоже ничего сложного
//LL-длина железного листа целого
lobr - длина обрезанного
НН - ширина целого листа
lobr:= LL-max;
И тут встает первая проблема
Если фигура расположена неудачно ее надо повернуть, в таком случае шиина с длиной меняются местами
Даже если это отбросить в результате обрезки у нас получаются прямоугольника с параметрами:
max*HH
Lobr*HH

что тут делать дальше я и застрял. Я знаю что тут надо писать процесс генерации оптимальных карт раскроя. Вот я и не врублюсь как это делается.
Но если плясать от изложенного выше то в -м прямоуголнике с размерностью max*HH, Сходу надо отчечь ширину уже готовой детали пусть это будет h
Итого в нашем расоряжении прямоугольник
max*HH-h
И опять перебирать детали, какая из них сюда поместится так чтобы остался минимум свободного места

[GRIFEL]

http://lee-mac.com/boundingboxreactor.html Посмотри здесь - могут возникнуть интересные идеи - хотя все наоборот тут - лист вокруг заготовок .......

[romanew]

Сообщение от Елпанов Евгений странный у вас вопрос. 3. абсолютный раскрой - создаем квадратную матрицу, с размерностью равной удвоенному количеству всех деталей и решаем, если нет решений, убираем из матрицы одну деталь и решаем заново. Данный путь, я бы не рекомендовал для большого количества деталей...

а можешь поподробнее рассказать про это, или ссылку какуюнибудь или еще чонить?..) поискал в инете, не нашел, имею подобную задачу - есть прямоугольник большой и много маленьких, требуется ответить поместятся маленькие в большом или нет, на Си , С++ ...) вот , нашел кое какие алгоритмы, но они печальны, завтро еще с преподавателем поговорю..