Привет всем
Помогите пожалуйста с алгоритмом решения вот такой задачи
Задача:
есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
росположить их на прямоугольных столах розмером M см на N см
так что бы столов было использовано как можно меньше

Заранее спасибо

Здравствуйте, Delf, Вы писали:

D>Привет всем
D>Помогите пожалуйста с алгоритмом решения вот такой задачи
D>Задача:
D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
D>росположить их на прямоугольных столах розмером M см на N см
D>так что бы столов было использовано как можно меньше

D>Заранее спасибо

Вообще вспомнить сам алгоритм не смогу, но это стандартный алгоритм, я думаю что во многих учебника по оптимизации он точно есть, называется он что-то типа "Оптимальный раскрой листового металла" или ткани. Вобщем помню только, что минимизировать надо обрезки. Поищи в сети что-нибудь с таким названием. Удачи.

Спасибо Анониму за ответ я обизатэльно поищу "Оптимальный раскрой листового металла"
Чтото подобное я правда уже искал
В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
А решить её перебором вобще не возможно(я даже сам сначала пробовал, моя програма перебирала 500 000 комбинацый за секунду но эсли задать больше 30 деталей дохла)

Здравствуйте, Delf, Вы писали:

D>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно

Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.

D>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно

MAG>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.

Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

Здравствуйте, DeaTH FaNG, Вы писали:

DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

А какие есть эвристики для произвольных многоугольников (невыпуклых)? Что можно почитать по этому поводу?

Здравствуйте, Delf, Вы писали:

D>Привет всем
D>Помогите пожалуйста с алгоритмом решения вот такой задачи
D>Задача:
D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
D>росположить их на прямоугольных столах розмером M см на N см
D>так что бы столов было использовано как можно меньше

Что-то очень похожее:http://www.rsdn.ru/File/9700/Flats.zip

Константин

Здравствуйте, DeaTH FaNG, Вы писали:

DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

Буду очень признателен если дадите сылку на доказательство
Может ктото ещо знаэт где евристические алгоритмы по етой задачи достать у меня пока есть только вариант с генетическим алгоритмом

Здравствуйте, klovetski, Вы писали:


K>Что-то очень похожее:http://www.rsdn.ru/File/9700/Flats.zip

K>Константин

Большоє сбасибо за алгоритм
очень оригинальный метод
сечас пишу прогу на Дельфе с использованием етого алгоритма надеюсь будет работать

D>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно

MAG>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.

DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

К этой задаче очевидным образом сводится задача о рюкзаке.

Здравствуйте, Delf, Вы писали:

D>Задача:
D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
D>росположить их на прямоугольных столах розмером M см на N см
D>так что бы столов было использовано как можно меньше

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

А вот для каждого конкретного стола мы имеем задачу двумерного раскроя и упаковки. Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет. Для практического решения этой задачи существуют разноообразные приближенные алгоритмы. В частности, существует довольно простой алгоритм попарного слияния прямоугольников (известный также как алгоритм Ванга). Алгоритм Ванга в чистом виде является переборным алгоритмом, которые дает оптимальное решение среди всевозможных гильотинных размещений (гильотинный раскрой (или размещение) — это раскрой, который может быть получен из исходного куска материала с использованием только "сквозных" разрезов от края до края). С точки зрения исходной задачи такое решение в общем случае оптимальным, разумеется, не будет (несложно построить контрпример), но во многих случаях его качество будет приемлемым. Следует заметить, что даже если мы ограничимся рассмотрением только гильотинных размещений, нахождение оптимального решения все равно будет являться весьма трудоемкой задачей (для большого числа заготовок). Оптимизировать (сократить) перебор можно как такими "беспотерьными" методами, как метод ветвей и границ, так и несложными эвристическими методами.

Здравствуйте, Андрей Тарасевич, Вы писали:


АТ>Если я не ошибаюсь, не верхнем уровне задача может решаться итеративно в соответствии со следующей стратегией: производим оптимальное размещение имеющихся в наличии деталей на первом столе (оптимальное = площадь непокрытой части стола минимальна), и затем рекурсивно переходим к решению этой же задачи для оставшихся столов и оставшихся деталей.

АТ>А вот для каждого конкретного стола мы имеем задачу двумерного раскроя и упаковки. Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет. Для практического решения этой задачи существуют разноообразные приближенные алгоритмы. В частности, существует довольно простой алгоритм попарного слияния прямоугольников (известный также как алгоритм Ванга). Алгоритм Ванга в чистом виде является переборным алгоритмом, которые дает оптимальное решение среди всевозможных гильотинных размещений (гильотинный раскрой (или размещение) — это раскрой, который может быть получен из исходного куска материала с использованием только "сквозных" разрезов от края до края). С точки зрения исходной задачи такое решение в общем случае оптимальным, разумеется, не будет (несложно построить контрпример), но во многих случаях его качество будет приемлемым. Следует заметить, что даже если мы ограничимся рассмотрением только гильотинных размещений, нахождение оптимального решения все равно будет являться весьма трудоемкой задачей (для большого числа заготовок). Оптимизировать (сократить) перебор можно как такими "беспотерьными" методами, как метод ветвей и границ, так и несложными эвристическими методами.

Большоэ спасибо за такой подробный ответ хотя я и не знаю что такое алгоритм Ванга но обизатильно поищу в нете
Вобще то я сильно сомневаюсь что оптимальное размещение фигур на первом столе никак не повлияет на оптимальность размещения на остальных столах и на оптимальность в целом. Но честно говоря контрпример не могу привести хотя потратил на это весь вечер.

D>Большоэ спасибо за такой подробный ответ хотя я и не знаю что такое алгоритм Ванга но обизатильно поищу в нете
D>Вобще то я сильно сомневаюсь что оптимальное размещение фигур на первом столе никак не повлияет на оптимальность размещения на остальных столах и на оптимальность в целом. Но честно говоря контрпример не могу привести хотя потратил на это весь вечер.

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

Пример:
1. Есть Одна Большая Деталь. Настолько большая, что две штуки таких деталей на столе не разместить.
2. Есть куча мелких деталей, причем _все_ они помещаются на стол рядом с большой. Допустим процент выхода при это получается 85%.

3. А вот теперь умножаем задачу, скажем раз в 100.

Какая для нее будет оптимальная раскладка? Правильно, нужно сто раз повторить раскладку первоначального задания.

А как будет поступать вышеуказанный алгоритм? Он выберет мелкие детали и разместит их на одном из листов с выходом 99% (не сомневаюсь, что он это сумеет). Куда положить 100 Больших Деталей теперь? Правильно... на 100 дополнительных листов. Так что результат в конце будет далеко не оптимальный. Причем, как показала моя практика, такие или похожие варианты встречаются нередко.

Конечно, идеального решения быть не может (NP-полнота). Но некоторые эвристики более удачные, некоторые менее. У меня в программе используется следующий алгоритм (правда это гильотинный раскрой):

1. Составляем "базис" из хорошо оптимизированных карт. Грубо говоря это делается так: берется подвыборка деталей и из нее перебором составляется _одна_ карта. Подвыборки формируются так, чтобы карты, полученные из них были _разными_.

После этого у нас есть куча карт (N = ~200-1000), которые оптимальны в некотором роде, но задания они еще не решают.

2. Чтобы решить задание — нужно составить из базиса _решение_. Короче, определить сколько раз какую карту употребить. Употребить можно 0 раз, конечно. Эта задача решается случайным поиском на целочисленном векторе длиной N. Случайный поиск — это случайные изменения целевого вектора, постепенно уменьшающиеся к концу оптимизации. Короче, это та же генетика, но без рекомбинации, а только с мутациями контролируемой силы.

3. Если после шага 2 не все задание исчерпано — переходии к 1 и решаем задачу на остатке...

Теперь по поводу гильотинности. Гильотинность хороша тем, что пространство решения задачи №1 (оптимизация _одной_ карты) резко сужается. Это вследствие того, что работать приходится только с прямоугольниками. А вот вторая часть — целочисленное линейное программирование — остается неизменной и ее можно приспособить и для упаковки.

Если хочешь посравнивать, вот ключевые слова:
Астра-Д, BestCut, Orion, 2D Nesting and Case Packer Optimizer,
Plus 2D, eCutout

Я сравнивал свою программу(ну и алгоритм соответственно eCutout.
Фактически на моем алгоритме достигаются лучшие результаты. К сожалению за это приходится платить временем.

Здравствуйте, Delf, Вы писали:

D>Привет всем
D>Помогите пожалуйста с алгоритмом решения вот такой задачи
D>Задача:
D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
D>росположить их на прямоугольных столах розмером M см на N см
D>так что бы столов было использовано как можно меньше

D>Заранее спасибо

Как к.т.н. скажу: одним из способов решения задачи оптимального ракроя листового материала на прямоугольные заготовки с различными постановками (прямые задачи, обратные и т.д.) являетя метод динамического программирования (Беллмана). Решение получаешь однозначное. Есть четкие оценки машинных затрат применения этого метода по сравнению с полным перебором.
Смотри книжки по оптимальному раскрою листового и не только листового материала. В инете мало информации реально помогающей. Надо идти в библиотеку, в научную естественно (при ВУЗ-ах или от академии наук).

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Здравствуйте, Delf, Вы писали:

"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."

Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.

Здравствуйте, DeaTH FaNG, Вы писали:

D>>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно

MAG>>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.

DF>>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

DF>К этой задаче очевидным образом сводится задача о рюкзаке.

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

D>>>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно

MAG>>>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.

DF>>>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....

DF>>К этой задаче очевидным образом сводится задача о рюкзаке.

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

Давай еще заметим, что линейный раскрой — самый простой случай раскроя. Мы же NP-полную задачу сводим к нашей.

Здравствуйте, Аноним, Вы писали:

А>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."

А>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.

Во-первых. Метод динамического программирования эффективным не назовёшь (мало того, что экспоненциальное время, да ещё и экспоненциальная память).

Во-вторых. эта задача NP-трудна в сильном смысле (Strongly NP-hard), а отсюда следует, что если твой алгоритм динамического программирования выдаёт точное решение, то P==NP, с чем я тебя и поздравляю.

Это о теории, а насчёт практики здесь.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Андрей Тарасевич, Вы писали:

А>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."

А>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.

В том то и дело, что знаю. Причем знаю очень хорошо. Так что бредом, извините, придется назвать Ваше заявление. Во первых, метод динамического программирования не является стандартным методом решения данной задачи. Есть масса других, не менеее "стандартных" методов решения. Во-вторых, ни о какой эффективности решения методм динамического программирования речи, разумеется, быть не может. Задача, как я уже сказал, переборная, и методы типа динамического программирования, "ветвей и границ" и т.п. ничего здесь принципиально поменять не могут. Все это лишь способы более разумной организации перебора. Который, в общем случае, огромен.

LCR>Во-вторых. эта задача NP-трудна в сильном смысле (Strongly NP-hard), а отсюда следует, что если твой алгоритм динамического программирования выдаёт точное решение, то P==NP, с чем я тебя и поздравляю.

LCR>Это о теории, а насчёт практики здесь.

Кстати, насчет NP==P, что вы думаете насчет:
http://www.tarusa.ru/~mit/ENG/eng.html