Поскольку речь идёт о прямоугольниках, то задача решается независимо для горизонтального и вертикального направлений, если считать допустимым, что проекции блоков на прямую накладываются друг на друга. Тогда нужно минимизировать ненакладывающиеся части отрезков и сделать одинаковыми отрезки между блоками.
Думаю, с 1D случаем справиться будет легче. По крайней мере полученное таким образом решение будет некой основой, которую можно попробовать улучшать. Решать сразу 2D случай - сложнее и мозгов участвующих может не хватить.
Добавлено через 2 часа, 13 минут и 2 секунды:Пусть у нас страница выглядит примерно так: вертикальное размещение приемлемое, горизонтальное - нет. Будем считать, что каждый блок имеет вес 1 (если хочется, весом можно взять высоту блока). Тогда проекция блоков по горизонтали создаёт ступенчатую "функцию" от ширины листа. Все вертикальные границы блоков как бы продлены на всю высоту листа.
Это можно кодировать массивом точек, что наглядно, но требует много данных:
(0, 0, 1, 2, 2, 1, 1, 0, 1, 1, 1, 1, 0)
Либо (что актуально для больших страниц, имеющих метрические размеры), её можно кодировать массивом структур вида (уровень, длина):
((0, 2), (1, 1), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)). Это менее наглядно, зато удобнее для алгоритмической обработки.
Предположим, что нормальным расстоянием между краями блоков является 2 и более. Тогда во втором представлении элементарно находятся проблемные места: (+, (1, 1), +, +, (0, 1), +, (0, 1)). Если расстояние меньше допустимого, значит в этом проблемном месте нужно "склеить" или "растолкать" границы блоков. Делать это в каждом случае можно двумя способами: либо уменьшить длину левого хорошего участка и увеличить длину текущего плохого на нужную величину, либо уменьшить длину правого плохого участка и увеличить длину текущего плохого на нужную величину. Каждая такая перестановка может:
- превратить соседний хороший участок в участок 0-й длины - такой участок можно смело выкинуть, если его уровень 0, иначе это потребует ликвидации блоков, что неприемлемо;
- превратить соседний участок в плохой, оставив плохим текущий участок - если при этом суммарный дефицит длин участков уменьшился, это хорошее преобразование, иначе - плохое (вроде бы не должен уменьшаться дефицит);
- превратить соседний участок в плохой, сделав текущий участок хорошим (вроде бы это не даст уменьшения дефицита);
- сохранить соседний участок хорошим, сделав текущий участок тоже хорошим - однозначно положительное преобразование, устраняющее дефицит.
В рассматриваемом примере исходный дефицит длин составляет 3.
Возможные в данном случае варианты модификаций.
(
(0, 1), (1, 2), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
((0, 2),
(1, 2), (2, 1), (1, 2), (0, 1), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
(
(0, 3), (1, 0), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)) - ликвидация блока, не принимается
((0, 2), (1, 1), (2, 2),
(1, 1), (0, 2), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
((0, 2), (1, 1), (2, 2), (1, 2),
(0, 2), (1, 3), (0, 1)) - дефицит 2, полезно, принимается
((0, 2), (1, 1), (2, 2), (1, 2), (0, 1),
(1, 3), (0, 2)) - дефицит 2, полезно, принимается
Для дальнейших действий выберем любую лучшую из получившихся конфигураций. Пусть:
((0, 2), (1, 1), (2, 2), (1, 2), (0, 2), (1, 3), (0, 1))
Повторяя аналогичный процесс, получим ещё более хорошую конфигурацию:
((0, 2), (1, 1), (2, 2), (1, 2), (0, 2), (1, 2), (0, 2))
с дефицитом 1. После чего вышеизложенным способом дальнейших улучшений не получить.
Тогда нужно уточнить правило удаления блоков. Всякий блок может получить длину 0 и быть удалённым только при условии, что его длина будет прибавлена к блоку с более высоким уровнем.
В данном случае:
(
(0, 3), (1, 0), (2, 2), (1, 2), (0, 2), (1, 2), (0, 2)) - неприемлемо, так как увеличился блок меньшего уровня 0 за счёт блока большего уровня 1.
((0, 2),
(1, 0), (2, 3), (1, 2), (0, 2), (1, 2), (0, 2)) - приемлемо, так как увеличился блок большего уровня 2 за счёт блока меньшего уровня 1. При этом дефицит стал 0.
Итак, найдено одно из возможных оптимальных решений:
((0, 2), (2, 3), (1, 2), (0, 2), (1, 2), (0, 2))
или
(0, 0, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0)
