Задача об упаковке

Задача упаковки в контейнеры

Дано: множество предметов L = {1, … , n} и их веса wi((0,1), i(L.

Найти: разбиение множества L на минимальное число m подмножеств

B1, B2, … , Bm такое, что

[pic], для всех 1 ( j ( m.

Множества Bj называют контейнерами.

Требуется упаковать предметы в минимальное число контейнеров.

Задача NP-трудна и часто возникает в приложениях.

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

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

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

Если предмет входит, то помещаем его и переходим к следующему шагу,

иначе помещаем предмет в новый контейнер.

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

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

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

Пример

[pic]. Всего 4N предметов.

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

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

[pic].

Для задачи на минимум гарантированная относительнаяточность RA для алгоритма A определяется как

RA ( inf {r ( 1 | RA (L) ( r для всех L}.

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

[pic] ( inf {r ( 1 | ( N > 0 такое, что RA (L) ( r для всех L с OPT(L) ( N}.

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

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

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

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

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

|Пример |[pic] |
|L = {1,…, 18 m} | |

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

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

Т = О(n2), П = О(n).Теорема. RBF = RFF, [pic] и существуют примеры со сколь угодно большими значениями OPT(L), для которых BF(L) = 4/3 FF(L)

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

(Без доказательства)

Алгоритмы типа On-line

Предметы поступают в непредсказуемом порядке. Требуется упаковать их в минимальное число контейнеров. Упакованный предмет нельзя перемещать в другой контейнер. Место для предварительногохранения предметов отсутствует.

Алгоритмы NF, FF, BF являются On-line алгоритмами.

Теорема. Для любого On-line алгоритма A справедливо неравенство [pic]

(Без доказательства)

Алгоритмы с ограниченным доступом к контейнерам

On-line алгоритм называют алгоритмом с ограниченным доступом к контейнерам, если на каждом шаге алгоритм имеет возможность помещать предметы только в один из K контейнеров(K — const). Эти контейнеры называются открытыми. Если контейнер закрыли, то он уже не открывается (например, отправляется потребителю). Прежде чем добавить пустой открытый контейнер, нужно закрыть один из K открытых контейнеров.

Алгоритм NF — пример для K = 1.

Правила для выбора контейнера

1. Закрыть контейнер с наименьшим номером

2. Закрыть...