Коллекция алгоритмов, в помощь начинающим Опции

[Сладкая Смерть]

Алгоритм Дейкстры
Неплохой такой алгоритм, я его в дипломе использовала для 3D навигации по универу. Ищет кратчайший путь до заданного объекта от начальной точки.
Неформальное объяснение

» Кликните сюда для просмотра оффтоп текста.. «

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

Пример
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<\infty, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачеркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачеркнутыми, если до них нельзя добраться. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

Пример кода, который нашла

» Кликните сюда для просмотра оффтоп текста.. «

Поиск кратчайшего пути между двумя вершинами в графе.

Реализация на основе очереди с приоритетами. Сложность порядка O(nlog(n)).

#include <iostream>
#include <set>
#include <vector>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const int MAX = 1001;
const int MAXINT = 1000000000;

int n;
vvii G(MAX);
vi D(MAX, MAXINT);

void Dijkstra(int s)
{
set<ii> Q;
D[s] = 0;
Q.insert(ii(0,s));

while(!Q.empty())
{
ii top = *Q.begin();
Q.erase(Q.begin());
int v = top.second;
int d = top.first;

for (vii::const_iterator it = G[v].begin(); it != G[v].end(); it++)
{
int v2 = it->first;
int cost = it->second;
if (D[v2] > D[v] + cost)
{
if (D[v2] != 1000000000)
{
Q.erase(Q.find(ii(D[v2], v2)));
}
D[v2] = D[v] + cost;
Q.insert(ii(D[v2], v2));
}
}
}
}

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int m, s, t = 0;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0; i < m; i++)
{
int a, b, w = 0;
scanf("%d %d %d", &a, &b, &w);
G[a - 1].push_back(ii(b - 1, w));
G[b - 1].push_back(ii(a - 1, w));
}

Dijkstra(s - 1);

printf("%d\n", D[t - 1]);

return 0;
}

Мой пример (писала в Delphi)

» Кликните сюда для просмотра оффтоп текста.. «

//* uGraph - модуль для работы с графами - алгоритмы на графах

unit uGraph;

interface

uses
uPath;

type
TVertex = record
id : Integer;
x,y,z : Single;
Tag : Integer;
Marked : Boolean;
DistFromStart : Single;
PrevVertex : Integer;
end;

TGraph = class
public
//* Public declarations

M : array of array of Single;
V : array of TVertex;
N : Integer;
Path : TPath;
//*
StartVertex : Integer;
FinishVertex : Integer;
//*
constructor Create;
procedure LoadGraph (const FileName : ShortString);
procedure FindPath (const Tag : Integer );
end;

implementation

//* TGraph *//

procedure TGraph.LoadGraph(const FileName: ShortString);
var
F : TextFile;
i,j : Integer;

begin
AssignFile (F, FileName);
Reset (F);
ReadLn (F, N);

SetLength (M, N, N);
SetLength (V, N);

//

for i := 0 to N-1 do
begin
ReadLn (F, V[i].x, V[i].y, V[i].z, v[i].tag);
StartVertex := 0;
end;

for i := 0 to N-1 do
for j := 0 to N-1 do
begin
try
Read (F, M[i,j]);
except
M[i,j] := 10000000;
end;
end;

//

CloseFile (F);
end;

procedure TGraph.FindPath(const Tag: Integer);
var
i,j : Integer;
NotMarked : Integer;
vm,pv : Integer;
MinDist : Single;

begin
for i := 0 to N-1 do
begin
v[i].Marked := False;
v[i].DistFromStart := M[StartVertex,i];

if M[StartVertex,i] = -1 then
v[i].DistFromStart := 10000000;

v[i].id := i;

if v[i].Tag = Tag then FinishVertex := i;
end;

//*

v[StartVertex].Marked := True;
v[StartVertex].PrevVertex := -1;
NotMarked := N-1;

while NotMarked <> 0 do
begin
MinDist := 10000000;

for i := 0 to N-1 do
if (not v[i].Marked) and (v[i].DistFromStart < MinDist) and (v[i].DistFromStart <> -1) then
begin
vm := i;
MinDist := v[i].DistFromStart;
end;

v[vm].Marked := True;
NotMarked := NotMarked-1;

for i := 0 to N-1 do
if not v[i].Marked then
if (v[i].DistFromStart > v[vm].DistFromStart+M[vm,i]) and
(v[i].DistFromStart <> -1) and (v[vm].DistFromStart <> -1) and
(M[vm,i] <> -1) then
begin
v[i].DistFromStart := v[vm].DistFromStart+M[vm,i];
v[i].PrevVertex := vm;
end;
end;

//*

pv := v[FinishVertex].PrevVertex;
Path.Clear;
Path.AddVertex (v[FinishVertex].x, v[FinishVertex].y, v[FinishVertex].z, v[FinishVertex].Tag);

while pv <> -1 do
if pv <> -1 then
begin
if v[pv].PrevVertex <> -1 then
Path.AddVertex (v[pv].x, v[pv].y, v[pv].z, v[pv].tag);

pv := v[pv].PrevVertex;
end;

//*
end;

constructor TGraph.Create;
begin
Path := TPath.Create;
end;

end.

[Сладкая Смерть]

Волновой поиск

» Кликните сюда для просмотра оффтоп текста.. «

Элементарнейшая вещь. Подходит для карт, которые можно представить в виде двухмерного массива ячеек. Для начала нужно завести ещё один точно такой же массив, как и основная карта. Работает следующим образом:
1. Находим точку A, из которой будет осуществляться поиск и ставим в ней 0. Во всех свободных от препятствий ячейках, прилегающих к ней, пишем 1. Во всех свободных от цифр и препятствий ячейках, прилегающих к ячейкам с цифрой 1, пишем 2. Повторяем этот процесс, пока не доходим до искомой ячейки B. Алгоритм называется волновым потому что если визуализировать этот процесс в динамике, можно увидеть как от точки A разбегается волна из цифр.
2. Теперь строим от точки B до точки A путь по следующему правилу: следующая точка пути должна лежать в ячейке с меньшим, чем в текущей числом.
Алгоритм хорошо справляется с разными тупиками и всегда находит путь если тот существует. Однако, этот путь не всегда кратчайший. Да и сам алгоритм работает медленно, что не позволяет использовать его на больших (>1000 клеток) картах.

Поиск в глубину

» Кликните сюда для просмотра оффтоп текста.. «

Предыдущий алгоритм ещё называется поиском в ширину – он уровень за уровнем просматривает ближайшие клетки. Поиск в глубину выбирает одно направление и просматривает его вглубь на заданное число клеток, переходит к следующему направлению и т.д. пока не отыщется искомая точка. Чтобы найти кратчайший путь, надо вызвать функцию поиска для каждой из клеток, прилегающих к начальной. В вспомогательном массиве Mark такого же размера, как и основная карта хранится 1, если текущая клетка пройдена алгоритмом, и 0 – в противном случае. В переменных dest_x и dest_y должны храниться координаты точки, куда надо найти путь. В переменной length будет храниться длина текущего пути, чтобы он не стал длиннее максимального пути max_length. Вот функция поиска:

int deepsearch(int x, int y){
int i;
if length>max_lenght return 0;
int Mark[x][y];
// Здесь забейте весь массив значениями 1
if (x=dest_x && y=dest+y) {
/* Точка найдена! Исходный путь представлен значениями 1 в массиве Mark. Здесь можно запомнить построенный путь и очистить массив Mark, чтобы продолжить поиск или же остановиться, возвратив 1, если найден хотя бы один путь. */
};
length=length+1;
if Mark[x+1][y]=0 deepsearch(x+1,y);
if Mark[x][y+1]=0 deepsearch(x,y+1);
if Mark[x+1][y+1]=0 deepsearch(x+1,y+1);
if Mark[x-1][y-1]=0 deepsearch(x-1,y-1);
if Mark[x-1][y]=0 deepsearch(x-1,y);
if Mark[x][y-1]=0 deepsearch(x,y-1);
length=length-1
};

Метод Хука-Дживса

» Кликните сюда для просмотра оффтоп текста.. «

Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки , за которой в случае успеха следует поиск по образцу. Он применяется для решения задачи минимизирования функции без учета ограничений .

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной h1 для каждой переменной xj, j = 1, 2,…, n. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.

Б. Вычислить f (х) в базисной точке b1 с целью получения сведений о локальном поведении функции f (x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f(x) в базисной точке b1, находится следующим образом:

1. Вычисляется значение функции f (b1) в базисной точке b1.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b1+h1e1), где e1 – единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1+h1e1. В противном случае вычисляется значение функции f (b1-h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f (b1+h2e2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

3. Если b2=b1, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b2
b1, то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

1. Разумно двигаться из базисной точки b2 в направлении b2-b1, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
P1=b1+2(b2-b1) .

В общем случае

Pi=bi+2(bi+1-bi) .

2. Затем исследование следует продолжать вокруг точки Р1 (Рi) .

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

Модифицированный метод Хука-Дживса

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

Нужно проверить ,каждая ли точка ,полученная в процессе поиска , принадлежит области ограничений .Если каждая , то целевая функция вычисляется обычным путем . Если нет , то целевой функции присваивается очень большое значение . Таким образом , поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.

В тексте прогаммы модифицированного метода прямого поиска Хука-Дживса сделана попытка реализовать такую процедуру. Рассматриваемая задача формулируется следующим образом :

минимизировать f (x1,x2) = 3x12+4x1x2+5x22 ,

при ограничениях x1
x2
x1+x2

program HuDjMody;

(*** Модифицированный метод Хука-Дживса ***)

(*** (при наличии ограничений) ***)

uses crt;

label 0,1,2,3,4,5,6,7;

var k,h,z,ps,bs,fb,fi :real;

i,j,n,fe :integer;

x,y,b,p :array[1..10] of real;

(*** Процедура,вычисляющая функцию ***)

procedure calculate;

begin

z:=3*sqr(x[1])+(4*x[1]*x[2])+(5*sqr(x[2]));

if (x[1]<0) or (x[2]<0) or ((x[1]+x[2])<4) then

z:=1.7e+38;

fe:=fe+1; (*** Счетчик ***)

end;

begin

clrscr;

gotoxy(20,2);

writeln('Модифицированный метод Хука-Дживса');

gotoxy(23,3);

writeln('( при наличии ограничений )');

writeln;

writeln('Введите число переменных:');

readln(n);

writeln;

writeln('Введите начальную точку x1,x2,…,xN');

for i:=1 to n do

readln(x[i]);

writeln;

writeln('Введите длину шага');

readln(h);

writeln;

k:=h;

fe:=0;

for i:=1 to n do

begin

y[i]:=x[i];

p[i]:=x[i];

b[i]:=x[i];

end;

calculate;

fi:=z;

writeln('Начальное значение функции', z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

ps:=0;

bs:=1;

(*** Исследование вокруг базисной точки ***)

j:=1;

fb:=fi;

0: x[j]:=y[j]+k;

calculate;

if z<fi then goto 1;

x[j]:=y[j]-k;

calculate;

if z<fi then goto 1;

x[j]:=y[j];

goto 2;

1: y[j]:=x[j];

2: calculate;

fi:=z;

writeln('Пробный шаг',' ', z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

if j=n then goto 3;

j:=j+1;

goto 0;

3: if fi<fb-1e-08 then goto 6;

(*** После оператора 3,если функция не уменьшилась, ***)

(*** произвести поиск по образцу ***)

if (ps=1) and (bs=0) then

goto 4;

(*** Но если исследование производилось вокруг точки ***)

(*** шаблона PT,и уменьшение функции не было достигнуто,***)

(*** то изменить базисную точку в операторе 4: ***)

(*** в противном случае уменьшить длину шага в операторе***)

(*** 5: ***)

goto 5;

4: for i:=1 to n do

begin

p[i]:=b[i];

y[i]:=b[i];

x[i]:=b[i];

end;

calculate;

bs:=1;

ps:=0;

fi:=z;

fb:=z;

writeln('Замена базисной точки',' ',z:2:3);

for i:=1 to n do

writeln(x[i]:1:3);

(*** (следует за последним комментарием) ***)

(*** и провести исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

5: k:=k/10;

writeln('Уменьшить длину шага');

if k<1e-08 then goto 7;

(*** Если поиск незакончен,то произвести новое ***)

(*** исследование вокруг новой базисной точки ***)

j:=1;

goto 0;

(*** Поиск по образцу ***)

6: for i:=1 to n do

begin

p[i]:=2*y[i]-b[i];

b[i]:=y[i];

x[i]:=p[i];

y[i]:=x[i];

end;

calculate;

fb:=fi;

ps:=1;

bs:=0;

fi:=z;

writeln('Поиск по образцу',' ',z:2:3);

for i:=1 to n do

writeln(x[i]:2:3);

(*** После этого произвести исследование вокруг ***)

(*** последней точки образца ***)

j:=1;

goto 0;

7: writeln('Минимум найден');

for i:=1 to n do

writeln('x(',i,')=',p[i]:2:3);

writeln;

writeln('Минимум функции равен',' ',fb:2:3);

writeln('Количество вычислений функции равно',' ',fe);

repeat until keypressed;

end.

[Пастор]

Про двумерную упаковку: offline алгоритмы

---

Сегодня, дорогой Читатель, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

Как частный случай задачи двумерной упаковки, 2DSP заключается в упаковке объектов конкретной формы в конечное число контейнеров конкретной формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объем объектов (которые упаковывают) были наибольшими. Разница с двумерной упаковкой состоит в том, что есть только один контейнер, и вместо минимизации количества контейнеров, мы минимизируем высоту заполненности одного. Обеспечиваем максимальную плотность упаковки, если хотите.

Так как проблема NP-трудная, исследования сфокусированы главным образом на разработке приближенных алгоритмов решения. (На Хабре упоминался генетический алгоритм). Приближенные алгоритмы находят оптимальное решение с определенной точностью, но не гарантируют оптимальной упаковки для любого набора данных. При этом критерий оптимальности зависит от того, что вы пытались оптимизировать.
Я расскажу о простейших стратегиях и о том, к чему это все применимо в жизни (кроме рюкзака с пивом).

Итак, имеем набор из n прямоугольников и полуограниченный контейнер-стакан с фиксированной шириной W и бесконечной высотой. Каждый прямоугольник по ширине не превышает W. Задача — уложить прямоугольники в стакан без наложений и пересечений так, чтобы стакан стал как можно менее полон. Условимся, что все прямоугольники должны быть упакованы ортогонально, их нельзя поворачивать.

Исходные данные (начало XX века, кубизм)	Полуограниченная полоса	Вариант упаковки (похуже)	Вариант упаковки (получше)

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

Зоопарк алгоритмов

Для offline варианта 2DSP сразу известен размер всех упаковываемых прямоугольников, поэтому их можно отсортировать, выбрать по определенному критерию, сгруппировать или просто натыкать в подходящие места. На этом и основываются большинство алгоритмов:

1. уровневые (level)
2. шельфовые (shelf)
3. плоские (plane)

Плоские алгоритмы размещают прямоугольники строго вплотную друг к другу, но это не самая удачная стратегия, как может показаться на первый взгляд. Уровневые делят полосу на уровни, равные по высоте одному из выбранных прямоугольников, и помещают все остальные на конкретный уровень по определенному критерию. Шельфовые предопределяют сразу несколько шельфов (полок), и распихивают по ним прямоугольники, такое поведение характерно для online-алгоритмов, а это уже совсем другая история.

Чем распространяться на общие слова, лучше обо всем по порядку.

Next Fit Decreasing High

Алгоритм, что называется, «в лоб». Прямоугольники сортируются по не-возрастанию высоты (Decreasing High намекает), самый высокий располагается в левом нижнем углу полосы, тем самым инициализируя первый уровень, по высоте равный ему. Остальные прямоугольники располагаются слева направо, пока есть место на текущем уровне. Прямоугольник, который не поместился на уровне, помещается сверху, образуя следующий уровень, и так далее.
Иллюстрации для каждого алгоритма будут производиться для следующих двух примеров: для наглядности, в левом форма прямоугольников тяготеет к вытянутой, в правом — более квадратные.

Алгоритм NFDH

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles 
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: level = 0; h(level) = 0; w(level) = 0; i = 1
 2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 3: Pack rectangle Li left-justifed at the bottom of the strip
 4: h(level) = h(Li); w(level) = w(Li)
 5: for i = 2..n do
 6:   if W - w(level) ≥ w(Li) then
 7:     pack rectangle Li to the right of rectangle Li-1
 8:     w(level) += w(Li)
 9:   else [W - w(level) < w(Li)]
10:     create a new level above the previous one and pack rectangle Li on the new level
11:     level++; w(level) = w(Li); h(level) = h(level-1) + h(Li)
12:   end if
13: end for
14: print H = h(level)

First Fit Decreasing High

Похожий на предыдущий алгоритм, с той разницей, что для каждого следующего прямоугольника ищется место не только на последнем уровне, а начиная с самого нижнего. Отсюда и «first fit» — прямоугольник помещается на первый подходящий уровень снизу. Интуитивно понятно, что упаковка будет качественнее. Еще одно значительное отличие — в производительности, так как в худшем случае придется рассматривать на каждом шагу все уровни снизу вверх.

Алгоритм FFDH

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: level = 0; h(level) = 0; i = 1; LevelNum = 1
 2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 3: Pack rectangle Li left-justifed at the bottom of the strip; h(level+1) = h(Li)
 4: for i = 2..n do
 5:   search all levels (from the bottom) for the lowest with sufficient space
 6:   if such a level exist then
 7:     pack rectangle Li left justified on that level
 8:   else [there is insufficient space in all existing levels]
 9:     LevelNum++; level = LevelNum; h(level) = h(level-1) + h(Li)
10:     pack rectangle Li on the new level
11:   end if
12: end for
13: print H = h(level)

Best Fit Decreasing High

Модификация предыдущего алгоритма. Суть ее в том, что из уровней, подходящих для упаковки очередного прямоугольника, выбирается не первый, а лучший. Лучший уровень — это такой, на котором останется минимум места после упаковки текущего прямоугольника. Проще говоря, выбирается минимальное подходящее пространство, что способствует лучшему заполнению уровней.

Алгоритм BFDH

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: level = 0; h(level) = 0; i = 1; LevelNum = 1
 2: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 3: Pack rectangle Li left-justifed at the bottom of the strip; h(level+1) = h(Li)
 4: for i = 2..n do
 5:   search all levels for the level with sufficient space and has minimum residual space
 6:   if such a level exist then
 7:     pack rectangle Li left justified on that level
 8:   else [there is insufficient space in all existing levels]
 9:     create a new level above the top-most level and pack rectangle Li
10:     LevelNum++; level = LevelNum; h(level) = h(level-1) + h(Li)
11:   end if
12: end for
13: print H = h(level)

Knapsack 0-1

Здесь стоит остановиться подробнее. Knapsack 0-1 — это частный случай задачи о ранце; примечателен тем, что кроме ответа на основной вопрос (нет, не 42, а полученный объем упаковки) дает еще и решение — список предметов, которые нужно упаковать. Порядок действий таков: прямоугольники сортируются по не-возрастанию высоты; упаковывается первый прямоугольник на новый уровень; для этого уровня находится решение задачи Knapsack 0-1, которое дает нам список прямоугольников, максимизированный по площади. Выбранные прямоугольники пакуются и извлекаются из списка неупакованных, уровень закрывается и открывается новый — инициализированный, как водится, первым (самым высоким) из оставшихся. Повторить, пока есть прямоугольники.

Алгоритм KP01

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 2: level = 0
 3: while there are unpacked rectangles do
 4:   pack first unpacked rectangle, Li say
 5:   h(level) += h(Li)
 6:   solve KP01 instance
 7:   pack selected rectangles
 8:   level = level + 1
 9: end while
10: print H = h(level)

Split Fit

Алгоритм, призванный улучшить FFDN по принципу «разделяй и властвуй». Для начала отбираются прямоугольники, которые шире чем половина полосы. Они будут упакованы в первую очередь. Из них выбираются еще более широкие — шире, чем 2/3 полосы; они упаковываются алгоритмом FFDH. Над ними, начиная со следующего уровня (назовем его уровень R), упаковываются оставшиеся, те, что все еще шире 1/2, но уже 2/3. Они тоже упаковываются с помощью FFDH. Это разделение создает свободный регион шириной 1/3 справа от только что упакованных, начинающийся на уровне R и заканчивающийся текущей верхней границей упаковки (то есть он не простирается выше прямоугольников 1/2 < width <= 2/3). Все оставшиеся прямоугольники, которые уже, чем 1/2 полосы, упаковываются с помощью того же FFDH в первую очередь в образовавшийся регион, а если не помещаются — то сверху. На словах звучит громоздко, на картинке должно быть понятнее. А для тех, кто уже устал от моих литературных упражнений — псевдокод:

Алгоритм SF

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
1: Let m ≥ 1 be the largest integer for which all rectangles in L
   have width at most 1=m
2: Partition the list of rectangles L into two sublists L1 and L2
   such that L1 is a list of rectangles of width greater than
   1/(m+1), while L2 is a list of rectangles of width at most 1/(m+1)
3: Pack the L1 rectangles into the strip, using the FFDH algorithm
4: Rearrange the blocks of this packing such that those of width
   greater than (m+1)/(m+2) are below those of width
   at most (m+1)/(m+2)
5: Pack rectangles of width at most 1/(m+2) into the region R
   using FFDH algorithm such that no rectangle overlaps the top
   of R and those failing to fit in R are packed above the packing of L1
6: Output the height of the strip, found by adding the height of each level

Join

Судя по всему, этот алгоритм был заточен под определенного характера входные данные, что ж, любая практическая ситуация имеет право на существование. Сейчас сами все поймете. Отсортированные, как водится, по не-возрастанию высоты прямоугольники объединяются в пары так, чтобы разница высоты в паре не превышала заданной доли, обычно 0-10%. Еще одно условие — чтобы их суммарная ширина помещалась в полосу. Полученные «супер-прямоугольники» упаковываются вместе с оставшимися без пары с помощью NFDH и FFDH, выбирается лучшее решение.
Существует вариация этого алгоритма, когда прямоугольники сортируются по ширине и объединяются вертикально, с тем же условием максимального отклонения ширины в паре на заданное количество процентов.

Алгоритм Join

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)}, the constant gamma as a
       percentage and the strip width W.
Output: The height of a packing obtained in the strip.
 1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 2: j = 1
 3: while j+1 ≤ n do
 4:   if (h(Lj) - h(Lj+1))/h(Lj) * 100 < gamma
         and w(Lj) + w(Lj+1) ≤ W then
 5:     w(Lj) += w(Lj+1)
 6:     j += 2
 7:   else
 8:     j++
 9:   end if
10: end while
11: Execute the NFDH and FFDH algorithms to pack the rectangles
12: From the best solution, construct a feasible packing of the original instance
13: Output the height of the strip, found by adding the height of each level

Floor Сeiling No Rotation

Если вы все еще недоумеваете по поводу остающегося на уровнях пространства, то этот алгоритм для вас. Прямоугольники сортируются по не-возрастанию высоты (неожиданно, да?) и применяется алгоритм BFDH с некоторыми модификациями. У каждого уровня есть «пол» (floor) и «потолок» (ceiling). Пока есть возможность, прямоугольники пакуются на «пол» слева направо. Когда место заканчивается, предпринимается попытка упаковать на «потолок» справа налево; если нет места на потолке, то только тогда начинается новый уровень. В лучших традициях BFDH, на каждом шагу просматриваются все уровни — сначала «пол», затем «потолок» — на наличие наиболее подходящего места. Упаковка, как видите, неплохая. Метод удачно упаковывает по «потолкам» самые мелкие прямоугольники.

Алгоритм FCNR

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: Sort the rectangles in order of non-increasing height such that h(L1) ≥ h(L2) ≥ ... ≥ h(Ln)
 2: for i = 1..n do
 3:   if Li is ceiling feasible then
 4:     pack Li on ceiling with minimum residual space
 5:   else [Li is not ceiling feasible]
 6:     if Li is floor feasible then
 7:       pack Li on the floor with minimum residual space
 8:     else [Li is not floor feasible]
 9:       level++;
10:     end if
11:   end if
12: end for
13: Output the height H of the strip, found by adding the height of each level

Sleator

Настало время «плоских» алгоритмов, без деления на уровни. Алгоритм Sleator использует интуитивный принцип упаковки рюкзака: сложить на дно самые крупные предметы и засыпать сверху мелкими. Вот как это выглядит. Из прямоугольников выбираются самые широкие, шире половины полосы, как вы уже догадались, и хаотично укладываются друг на друга с выравниванием по левому краю. Оставшиеся сортируются по не-возрастанию высоты и начинают укладываться друг за другом слева направо сверху на уже уложенные. Как только их суммарная ширина превысит половину ширины полосы, оставшиеся раскидываются друг на друга то слева (начиная от левого края полосы), то справа (от середины), по принципу «где на данный момент меньше». Как видно из рисунков, этим методом удобнее укладывать книги, чем коробки.

Алгоритм Sleator

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: Partition L into two sublists L1 and L2 consisting of rectangles
    of width greater than 1/2 and at most 1/2 respectively.
 2: Stack all the rectangles in L1 left justified on top of
    one another starting at the bottom of the strip. Compute Hstack
 3: Packing will continue above Hstack
 4: Sort the rectangles in L2 according to non-increasing height
    such that h(Li) ≥ h(Li+1) for i < n
 5: Let Htall be the height of the tallest rectangle in list L2.
 6: Pack the rectangles, left justified from the left to the right
    edge of the strip until there is insufficient space to pack
    a rectangle or all of the rectangles have been packed
 7: Partition the strip with a vertical line into two equal segments.
    There is possibly one rectangle whose interior may be intercepted
    by the vertical line.
 8: Let Hright and Hleft be the height of the rectangle on the right
    (resp. left) half of the strip whose left (resp. right) edge
    is adjacent to the vertical line or whose interior is intercepted
    by the vertical line
 9: while there are unpacked rectangles do
10:   Draw horizontal lines of length half across
      the rectangles whose height is Hleft and Hright
11:   All subsequent packing will either be on the left
      or right segment of the strip
12:   Select the segment with minimum height and pack
      rectangles from the edge of the strip to the
      vertical line until all rectangles have been
      packed or there is a rectangles which does not fit
13: end while
14: print H = max{Hleft; Hright}

Burke

Снова безуровневый алгоритм, для которого вводится дополнительная «карта высот»:

|               |    |    _   _   ___|
|               |    |   | |_|_| |   |
|               |    |_  | |   | |   |
|_ _ _ _ _ _ _ _| .. |_|_|_|_ _|_|_ _|
 0 0 0 0 0 0 0 0      1 0 3 2 3 0 3 3

Это массив, по которому по мере заполнения полосы можно отслеживать наименее заполненные области и их ширину. В начале он заполнен нулями. Прямоугольники сортируются по не-возрастанию, внезапно, ширины. Затем, на каждом шаге алгоритма:
1. Вычисляется позиция самой низкой области — индекс минимального значения массива;
2. Выбирается наиболее подходящий прямоугольник — во-первых, помещающийся в эту область, во-вторых, максимально ее заполняющий по ширине;
3. Если подходящий прямоугольник найден, он размещается в этой области одним из способов:
3.1 По левому краю области;
3.2 Ближе к более высокому соседу, если один из соседей — край полосы, то ближе к краю;
3.3 Ближе к менее высокому соседу, если один из соседей — край полосы, то дальше от края. К значениям массива, соответствующим ширине прямоугольника, прибавляется его высота.
4. Если подходящего прямоугольника нет, область «заполняется» путем выравнивания ее высоты до высоты ближайшего края.
Вам уже захотелось написать по этому алгоритму бота, играющего в Тетрис?

Алгоритм Burke

Input: The number of rectangles to be packed n,
       the dimensions of the rectangles
       {w(Li); h(Li)} and the strip width W.
Output: The height of a packing obtained in the strip.
 1: Sort the rectangles according to non-increasing width such that w(Li) ≥ w(Li+1) ≥ .. ≥ W(Ln)
 2: for each placement policy
    (leftmost, tallest neighbour, smallest neighbour) do
 3:   while Rectangles not packed do
 4:     find lowest gap
 5:     if w(Li) ≤ GapWidth then
 6:       place best fitting rectangle using placement policy
 7:       raise elements of array to appropriate height
 8:     else
 9:       raise gap to height of the lowest neighbour
10:     end if
11:   end while
12: end for
13: The elements of the array with greatest entry give the total height of the packing
14: Compare total packing heights obtained by each placement policy and return the best solution

Кто лучше?

Результат работы каждого алгоритма — это уровень заполненности полосы, чем меньше, тем лучше. Его можно оценить отношением к нему оптимального:



Сравним полученные результаты для двух приведенных наборов исходных данных:

	Оптимальное решение	NFDH	FFDH	BFDH	KP01	SF	JOIN	FCNR	Sleator	Bruke
Набор 1	149	0,65	0,71	0,71	0,71	0,75	0,61	0,83	0,68	0,72
Набор 2	140	0,66	0,77	0,77	0,78	0,77	0,70	0,84	0,51	0,71

Видим, что для обоих наборов данных победил алгоритм Floor Ceiling. Можно отметить, что Sleator показал гораздо лучший результат для первого набора, а Join, наоборот, больше подходит для второго. Но все это не более, чем статистика.

Эпилог

За счет своей простой формулировки, задача бинарной упаковки может быть подтянута к огромному количеству практических применений: непосредственно к упаковке объектов или раскройке материала, распределению средств, планировке задач на кластерах, etc. В жизни мало рафинированных задач, но, ограничив некоторые условия, можно свести ситуацию к красивой математической модели, имеющей неплохое решение, достижимое за полиномиальное время. А однажды, в результате эффекта бабочки, отброшенные условия возымеют большой вес и решение полетит ко всем Безымянным. Вот из-за таких допущений и несовершенен мир.

Что-то я отвлеклась. В следующей части надеюсь рассказать об online-версии задачи и шельфовых алгоритмах. Good luck!

---

Источники вдохновения:
Nthabiseng Ntene An Algorithmic Approach to the 2D Oriented Strip Packing Problem
David Pisinger Knapsack problem
Survey on two-dimensional packing
Level Algorithms and Shelf Algorithms (осторожно, дизайн-вырви-глаз)

Код (Qt):
Алгоритмы packager.h packager.cpp
Гуй window.h window.cpp renderarea.h renderarea.cpp main.cpp

Wildy

[Пастор]

Про двумерную упаковку: online алгоритмы

---

Это продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

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

Для иллюстрации будет использоваться вот такая последовательность кирпичей:

(Спонсор исходных данных — random.org).
Будут описаны некоторые эвристические алгоритмы, общая идея которых состоит в том, чтобы предварительно разделить полосу на области, и размещать вновь поступающие прямоугольники в конкретной области по определенным критериям.

Level algorithms

Подход всех уровневых алгоритмов в том, что полоса разделяется на уровни, исходя из высоты имеющихся на данном этапе прямоугольников. Прямоугольники размещаются вдоль основания текущего уровня слева направо, пока это возможно; прямоугольник, который не поместился, упаковывается на следующий уровень. Высота каждого уровня определяется по самому высокому прямоугольнику в нем. Вот три варианта упаковки:
Next Fit Level — когда открывается следующий уровень, предыдущий «закрывается» и его больше не рассматриваем;
First Fit Level — на каждом шагу алгоритма просматривается каждый уровень, начиная с самого нижнего, и прямоугольник упаковывается на первый подходящий, на котором достаточно места;
Best Fit Level — на каждом шагу алгоритма просматриваются все уровни, и выбирается наиболее подходящий — тот, на котором после упаковки останется минимум места.
Все три алгоритма проиллюстрированы выше. На этом этапе несложно догадаться, какой где.

Алгоритмы NFL, FFL, BFL

Next Fit Level

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: level = 0; h(level + 1) = 0; H = 0; i = 0
 2: while there is an unpacked rectangle do
 3:    i++
 4:    if there is sufficient space on current level then
 5:       pack rectangle left justified
 6:       if h(level + 1) < h(Li) then
 7:          h(level + 1) = h(Li)
 8:       end if
 9:    else [there is insufficient space on current level]
10:       open a new level and pack the rectangle
11:       H += h(level + 1); level++
12:    end if
13: end while
14: print H and entire packing

First Fit Level

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: level = 0; h(level + 1) = h(L1); H = h(L1); i = 1
 2: while there is an unpacked rectangle do
 3:    i++; level = 0
 4:    search for the lowest level with sufficient space
 5:    if such a level exists then
 6:       pack rectangle left justified
 7:       if this is the top-most level and h(level) < h(Li) then
 8:          h(level) = h(Li)
 9:       end if
10:    else [there is insufficient space in all existing levels]
11:       create a new level above the top-most level
12:       pack rectangle left justified
13:       h(level) = h(Li); H += h(Li)
14:    end if
15: end while
16: print H and entire packing

Best Fit Level

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: level = 0; h(level + 1) = h(L1); H = h(L1); i = 0
 2: while there is an unpacked rectangle do
 3:    i++; level = 0
 4:    search for lowest level with minimum residual horizontal space
 5:    if such a level exists then
 6:       pack rectangle left justified
 7:    else [such a level does not exist]
 8:       create a new level above the top-most level
 9:       pack rectangle left justified
10:       h(level) = h(Li); H += h(Li)
11:    end if
12: end while
13: print H and entire packing

Bi-Level Next Fit

Хитрая модификация Next Fit Level. Уровни создаются по два, на каждом из которых своя стратегия.
Нижний уровень (или все нечетные): первый пришедший прямоугольник упаковывается по левому краю, остальные — справа налево, пока достаточно места. Затем уровень закрывается и его высота определяется по самому высокому прямоугольнику в нем.
Верхний уровень (или все четные): если на нижнем уровне всего один прямоугольник, уровень упаковывается аналогично нижнему. Если два и больше, то первый прямоугольник упаковывается над более низким из двух прижатых к краям полосы, и также прижимается к краю полосы; все последующие упаковываются справа налево, независимо от того, где был упакован первый — слева или справа.

Звучит путано и не сразу понятно, к чему такие танцы с бубном. Единственное, что очевидно обеспечивает этот алгоритм — это более равномерное распределение прямоугольников по объему полосы, без перекоса к левому краю. Но мы еще вернемся к этой стратегии, когда будем рассматривать алгоритмы компрессии.

Алгоритм BiNFL

Bi-Level Next Fit

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: level = 1; h(level) = 0; H = 0; i = 1
 2: open a new bi-level
 3: call 'pack on lower level'
 4: print H and entire packing
Procedure 'pack on lower level'
 1: the first rectangle packed is left justified
 2: subsequent rectangles that fit are right justified
 3: if there is insufficient space then
 4:    h(level) is given by the height of tallest rectangle packed
 5:    call 'pack on upper level'
 6: end if
Procedure 'pack on the upper level'
 1: if Li+1 is the first rectangle packed then
 2:    left justify on top of Li
 3: else
 4:    if Li+2 is the first rectangle packed then
 5:       pack above min {h(Li); h(Li+1)}
 6:       justify according to min {h(Li); h(Li+1)}
 7:   else
 8:      if Li+j (j > 3) fits on the upper level then
 9:         left justify all other rectangles
10:      else [rectangle does not fit]
11:         H += h(lower) + h(upper); open new bi-level
12:      end if
13:    end if
14: end if

Shelf algorithms

Шельфовые алгоритмы не привязываются к точной высоте прямоугольников и после упаковки первого на уровне (шельфе) остается немного места на случай если следующий будет немного выше. Это «немного» регулируется параметром r ∈ (0;1). Высота шельфа определяется как r^k, где r^k+1 < h(L_i) ≤ r^k для некоторого целого k и высоты первого упаковываемого прямоугольника h(L_i). Аналогично уровневым алгоритмам, применяются стратегии обхода шельфов Next Fit, First Fit и Best Fit. Оставленный на каждом шельфе «резерв» становится выгодным в двух последних случаях (сравните FFL и FFS, BFL и BFS). В примере p=0,7.

Алгоритмы NFS, FFS, BFS

Next Fit Shelf

Input: The dimensions of the rectangles {w(Li); h(Li)}
       the parameter r and the strip width W.
Output: The height H and the entire packing.
 1: shelf = 1; w(shelf) = 0;
    h(shelf) = r^k for some integer k; i = 0; H = h(shelf)
 2: while there is an unpacked rectangle do
 3:    i++; compute k
 4:    if there is sufficient space and r^(k+1) < h(Li) ≤ r^k then
 5:       pack rectangle to the right of the previously packed rectangle
 6:    else [there is insufficient space]
 7:       create a new shelf on top of the previous one
          and pack rectangle Li on the new shelf.
 8:       shelf++; H += r^k
 9:    end if
10: end while
11: print H and entire packing.

First Fit Shelf

Input: The dimensions of the rectangles {w(Li); h(Li)}
       the parameter r and the strip width W.
Output: The height H and the entire packing.
 1: shelf = 1; h(shelf) = r^k for some integer k;
    i = 0; H = h(shelf); shelfnum = 1
 2: while there is an unpacked rectangle do
 3:    i++; compute k
 4:    search for lowest shelf of appropriate height with sufficient space
 5:    if such a shelf exists then
 6:       pack rectangle to the right of the previously packed rectangle
 7:    else [there is insufficient space in all shelves of
             appropriate height or such a shelf does not exist]
 8:       create a new shelf above the top-most shelf
          and pack rectangle Li on the new shelf.
 9:       shelf++; H += r^k; shelfnum++
10:    end if
11: end while
12: print H and entire packing.

Best Fit Shelf

Input: The dimensions of the rectangles {w(Li); h(Li)}
       the parameter r and the strip width W.
Output: The height H and the entire packing.
 1: shelf = 1; h(shelf) = r^k for some integer k;
    i = 0; H = h(shelf); shelfnum = 1
 2: while there is an unpacked rectangle do
 3:    i++; compute k
 4:    search all shelves (starting with the bottom) for one
       with appropriate height and has minimum residual horizontal space.
 5:    if such a shelf exists then
 6:       pack rectangle to the right of the previously packed rectangle
 7:    else [there is insufficient space or
             there is no shelf of appropriate height]
 8:       create a new shelf above the top-most shelf
          and pack the rectangle Li on the new shelf.
 9:       shelf++; H += r^k; shelfnum++
10:    end if
11: end while
12: print H and entire packing.

Harmonic Shelf

Harmonic Shelf пакует на один уровень прямоугольники не только со схожей высотой, но и со схожей шириной. В результате получится больше уровней, но заполнены они будут плотнее. Вводится дополнительный параметр M для расчета допустимой ширины.

Общая ширина полосы, для простоты возьмем ее за единицу, делится на M интервалов I₁..I_M. Автор утверждает, что разумное значение M находится в [3; 12]. Ширина интервалов рассчитывается по формуле:

;     

Для каждого прямоугольника рассчитывается значение p. Параметр k для высоты рассчитывается аналогично шельфовым алгоритмам. Проверяются два условия: есть ли для прямоугольника место на каком-нибудь шельфе высотой r^k и соответствует ли его p уже упакованным там. Если хотя бы одно не выполнено, для него создается свой шельф, с блекджеком и максимально комфортными условиями. В примере p=0,7, M=4.

Алгоритм HS

Harmonic Shelf

Input: The dimensions of the rectangles {w(Li); h(Li)}
       the parameters M, r and the strip width W.
Output: The height H and the entire packing.
 1: shelf = 1; h(shelf) = r^k for some integer k; i = 0
 2: while there is an unpacked rectangle do
 3:    i++; compute k such that r^(k+1) < h(Li) ≤ r^k
 4:    compute the value of p such that 1/(p+1) < w(Li) ≤ 1/p
       where 1 ≤ p < M
 5:    amongst shelves of height r^k find the one
       with packing rectangles whose width fits in the interval Ip
 6:    if there is insufficient space or no rectangle of height r^k then
 7:       a new shelf of appropriate height is created above the top-most shelf
 8:       shelf++
 9:    end if
10:    if rectangle Li is the first on the shelf then
11:       h(shelf) = r^k; H += h(shelf)
12:    end if
13: end while
14: print H and entire packing

Azar_Y

Для деления на уровни вводится некое пороговое значение 0 < Y < 1/2. Ширина прямоугольников масштабируется в соответствии с шириной полосы, которая принимается за единицу. Прямоугольники высотой 2^j-1 < h(L_i) ≤ 2^j и шириной 2^-x-1 < h(L_i) ≤ 2^-x упаковываются на один уровень. То есть уровень характеризуется парой (x, j) для некоторого целого j и натурального x.

Прямоугольники шириной не менее Y нарекаются буферными и пакуются каждый на отдельный уровень. То есть если попался такой прямоугольник, нужно срочно открывать новый уровень, высотой равный ему. Все остальные (не-буферные) пакуются на первый подходящий уровень. Подходящий — в смысле с такой же парой (x, j). Если вдруг места не хватило, не-буферный прямоугольник может стать первым в новом уровне, тогда высота этого уровня будет 2^j.
Какая-то нездоровая иерархия, в общем.
В примере Y=0,4.

Алгоритм Azar

Azar_Y

Input: The dimensions of the rectangles {w(Li); h(Li)}
       the parameter Y and the strip width W.
Output: The height H and the entire packing.
 1: h(level) = 0; w(level) = 0; level = 0
 2: while there is an unpacked rectangle do
 3:    if w(Li) ≥ Y then
 4:       level++; w(level) = w(Li); h(level) = h(Li); H += h(level)
 5:    else [w(Li) < Y ]
 6:       compute x and j such that
          2^(j-1) < h(Li) ≤ 2^j and 2^(-x-1) < w(Li) ≤ 2^(-x)
 7:       search for the lowest (x, j) level
 8:       if no (x, j) level is available or Li is blocked then
 9:          level++; h(level) = 2^j; H += h(level)
10:          w(level) += w(Li)
11:       else [(x, j) level is available and not blocked]
12:          w(level) += w(Li)
13:       end if
14:    end if
15: end while
16: print H and entire packing

Compression algorithms

Компрессионные алгоритмы основаны на BiNFL и по сути представляют собой патчи к методу упаковки верхнего уровня.
Общее отличие — верхний уровень всегда упаковывается слева направо.
Compression Part Fit: Для каждого прямоугольника, упакованного на верхний уровень, проверяется, есть ли под ним место на нижнем уровне. Если можно сдвинуть его на нижний уровень так, что часть его останется на верхнем, он сдвигается (отсюда Part Fit — он частично может быть «вжат» в предыдущий уровень). Таким образом можно снизить общую высоту второго уровня. Больше на упаковку он никак кардинально не влияет. На первом рисунке видно прямоугольник, висящий между уровней — он и был сдвинут.
Compression Full Fit: Для каждого прямоугольника, упакованного на верхний уровень, проверяется, может ли он полностью сместиться вниз на предыдущий уровень. Собственно, если может, то и смещается. Это дает нам стратегическое преимущество: освободившееся таким образом место на уровне может быть использовано для следующего прямоугольника. К сожалению, второй рисунок не содержит такую ситуацию, но зато на нем можно увидеть двоих провалившихся.
Compression Combo: Да-да, это комбинация двух предыдущих и, соответственно, комбинация их плюсов. Третий рисунок иллюстрирует.

Алгоритмы CPF, CFF, CC

Compression

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: i = 0; H = 0
 2: open new bi-level
 3: packing on lower level is similar to BiNFL; H += h(lowerlevel)
 4: if there is insufficient space to pack a rectangle on the lower level then
 5:    call 'pack on the upper level'
 6: end if
 7: print H and entire packing
Procedure 'pack on the upper level'
 1: while there is an unpacked rectangle do
 2:    if i ≥ 3 and Li is the first rectangle packed then
 3:       justify according to the shorter
          of the left-most and right-most rectangles
 4:       slide rectangle downwards if there is sufficient space
          and go to 12
 5:    else
 6:       if i ≥ 3 and Li is the second rectangle packed then
 7:          right justify and go to 12
 8:       else [rectangle does not fit]
 9:          H += h(upperlevel); open new bi-level
10:       end if
11:    end if
12: end while

Compression Part Fit

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: i = 0; H = 0
 2: open a new bi-level
 3: packing on lower level is similar to BiNFL; H += h(lowerlevel)
 4: if there is insufficient space to pack a rectangle on the lower level then
 5:    call 'pack on the upper level'
 6: end if
 7: print H and entire packing
Procedure 'pack on the upper level'
 1: while there is an unpacked rectangle do
 2:    if h(Li) > VerticalSpace and w(Li) ≤ HorizontalSpace then
 3:       shift rectangle Li downwards; go to 11
 4:    else
 5:       if h(Li) ≤ VerticalSpace and W - w(level) ≥ w(Li) then
 6:          left justify; go to 11
 7:       else [rectangle does not fit]
 8:          H += h(upperlevel); open a new bi-level
 9:       end if
10:    end if
11: end while

Compression Full Fit

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: i = 0; H = 0
 2: open a new bi-level
 3: packing on lower level is similar to BiNFL; H += h(lowerlevel)
 4: if there is insufficient space to pack a rectangle on the lower level then
 5:    call 'pack on the upper level'
 6: end if
 7: print H and entire packing
Procedure 'pack on the upper level'
 1: while there is an unpacked rectangle do
 2:    if h(Li) ≤ VerticalSpace and w(Li) ≤ HorizontalSpace then
 3:       slide rectangle Li downwards; go to 11
 4:    else
 5:       if h(Li) ≤ VerticalSpace and W - w(level) ≥ w(Li) then
 6:          left justify; go to 11
 7:       else [rectangle does not fit]
 8:          H += h(upperlevel); open new bi-level
 9:       end if
10:    end if
11: end while

Compression Combo

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: i = 0; H = 0
 2: open a new bi-level
 3: packing on lower level is similar to BiNFL; H += h(lowerlevel)
 4: if there is insufficient space to pack a rectangle on the lower level then
 5:    call 'pack on the upper level'
 6: end if
 7: print H and entire packing
Procedure 'pack on the upper level'
 1: while there is an unpacked rectangle do
 2:    if w(Li) ≤ HorizontalSpace then
 3:       slide rectangle Li downwards; go to 11
 4:    else
 5:       if w(Li) > HorizontalSpace and W - w(level) ≥ w(Li) then
 6:          left justify, go to 11
 7:       else [rectangle does not fit]
 8:          H += h(upperlevel); open new bi-level
 9:       end if
10:    end if
11: end while

Online fit

Более трудоемкий метод, чем предыдущие, но и более производительный. Основан на алгоритме Burke для оффлайн-варианта задачи. Некоторые аспекты я, пожалуй, нарисую.



В процессе упаковки могут образовываться пустые области (Empty Areas), которые алгоритм будет пытаться заполнить в первую очередь. Как они могут образоваться, видно на фото слева. Заметим, что для этого нужно хранить некое представление заполненности полосы.
После заполнения из пустой области может получиться две (а может и не получиться, you know).

Также одним шагом упаковки могут быть созданы сразу несколько областей — пространство под прямоугольником анализируется по вертикали и делится по количеству «ступенек». На среднем фото еще раз показано разбиение пустой области на две после упаковки туда прямоугольника (кстати, мне кажется, в этом месте оптимальнее было бы разбить ее по горизонтали).
В общем, чем дальше в лес, тем больше пустот. На каждом шаге пристально рассматриваются стремительно мельчающие пустоты. Здесь мне видится еще одна оптимизация: можно ввести меру целесообразной площади и отбрасывать неугодные.

Если ни одна пустая область не подходит, упаковка продолжается методом Burke. Я напомню. Строится карта высот для полосы, и прямоугольник примеривается в самую низкую на данный момент область. Если он туда не входит, низкое место «заполняется» до уровня ближайшей ступеньки, и поиск повторяется. Так потенциальное место может быть вытолкнуто на самый верх, и тогда возникает еще один вариант образования пустого пространства (см. справа).
Та же карта высот используется на каждом шаге для выявления пустых областей.

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

Алгоритм OF

Online Fit

Input: The dimensions of the rectangles {w(Li); h(Li)} and the strip width W.
Output: The height H and the entire packing.
 1: i = 0; H = 0
 2: Create a linear array whose number of elements are equal to W
 3: while there is an unpacked rectangle do
 4:    i++
 5:    Search the list of empty areas for sufficient space to pack Li
 6:    if w(EmptyArea) ≥ w(Li) and h(EmptyArea) ≥ h(Li) then
 7:       pack rectangle in empty area
 8:    else
 9:       if rectangle does not fit in any of the empty areas then
10:          search the linear array for available packing width
11:       else [there is insufficient space in linear array]
12:          pack rectangle on top left justified
             from the index leading to smaller space
13:       end if
14:    end if
15: end while
16: H = highest entry in the linear array
17: print H and entire packing

Послесловие

Чтобы развеять ощущение бесцельности происходящего, приведу один из классических, но вдохновляющих примеров применения алгоритмов двумерной упаковки в полуограниченную полосу. Это планировщик задач для многопроцессорной системы. В современном софте для кластеров используются более «взрослые» алгоритмы, но сама задача планирования сводится к 2DSP. В условиях работы кластеров поток поступающих задач представляет собой не что иное, как online данные для упаковки: размерность по горизонтали — требуемое количество ядер, по вертикали — время работы задачи. (Все как на заре технологий: встаешь в очередь к компьютеру и заранее предупреждаешь, сколько тебе нужно ресурсов и как долго будет крутиться твоя перфокарта). Планировщик должен выделить для задачи конкретные процессоры и определить момент запуска. В чистом виде, кстати, ни один алгоритм использовать нельзя, так как время капает, пока планировщик ждет задачу или думает над ее размещением. Дополнительно программисту могут связывать руки разные специфические условия: приоритет задач; возможность масштабирования задачи во время выполнения; хардварные задержки и самообслуживание системы, в том числе перераспределение с учетом отказавших ресурсов; сопоставление характера коммуникаций внутри задачи с архитектурой кластера, etc.
Любой алгоритм прекрасен в своей математической строгости, пока не начнешь прикладывать его к реальной жизни.

И напоследок — сравнительная характеристика алгоритмов в приятном обезличенном виде. Здесь приведено отношение оптимальной высоты упаковки (сумма площадей прямоугольников, деленная на ширину полосы) к полученной.

NFL	FFL	BFL	BiNFL	NFS	FFS	BFS	HS	AzarY	CPF	CFF	CC	OF
0,56	0,63	0,75	0,56	0,45	0,57	0,57	0,37	0,44	0,60	0,59	0,63	0,72

---

Код (Qt):
Алгоритмы packager.h packager.cpp
Гуй window.h window.cpp renderarea.h renderarea.cpp main.cpp

• 2DSP
• , bin packing
• , двумерная упаковка
• , задача о рюкзаке

Wildy