Задача минимизации группировки

[OtherSide]

Есть блоки длиной 1..M и Ширина экрана N

Блоки идут по порядку, если есть место в строке для размещения следующего - добавляется в строку, иначе перенос строки

Нужно отсортировать блоки для минимизации места на экране. Я пока что просто сортирую по убыванию длины, но понятно что это не оптимально.

Есть какой-то стандартный алгоритм под это дело, не напомните?
Прямой перебор - это сложность по факториалу, а самому придумывать что то лень (думаю реально займет день), задача не так уж и важна,

[OtherSide]

Вспомнил, есть задача упаковки, но там у прямоугольников разная ширина и высота, а у меня высота = const

[AndreyT]

Вспомнил, есть задача упаковки, но там у прямоугольников разная ширина и высота, а у меня высота = const

Задачи раскроя-упаковки бывают одномерные, двумерные, трехмерные и т.д. Ваша - классическая задача одномерного раскроя-упаковки. Задача NP-трудная, т.е. эффективных алгоритмов для поиска оптимального решения нет. Если вас не интересует гарантированная оптимальность решения, то простейшие эвристические алгоритмы дадут неплохой результат ("best fit decreasing", "first fit decreasing" и т.п.). А если нужно именно оптимальное решение - то либо перебор с отсечением (branch&cut), либо динамическое программирование.

[OtherSide]

Спасибо! Пока вот что удалось нагуглить

http://www.martinbroadhurst.com/bin-packing.html

[tessob]

то либо перебор с отсечением (branch&cut)

Будет очень сомнительная эффективность у такого алгоритма, т.к. перестановка отдельных элементов в строке никак не повлияет на оптимизируемую функцию.

@OtherSide: Я бы на вскидку попробовал что-то вроде интерпретации "Simulated annealing":
1. Сгенерировал бы случайную последовательность элементов.
2. Рандомно переставлял бы элементы попарно между строками. Если перестановка улучшает целевую функцию, то оставлять. Если нет, то реализовать любую функцию вероятности, которая будет затухать от времени/итераций, постепенно снижая шанс выигрыша "плохой" перестановки. Иначе говоря плохая комбинация тоже должна иметь шанс быть принятой. Но со временем шанс должен стремиться к нулю.

Если есть возможность считать это на ГПУ, то это хорошо распараллеливается.

[OtherSide]

У меня порядка 10 элементов и javascript. На сервере не посчитать, потому что неизвестно какой экран у юзера.
Да и задача не такой уж важности, +/- одна лишняя строка на экране. Если готовый код не откопипастить, то и фиг с ним.

[AndreyT]

то либо перебор с отсечением (branch&cut)

Будет очень сомнительная эффективность у такого алгоритма, т.к. перестановка отдельных элементов в строке никак не повлияет на оптимизируемую функцию.

К алгоритму как таковому это замечание не имеет никакого отношения вообще. И ежу понятно, что данная задача решается с точностью до порядка расположения блоков в каждой строке, т.е. порядок в строке не важен.

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

[OtherSide]

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

[Ion Tichy]

А эта задачка никак к линейному програмированию не относится? Если да, то библиотек с решалками ЛП вроде б до фига.

[Ion Tichy]

Вспомнил, есть задача упаковки, но там у прямоугольников разная ширина и высота, а у меня высота = const

Высота = конст есть частный случай произвольных высот, не?

[OtherSide]

Вспомнил, есть задача упаковки, но там у прямоугольников разная ширина и высота, а у меня высота = const

Высота = конст есть частный случай произвольных высот, не?

Частное решение бывает найти проще, чем общее, не?

[AndreyT]

Высота = конст есть частный случай произвольных высот, не?

<сарказм>
Да. Точно также так как любая одномерная задача является частным случаем десятимерной задачи, в которой входные данные просто по какому-то странному стечению обстоятельств оказались лежащими на одной прямой.
</сарказм>

[tessob]

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

OtherSide, очень многое у Вас будет еще зависеть от возможности введения эвристик. Например, если вы знаете что максимальная длинна строки - 4 элемента, то для 10 элементов это всего 210 возможных комбинаций. Троек 120. Двоек 45. В итоге у вас получится гораздо меньшее число возможных комбинаций, чем факториал 10.

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