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

алгоритм: оптимальное заполнение


0

0


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

дано: два множества A и B. каждое из них представляет собой набор неких блоков, которые в свою очередь имеют какой-то произвольный размер.

задача: распределить блоки из множества A в множестве B таким образом, чтобы все блоки поместились или же сказать, что такое размещение не возможно если это так. при размещении блоки не могут делиться или перекрывать друг друга. полученное взаимное расположение блоков из A в B друг относительно друга не важно.

пример1: A = {10, 10, 10}, B = {40}. укладывая блоки из A в B последовательно один за другим мы достигнем желаемого и ещё останется хвостик[и] - распределение возможно.
пример2: A = {10, 20}, B = {15, 25}. первый идёт в первый, второй во второй - распределение возможно.
пример3: A = {10, 20, 30}, B = {10, 20, 10, 20 }. распределение невозможно.

ps: реальные размеры множеств могут быть достаточно большими, i.e. тысячи/сотни тысяч объектов в каждом из них.

// wbr

← Преобразование типов в C++
Создание OpenOffice odt файлов →
Ответ на: комментарий от wfrr

ну в принципе конечно да, про упаковку я вспомнил, но AFAIU у меня требования несколько мягче, т.е. не нужно добиваться наиболее оптимального распределения, вполне достаточно хоть какого-то шоб влезло :) впрочем, совсем не уверен, что это послабление в условии что-то даст.

// wbr

klalafuda ★☆☆
() автор топика
Ответ на: комментарий от nikolayd

> На РСДН?

а где именно, если не секрет?

// wbr

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

А объектов много? Если не критично можно и случайным поиском сделать. А вообще обычное решение таких проблем: эвристики, "умный муравей", имитация отжига, генетика. Простые реализации этих способов пишутся в один заход.

bik ★★
()
Ответ на: комментарий от bik


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

> А объектов много?

в принципе объектов их может быть много - сотни тысяч - но давайте для определённости все-таки упростим задачу. скажем, что характерное число контейнеров исчисляется сотнями а грузовиков - десятками. можно даже в принципе задать их прикидочное соотношение. допустим, что характерное соотношение веса контейнера к вместимости грузовика лежит где-то в районе 1:5...1:10. хотя могут быть и очень тяжёлые контейнеры и маленькие грузовики.

> Если не критично можно и случайным поиском сделать.

а это как?

> А вообще обычное решение таких проблем: эвристики, "умный муравей", имитация отжига, генетика. Простые реализации этих способов пишутся в один заход.

только что посмотрел Кнута - ничего не нашёл, хотя казалось бы (т. I и III) :( не то смотрел?

// wbr

klalafuda ★☆☆
() автор топика
Ответ на: комментарий от wfrr

на что именно? "генетика" - генетические алгоритмы. информации и открытых реализаций полно; "муравей" - Ant Colony Optimization (ACO); "имитация отжига" - swarm optimization(применяется в частности в обучении нейронных сетей). "эвристики" - нечеткий логический вывод Мамдани/Цукамото/Такаги вкупе с той же генетикой, нейронными сетями(anfis)

bik ★★
()
Ответ на: комментарий от klalafuda

>> Если не критично можно и случайным поиском сделать.

>а это как?

Монте-Карло. Особенно если есть под рукой кластер =)

WerNA ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Преобразование типов в C++
Development
Создание OpenOffice odt файлов →