задача на оптимальное размещение

← →
ДНО (2005-12-01 00:42) [0]

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

← →
Deka © (2005-12-01 10:36) [1]

Может попробовать просто перебором? Пускай комп переберет все варианты и выберет самый оптимальный. Каждый вариант оценивается в процентах и в конце строится топ-3.

← →
ДНО (2005-12-01 19:19) [2]

Можно было бы конечно попробовать простым перебором, но по моим скромным расчетам, общее количество операций перестановки выкроек с тем учетом, что они все влезут на один лист можно вычислить по формуле: (n^n+1)*n. Где n - кол-во выкроек. Так при 10 выкройках получим 1.000.000.000.000 перестановок. Даже если я на пару порядков ошибся это мало что меняет. К тому же в реальной ситуации все выкройки на одном листе разместить редко возможно, а это еще утяжеляет задачу и как следствие кол-во переборов.

← →
vrem (2005-12-01 19:25) [3]

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

← →
ДНО (2005-12-01 21:16) [4]

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

← →
Piero (2005-12-02 10:46) [5]

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

← →
ДНО (2005-12-02 11:13) [6]

нет, это Мих. Мой мыл: sub_inet[@]freemail.ru. Может действительно чего придумаем...

← →
ДНО (2005-12-02 11:15) [7]

извиняюсь, описался. первое предложение читать так: "нет, это не Мих."

← →
Piero (2005-12-02 11:40) [8]

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

← →
han_malign © (2005-12-02 12:38) [9]

Бродит у меня мысль о приближении физической модели утряски(скатывания, всплывания, вымещения), но вот формализовать и оценить "тяжесть" алгоритма даже не пробовал...

← →
ДНО (2005-12-02 14:08) [10]

han_malign, наталкнули на такую мысль. Сделать что-то вроде тетриса, только падающие фигуры мы вольны выбирать сами.

App: eCutout

http://mathworld.wolfram.com/topics/PackingProblems.html

А это - в качестве предлога для размышления о сложности проблемы.

> Piero (02.12.05 10:46) [5]
</I

> ДНО (01.12.05 21:16) [4]

>
мне тоже понадобилось!!!!! пожалуйста кинте и мне!!!
ПОЖАЛУЙСТА оч надо, оч прошу!
dioman[a]tut.by

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

А чего кинуть-то ?

← →
ДНО (2005-12-06 21:44) [15]

//Jeer ©
//App: eCutout

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

//Jeer ©
//http://mathworld.wolfram.com/topics/PackingProblems.html

ага, ссылка интересная, но впр остается и она его ни как не снимает.

задача на оптимальное размещение Найти похожие ветки