Нужен алгоритм...
Всем привет!
Вот такая вот проблемка...
Есть некоторая прямоугольная область MxN и много прямоугольных "кусков" размером меньше этой области. Задача в том, чтобы как можно плотнее заполнить эту область, т.е. нужно по очереди добавлять каждую часть по определенным координатам, причем так, чтобы в конце оставшаяся неиспользуемая площадь была как можно меньше.
Где-то слышал об алгоритме, который решает такие задачи, но уже не помню.
Объясните пожалуйста в общих чертах принцип, или название алгоритма подскажите, чтоб я сам мог в инете поискать...
Заранее спасибо!
Вот такая вот проблемка...
Есть некоторая прямоугольная область MxN и много прямоугольных "кусков" размером меньше этой области. Задача в том, чтобы как можно плотнее заполнить эту область, т.е. нужно по очереди добавлять каждую часть по определенным координатам, причем так, чтобы в конце оставшаяся неиспользуемая площадь была как можно меньше.
Где-то слышал об алгоритме, который решает такие задачи, но уже не помню.
Объясните пожалуйста в общих чертах принцип, или название алгоритма подскажите, чтоб я сам мог в инете поискать...
Заранее спасибо!
Спасибо, пока, оставь себе.
Алгоритм...
В левый верхний угол помещаешь первый прямоугольник, за ним (справа) второй, <...> так пока не дойдешь до края. переходишь на новую строку. У левого края максимально высоко укладываешь следующий пр-ник (не поместившийся в первой строке) Так кидаешь прямоугольники пока они не коньчатся или не кончится место. Запоминаешь размер незаполненной области.
Перебираешь все варианты (их N!) и в конце концов находишь лучшй.
P.S. Все это работать будет долго, некрасиво, но будет.
Алгоритм...
В левый верхний угол помещаешь первый прямоугольник, за ним (справа) второй, <...> так пока не дойдешь до края. переходишь на новую строку. У левого края максимально высоко укладываешь следующий пр-ник (не поместившийся в первой строке) Так кидаешь прямоугольники пока они не коньчатся или не кончится место. Запоминаешь размер незаполненной области.
Перебираешь все варианты (их N!) и в конце концов находишь лучшй.
P.S. Все это работать будет долго, некрасиво, но будет.
Полный перебор конечно отпадает, я вообще считаю что полный перебор целесообразно использовать только при количестве елементов не более 10.
Я бы решал эту задачу так:
Укладываю прямоугольники начиная с самого большого (тут надо еще определить что такое самый большой - или большой по площади или габариты). Потом доставляю деталь в ту сторону которая короче (что бы занятая область вырастала равномерно в оба направления). Вот походу и все.
Этот алгоритм не даст 100% максимального заполнения, но будет близок к этому.
Для модернизации надо более разумно продумать установку следующего прямоугольника (проверять помещается ли он в уже получившиеся пробелы и т.д.)
Это пока все что взбрело в голову.
Кстати это задача олимпиадная, где-то обласного уровня, я ее еще в лицее решал, причем таким методом.
Так что можеш поискать на сайтах с олимпиадными задачами, может исходник есть. Но я бы советовал написать самому - это в сотни раз полезнее.
Я бы решал эту задачу так:
Укладываю прямоугольники начиная с самого большого (тут надо еще определить что такое самый большой - или большой по площади или габариты). Потом доставляю деталь в ту сторону которая короче (что бы занятая область вырастала равномерно в оба направления). Вот походу и все.
Этот алгоритм не даст 100% максимального заполнения, но будет близок к этому.
Для модернизации надо более разумно продумать установку следующего прямоугольника (проверять помещается ли он в уже получившиеся пробелы и т.д.)
Это пока все что взбрело в голову.
Кстати это задача олимпиадная, где-то обласного уровня, я ее еще в лицее решал, причем таким методом.
Так что можеш поискать на сайтах с олимпиадными задачами, может исходник есть. Но я бы советовал написать самому - это в сотни раз полезнее.
Цитата:
Originally posted by gnome
Всем привет!
Вот такая вот проблемка...
Есть некоторая прямоугольная область MxN и много прямоугольных "кусков" размером меньше этой области. Задача в том, чтобы как можно плотнее заполнить эту область, т.е. нужно по очереди добавлять каждую часть по определенным координатам, причем так, чтобы в конце оставшаяся неиспользуемая площадь была как можно меньше.
Где-то слышал об алгоритме, который решает такие задачи, но уже не помню.
Объясните пожалуйста в общих чертах принцип, или название алгоритма подскажите, чтоб я сам мог в инете поискать...
Заранее спасибо!
Всем привет!
Вот такая вот проблемка...
Есть некоторая прямоугольная область MxN и много прямоугольных "кусков" размером меньше этой области. Задача в том, чтобы как можно плотнее заполнить эту область, т.е. нужно по очереди добавлять каждую часть по определенным координатам, причем так, чтобы в конце оставшаяся неиспользуемая площадь была как можно меньше.
Где-то слышал об алгоритме, который решает такие задачи, но уже не помню.
Объясните пожалуйста в общих чертах принцип, или название алгоритма подскажите, чтоб я сам мог в инете поискать...
Заранее спасибо!
Почитай книгу Морозов А.Д. "Введение в теорию фракталов"
Цитата:
Originally posted by Matush
Полный перебор конечно отпадает, я вообще считаю что полный перебор целесообразно использовать только при количестве елементов не более 10.
Я бы решал эту задачу так:
Укладываю прямоугольники начиная с самого большого (тут надо еще определить что такое самый большой - или большой по площади или габариты). Потом доставляю деталь в ту сторону которая короче (что бы занятая область вырастала равномерно в оба направления). Вот походу и все.
Этот алгоритм не даст 100% максимального заполнения, но будет близок к этому.
Для модернизации надо более разумно продумать установку следующего прямоугольника (проверять помещается ли он в уже получившиеся пробелы и т.д.)
Полный перебор конечно отпадает, я вообще считаю что полный перебор целесообразно использовать только при количестве елементов не более 10.
Я бы решал эту задачу так:
Укладываю прямоугольники начиная с самого большого (тут надо еще определить что такое самый большой - или большой по площади или габариты). Потом доставляю деталь в ту сторону которая короче (что бы занятая область вырастала равномерно в оба направления). Вот походу и все.
Этот алгоритм не даст 100% максимального заполнения, но будет близок к этому.
Для модернизации надо более разумно продумать установку следующего прямоугольника (проверять помещается ли он в уже получившиеся пробелы и т.д.)
Для некоторых задач еще не придуманы лучшие алгоритмы как перебор! (Конечно, к данной это не относится). Да, предложенный алгоритм конечно не даст максимальное заполнение, а нужно то как раз максимальное. А что, касается насчет близости к максимуму, это не верно, можно подобрать такой случай, когда данный алгоритм даст плохое решение (ведь в наилучшем случае может случиться так что деталь с наибольшими габаритами будет лежать в середине области...)