Глава 1. Постановка задачи. Обзор задач упаковки в контейнеры

1. Формулировка задачи упаковки в контейнеры

Задача упаковки в контейнеры [1] формулируется следующим образом. Задан список предметов и вместимость контейнера . Требуется предметы из списка разместить в минимальное число контейнеров таким образом, чтобы сумма весов предметов в каждом контейнере не превосходила .

Задача упаковки в контейнеры является NP-полной [2].

1.2 Постановка задачи

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

1. типов 3-х мерных параллелепипедов, каждый из которых задан линейными размерами ;

2. 3-х мерный объем для укладки груза, заданный линейными размерами .

Требуется рассчитать точное расположение параллелепипедов в заданном объеме таким образом, чтобы его заполнение было наиболее эффективным по объему, т.е. суммарный объем поместившихся параллелепипедов должен быть максимальным из всех возможных. Допустимым положением груза считается такое, когда все упакованные параллелепипеды находятся внутри заданного объема, не пересекаются и полностью опираются на дно объема или на другие параллелепипеды.

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

• количество задействованных контейнеров для упаковки;

• плотность упаковки объектов в контейнерах.

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

1.3 Обзор алгоритмов упаковки в контейнеры

Алгоритм «Следующий подходящий» (NF)

В произвольном порядке упаковываем предметы по следующему правилу:

• первый предмет помещаем в первый контейнер;

• на k-м шаге пытаемся поместить k-й предмет в текущий контейнер;

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

Т = О(n), П = О(1), если не считать место для исходных данных.

Теорема. NF(L) ≤2OPT(L).

Доказательство. Пусть W .

Так как любые два последовательных контейнера содержат предметы суммарным весом не меньше единицы, тоNF(L) < 2⎡W⎤. Кроме того,

OPT(L) ≥⎡W⎤, откуда и следует требуемое.

Замечание.NF(L) ≤2OPT(L) – 1 для всех L.

Пусть алгоритм A для множества L порождает A(L) контейнеров и

.

Для задачи на минимум гарантированная относительная точность ля алгоритма A определяется как ≡inf {r ≥1 | (L) ≤r для всех L}.

Определение. Асимптотическая гарантированная относительная точность для алгоритма A определяется как

≡inf {r ≥1 | ∃N > 0 такое, что (L) ≤r для всех L с OPT(L) ≥N}.

Алгоритм «Первый подходящий» (FF)

В произвольном порядке упаковываем предметы по следующему правилу:

• первый предмет помещаем в первый контейнер;

• на k-м шаге находим контейнер с наименьшим номером, куда помещается k-й предмет, и помещаем его туда. Если такого контейнера нет, то берем новый пустой контейнер и помещаем предмет в него.

Т = О(n2), П = О(n).

Теорема.FF(L) ≤⎡ OPT(L) +1⎤для всех L и существуют примеры со сколь угодно большими значениями OPT, для которых

FF(L) ≥⎡ OPT(L) – 1⎤.

Алгоритм «Наилучший подходящий» (BF)

В произвольном порядке упаковываем предметы по следующему правилу:

• первый предмет помещаем в первый контейнер;

• на k-м шаге размещаем k-й предмет. Находим частично заполненные контейнеры, где достаточно для него свободного места и выбираем среди них наиболее заполненный. Если таких нет, то берем новый пустой контейнер и помещаем k-й предмет в него.

Т = О(n2), П = О(n).

Теорема. = , = и существуют примеры со сколь угодно

большими значениями OPT(L), для которых BF(L) = 4/3 FF(L)

и FF(L) = 3/2 BF(L).

Сравнительные характеристики алгоритмов упаковки

«Первый подходящий» — это быстрый алгоритм, поскольку поиск ведется с наименьшими затратами времени.  Незначительной вариацией алгоритма «первый подходящий» является алгоритм «следующий подходящий». Он работает так же, как и «первый подходящий», за исключением того, что отслеживает свое местоположение, как только находит подходящее пустое пространство. При следующем вызове для поиска пустого пространства он начинает поиск в списке с того места, на котором остановился в прошлый раз, а не приступает к поиску с самого начала, как при работе алгоритма «первый подходящий». Моделирование работы алгоритма «следующий подходящий», проведенное Бэйсом (Bays, 1977), показало, что его производительность несколько хуже, чем у алгоритма «первый подходящий». 

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

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