| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Разбиение множества |
| Автор: Гость_Prophet 26.6.2004, 21:12 |
| Необходимо распределить конечное множество элементов (для каждго элемента известен размер) по фиксированному числу контейнеров (размер которых известен и одинаков для всех контейнеров). Перебор не годится. Хотелось бы получить ссылку на материалы по теме ( в идеале алгоритм ) Прошу извинить, если это уже было. |
| Автор: Akina 28.6.2004, 08:09 |
| Сортировка элементов по размерам и затем наполнение по нисходящей. |
| Автор: @lex 29.6.2004, 12:22 | ||
данный вариант не обязательно оптимальный ИМХО данная задача является одним из вариантов задачи о рюкзаке... а предложенный выше алгоритм очень похож "жадный" |
| Автор: Akina 29.6.2004, 15:16 | ||||
@lex
|
| Автор: Тиньков 6.7.2004, 08:32 |
| Если заранее известно, что можно разместить ВСЕ предметы и нужно лишь найти правильное размещение, то жадный алгоритм оптимален. |
| Автор: Alex101 6.7.2004, 09:38 |
| Мне кажется, что тут жадный не даст оптимального размещения. Думаю, что тут надо использовать динамическое программирование. |
| Автор: neutrino 31.7.2004, 20:41 |
| Можно поэкспериментировать с генетикой, но требуется много времени. |
| Автор: Yuri Burger 2.8.2004, 10:30 | ||
Блин, народ, уже вторую мессагу вижу с фразой "можно попробывать ГА, но он медленный" - да с чего вы это взяли? Нормально реализованный ГА на задачах подобных описанной дает весьма приемлемое время.. Единственная проблема - алгоритм никогда не останавливается сам и если делать ограничение по времени то никогда не знаешь - нашел ли он оптимальное решение. С другой стороны, на NP задачах (где и нужно применять ГА) вообще трудно говорить об оптимальном решении - на то они и NP ;) И вообще по поводу скорости - подобные задачи обычно не требуют realtime решения, тобишь решаются они один раз (или давольно редко) т.ч. потратить время не жалко (тем более что речь идет не о годах, и даже не о днях ;) А задачу о рюкзаке и о контейнерах моя реализация решела минут 10, и то это время я выдержал "на всякий случай" - конечное решение было не на много лучше решения найденнного за первую минуту... (кстати размер задачи в случае с ГА связан со временем/качеством далего не линейно, тобишь время/гачество изменяется гораздо медленнее размера, что есть гуд). Если же ваш ГА решает эту задачу медленно или "не качественно" ;) то стоит обратить внимание на оценочную функцию и выбранные операторы ГА. |
| Автор: val 2.8.2004, 14:33 |
| А не кажется ли вам, что эту задачу можно свести к задаче о рюкзаке... |
| Автор: neutrino 2.8.2004, 15:24 | ||||
А где это я сказал, что алгоритм медленный? Наоборот самый быстрый. Я имел в виду, что подбор шансов, кросовера, функции мутаций - долгая песня. Кстати, есть ли проги для разработки эволюц. алг.? Добавлено @ 15:31
Оно и верно - за первые несколько поколений эффективность растет очень быстро, а дальше очень медленно. |
| Автор: nanson 19.4.2009, 11:47 |
| это 3DBPP (3-D Bin Packing Problem) ... статью хорошую что-то сейчас не нашел, хотя где-то в инете она была... поищи по фразам 3dbpp, авторы martello, pisinger, vigo... вот ссылка на код по этой статье... http://www.diku.dk/hjemmesider/ansatte/pisinger/test3dbpp.c |
| Автор: GoldFinch 19.4.2009, 19:06 |
| омг некропост, аж 5лет прошло о_О |
| Автор: nanson 25.4.2009, 09:11 |
| нууу, может быть и некро... но я сам сейчас над этой задачей бьюсь, а нормального готового алгоритма найти не могу... |