| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
задача на оптимальное размещение
ДНО © (2005-12-01 00:42:00)Есть лист (бумаги, двп...) и есть выкройки. Выкройки нужно как можно оптимальнее разместить на листе. Есть ли какие-нибудь алгоритмы способные в этом помочь. Или может укажите в какую сторону копать...
ДНО (2005-12-06 21:44:00) [1]//Jeer ©
//App: eCutout
ну и что, я тоже могу указать не на одну программу. Приступая к решению той или иной задачи всегда почву под ногами надо прощупывать, что бы в итоге лишнюю работы не делать.
//Jeer ©
// http://mathworld.wolfram.com/topics/PackingProblems.html
ага, ссылка интересная, но впр остается и она его ни как не снимает.
Piero (2005-12-06 13:25:00) [2]А чего кинуть-то ?
Dioman (2005-12-06 12:26:00) [3]
> Piero (02.12.05 10:46) [5]
</I
> ДНО (01.12.05 21:16) [4]
>
мне тоже понадобилось!!!!! пожалуйста кинте и мне!!!
ПОЖАЛУЙСТА оч надо, оч прошу!
dioman[a]tut.by
зарание спасибо
Jeer (2005-12-02 14:39:00) [4]http://mathworld.wolfram.com/topics/PackingProblems.html
А это - в качестве предлога для размышления о сложности проблемы.
Jeer (2005-12-02 14:27:00) [5]App: eCutout
ДНО (2005-12-02 14:08:00) [6]han_malign, наталкнули на такую мысль. Сделать что-то вроде тетриса, только падающие фигуры мы вольны выбирать сами.
han_malign (2005-12-02 12:38:00) [7]Бродит у меня мысль о приближении физической модели утряски(скатывания, всплывания, вымещения), но вот формализовать и оценить "тяжесть" алгоритма даже не пробовал...
Piero (2005-12-02 11:40:00) [8]ладно передам, у него там фигуры (треугольники разные, круги и т. д. ) различного размера, количество - фиксировано, и надо потратить как можно меньше листов выкройки.
ДНО (2005-12-02 11:15:00) [9]извиняюсь, описался. первое предложение читать так: "нет, это не Мих."
ДНО (2005-12-02 11:13:00) [10]нет, это Мих. Мой мыл: sub_inet[@]freemail.ru. Может действительно чего придумаем...
Piero (2005-12-02 10:46:00) [11]Мой одногрупник получил подобную задачу в качестве диплома, могу дать почту, может пообщаетесь продуктивно.
Или это ты Мих?
ДНО (2005-12-01 21:16:00) [12]vrem, вообще, да..., надо подумаю над этой мыслью.
У самого пока только такая мысль: сортировать выкройки по размерам, затем пытаться уместить самые большие выкройки столько раз на лист, сколько влезут, в оставшиеся место пытаться размещать выкройки поменьше. Но не всегда, и даже далеко, не оптимально. Ваша мысль, vrem, мне нравиться больше.
vrem (2005-12-01 19:25:00) [13]Мысль - прямоугольная выкройка самая удобная для размещения. Комбинировать выкройки одна с другой для определения пар, которые лучше всего дополняют друг друга до прямоугольного состояния. Ну или тройки выкроек(вообще по выкройкам посмотреть сколько штук удобнее). А потом размещать уже близкие к прямоугольным части..
ДНО (2005-12-01 19:19:00) [14]Можно было бы конечно попробовать простым перебором, но по моим скромным расчетам, общее количество операций перестановки выкроек с тем учетом, что они все влезут на один лист можно вычислить по формуле: (n^n+1)*n. Где n - кол-во выкроек. Так при 10 выкройках получим 1.000.000.000.000 перестановок. Даже если я на пару порядков ошибся это мало что меняет. К тому же в реальной ситуации все выкройки на одном листе разместить редко возможно, а это еще утяжеляет задачу и как следствие кол-во переборов.
Deka (2005-12-01 10:36:00) [15]Может попробовать просто перебором? Пускай комп переберет все варианты и выберет самый оптимальный. Каждый вариант оценивается в процентах и в конце строится топ-3.
| |
