Не могу придумать алгоритм

[Nadgil]

Всем привет!

Задача такая:

Есть прямоугольный жестяной лист, ширина постоянная - 120 см, длина его до 300 см (по необходимости). Из этого листа нужно вырезать прямоугольные куски со сторонами a и b (переменные). Смысл задачи в следующем нужно, чтобы программа, после того, как пользователь введёт количество прямоугольников и их параметры, просчитала все возможные варианты расположения этих прямоугольных кусочков на листе и предложила наиболее выгодный, т.е. тот вариант при котором отходов будет как можно меньше. Ну и в последующем картинку выведет на печать.

Может кто писал уже подобные вещи? Или видел в сети?

Может у кого-нибудь есть идеи как реализовать процесс проверки - я уже что только не перепробовал - не получается.

Заранее благодарен!!!

[Васильевич]

Таких программ мне известно, по крайней мере, две. Обе московские - одна фирмы "Лего" для раскроя ткани, вторая - автора-одиночки, увы, не помню точных атрибутов, предназначена для раскроя жестяных листов. Обе платные, вторая хранилась на www.freeware.ru. Я не вникал в тонкости алгоритма. Но, если бы такой программой занялся я сам, скорее всего, в основе была бы формула Лапласа для определения площади сегментов.

[mmap]

Можно решить задачу влоб.

Если кусок со сторонами a и b - не квадрат, то он может лежать либо вертикально, либо горизонтально.

Ну и тогда рекурсией перебераешь все возможные варианты...

P.S.:

Этот способ ооочень долгий и плохой..

[Тролль]

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

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

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

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

[Gorshok23]

Во-первых надо сравнить пропорциональность сторон листа и заданных сторон прямоугольников. сходя из этого распологаешь соответственно заданные прямоугольники!

Процесс проверки можно организовать следующим способом:

для VB есть мето Point(x,y) х и у - координаты любой точки, выдает число от 0 до 16777216, это цвет! Если прямоугольники будут одного цвета, а лист другого ты получишь примерную картину расположения прямоугольников! (цвет можно рассчитать по формуле Point(x,y)=256*256*B+256*G+R? где B, G, R - соответсвенно колическво синего, зеленого и красногго)!

[kvazimoda]

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

[Nadgil]

kvazimoda это не практично - будет большой расход материала

[Тролль]

kvazimoda

Идея правильная - это несколько недоделанный "алгоритм левого нижнего угла", но дело в том, что и алгоритм левого нижнего угла относится к категории эвристических, то есть лучше, чем ничего, но все же неточно. На самом деле для таких вещей есть довольно сложные теории, как и вообще во всей области поиска оптимальных решений.

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

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

В данном случае решение - для специалистов по алгоритмам. Дело в том, что компьютерное дело состоит из трех частей - hardware, software и еще одна вещь, для которой используется, хотя и довольно редко, термин brainware - алгоритмы (советую прочитать об этом интервью с академиком Журавлевым, его и вообще прочитать интересно). Например, классический трехтомник Кнута - это почти в чистом виде brainware. Программисты чаще всего используют brainware в виде готовых библиотек программ, реализующих алгоритмы - поиск, организация стека, работа с деревьями, коллекции... Нельзя что-то придумывать, не зная решений аналогичных задач, получается всегда первый вариант велосипеда. Что-то из этого дают при изучении программирования, но очень мало и к тому же практически этим почти никто не занимается - большинство таких вещи уже реализованы в виде стандартных библиотек. И самому изобретать, скажем, алгоритмы поиска или работу с хэш-таблицами не стоит. Тем более что даже хороший алгоритм решения квадратного уравнения на компьютере должен обходить кое-какие невидимые неспециалисту подводные камни.

[-= MFM =-]

Вот выложил пару страниц, из одной

книжонки, как раз по твоему вопросу

1 - 2 - 3 - 4 - 5 - 6

:D B) :)

[Gorshok23]

http://online.download.ru/Download/[ProgramID=6067] ссылка условно беспланой программы. На этом сайте есть и другие подобные посмотри!