LINUX.ORG.RU
Форум — Job  

Разовая удаленая работа: Реализация варианта алгоритма 2d упаковки.


0

1

Требуется реализовать один из алгоритмов 2d упаковки.

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

Я реализовал это для прямоугольных объектов, но для произвольных моих знаний не хватает.

Язык реализации любой, единственное дополнительное требование возможность запуска в Виндовс в виде одного экзешника. Я писал на ruby и при помощи rubyscript2exe получал независимый .ехе контейнер.

контакт: sdio4lor@gmail.com

★★★★★

Перебирал как-то все решения укладки пентамино. Долго, но конечно. Может и здесь в первом приближении идти от принципа «растеризации» фигур до квадратной сетки, а потом уточнять точными смещениями и подкрутками?

mclaudt ☆
()
Ответ на: комментарий от mclaudt

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

sdio ★★★★★
() автор топика

Характерная задача для пролога, перебор вариантов с возвратом. А сколько будет этих «фигур», 10, 100, 1000 или миллион? От этого сильно зависит время нахождение оптимального варианта.

Sun-ch ☆
()
Ответ на: комментарий от Sun-ch

> Характерная задача для пролога, перебор вариантов с возвратом.

Совершенно не характерна для пролога. Тупой перебор здесь не будет работать.

ss-v
()
Ответ на: комментарий от Sun-ch

> Алгоритм оптимального раскроя материалов можно отнести к классу NP-полных задач, не?

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

ss-v
()

Про оптимальность тут ни слова. Была у меня точно такая лабораторная, на borland c++ делал, как сейчас помню, даже с визуализацией процесса. Правда, вращать можно только на угол кратный 90. Поищу на винте, может осталась.
Вот что в инете есть:
http://www.devx.com/dotnet/Article/36005
http://web.archive.org/web/20070812094746/blog.netxus.es/demos/RectanglePacker/

SOmni ★★
()
Ответ на: комментарий от ss-v

>задача непрерывной оптимизации

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

ЗЫЖ Работы (Гольдберг, 1989; Голланд, 1992)

   

Sun-ch ☆
()
Ответ на: комментарий от Sun-ch

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

Sun-ch ☆
()
Ответ на: комментарий от Sun-ch

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

Да уж, ты пролог-то хоть в глаза видел? Что такое эволюционные алгоритмы и как они работают представляешь?

ss-v
()
Ответ на: комментарий от ss-v

Обчитались википедии, и давай всяку х..ню писать...

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Job