Приближенные схемы Задачи упаковки. Задача oб упаковке Дано: n предметов и их размеры a 1,…,a n (0,1]. Найти упаковку всех предметов в единичные ящики, - презентация

1 Приближенные схемы Задачи упаковки

2 Задача oб упаковке Дано: n предметов и их размеры a 1,…,a n (0,1]. Найти упаковку всех предметов в единичные ящики, так чтобы минимизировать число использованных ящиков.

3 Правило «Первый подходящий» Рассмотрим предметы в произвольном порядке. Пусть мы получили лист частично заполненных ящиков, скажем B 1,…, B k. Положим очередной предмет в первый ящик, в который он войдет. Если такого нет, то откроем новый ящик B k+1 и положим предмет в него.

4 Алгоритм «Первый подходящий» Input (a 1,…,a n ) 1) i 1, k 1, bin(1) 1, bin(2) 1. 2) While i n do: r min{j k+1| a i bin(j)} if (r k ) then bin(r) bin(r) – a i otherwise k k + 1 bin(k) 1 – a i bin(k+1) 1 Output (k)

5 Оценка качества алгоритма «Первый подходящий» Теорема 6.1 Алгоритм «Первый подходящий» 2-приближенным алгоритмом для задачи об упаковке. Доказательство: Пусть использовано k ящиков.

6 Неаппроксимируемость Теорема 6.2 Для любого ε >0, не существует ρ-приближенного алгоритма для задачи об упаковке с ρ=3/2 – ε, если P NP. Идея доказательства. Сведем NP-трудную задачу «Разбиение» к проверке можно ли разместить все предметы в два ящика.

7 Асимптотическая приближенная схема Теорема 6.3 Для любого ε, 0 < ε 0.5, существует полиномиальный от n алгоритм A ε, который находит упаковку, использующую не более (1+2ε)OPT + 1 ящик.

8 Упаковка ограниченного числа больших предметов Лемма 6.4 Пусть ε > 0 фиксированная константа и K > 0 фиксированное целое. Рассмотрим примеры задачи об упаковке, в которых размеры предметов не меньше ε, и число различных размеров равно K. Тогда существует полиномиальный алгоритм, который точно решает такие примеры.

9 Доказательство Число предметов в одном ящике 1/ε := M. Пусть x i – число предметов i-го размера в ящике. Вектор (x 1,…, x K ) определяет тип ящика. Число различных типов ящиков. Общее число ящиков n. Число возможных допустимых упаковок и ограничено полиномом от n.

10 Упаковка больших предметов Лемма 6.5 Пусть ε > 0 фиксированная константа. Рассмотрим примеры задачи об упаковке, в которых размеры предметов не меньше ε. Тогда существует полиномиальный алгоритм, который находит упаковку в не более чем (1+ε)OPT ящиков, где OPT – число ящиков в оптимальной упаковке.

11 Доказательство (преобразование примера I) Упорядочим все предметы по не убыванию размеров. I Разобьем их в K= 1/ε 2 групп по не более чем Q= nε 2 предметов. Округлим размер каждого предмета к размеру наибольшего в группе.

12 Доказательство (преобразование примера I) Упорядочим все предметы по не убыванию размеров. J Разобьем их в K= 1/ε 2 групп по не более чем Q= nε 2 предметов. Округлим размер каждого предмета к размеру наибольшего в группе. В J не более K различных размеров предметов. По лемме 6.5 можно найти оптимальную упаковку для примера J.

13 Доказательство OPT(J) (1+ε) OPT(I) J I J

14 Алгоритм Фернандес де ла Вега- Луекера Input (a 1,…,a n ) 1) Определим Big = { j | a j ε} и Small = { j | a j < ε} 2) Разбить большие предметы в K= 1/ε 2 групп по не более чем Q= nε 2 предметов. 3) Округлить размер каждого большого предмета к размеру наибольшего в группе. 4) Упаковать большие предметы оптимальным образом относительно новых размеров. 5)Упаковать маленькие предметы используя правило «Первый подходящий». Пусть k – число использованных ящиков в полученной упаковке. Output (k)

15 Асимптотическая приближенная схема Теорема 6.3 Для любого фиксированного ε, 0 < ε 0.5, алгоритм Фернандес де ла Вега-Луекера находит упаковку, использующую не более (1+2ε)OPT + 1 ящик и время его работы ограничено полиномом от n.

16 Доказательство Теоремы 6.3 k – число использованных ящиков в полученной упаковке. Пусть I пример, полученный из исходного примера I, удалением множества Small. На шаге 4 алгоритм получит упаковку больших предметов в не более чем (1+ε)OPT(I) ящиков. Если на шаге 5 вставляя маленькие работы не потребуется ни одного нового ящика, то k = (1+ε)OPT(I) (1+ε)OPT(I). В противном случае, по крайней мере k–1 ящик должен быть заполнен не меньше чем на 1–ε. Следовательно, сумма размеров предметов в I, по крайней мере (k–1)(1–ε) OPT(I). k OPT(I)/(1–ε) + 1 (1+2ε)OPT(I)+1, (0 < ε < 1/2).

17 Задача P||C max Дано: m машин, n работ и их длительности p 1,…,p n. Найти назначение всех работ на m машин, так чтобы минимизировать длину расписания (время завершения всех работ, максимальную загрузку машины).

18 Жадный алгоритм с произвольным списком (GL) Задан список работ в произвольном порядке. Когда какая-нибудь машина освобождается, первая работа из списка назначается на эту машину и удаляется из списка.

19 Первый приближенный алгоритм Теорема 6.6 (Грэхэм [1966]) Алгоритм GL является (2 – 1/m)-приближенным алгоритмом для P||C max.

20 Доказательство JkJk M1M1 M2M2 M3M3 M4M4 sksk CkCk t = 0

21 P||C max и задача oб упаковке M1M1 M2M2 M3M3 M4M4 0t 0 t 4 ящика bins(i,t) – минимальное число ящиков размера t, требуемое упаковать данные n предметов.

22 Бинарный поиск Чтобы осуществить сведение нам нужно знать или угадать значение С max в оптимальном решении. – нижняя оценка. Можно угадать значение оптимального решения устроив бинарный поиск и используя в качества проверки решение задачи об упаковке.

23 Упаковка ограниченного числа предметов Пусть k – фиксированное число размеров предметов. Зафиксируем порядок размеров. Для каждого примера вход может быть представлен как вектор из k компонент, (i 1, i 2,…, i k ) указывающий число предметов каждого размера. BINS(i 1, i 2,…, i k ) – минимальное число ящиков требуемое упаковать это множество предметов. (4,1,2,5)

24 Один ящик Для данного примера (n 1, n 2,…, n k ), Σn i = n, вычислим множество Q всех векторов (q 1, q 2,…, q k ), таких что BINS(q 1, q 2,…, q k ) = 1 и 0 q i n i, 1 i k. (4,1,2,5) (0,0,0,1)(0,0,0,1) (0,0,0,2)(0,0,0,2) (1,0,1,0)(1,0,1,0) (0,1,0,0)(0,1,0,0)

25 Динамическое программирование Вычислим все значения k-размерной таблицы BINS(i 1, i 2,…, i k ) для каждого (i 1, i 2,…, i k ) {0,…,n 1 }×{0,…,n 2 }×…× {0,…,n k }. Сначала заполним таблицу для элементов из Q. Вычислим остальные значения по формуле Все значения в таблице могут быть выполнены за O(n 2k ).

26 Идея схемы Поскольку в PTAS мы можем позволить некоторую неточность в вычислении длины расписания, то мы можем свести задачу P||C max к задача oб упаковке ограниченного числа предметов. При сведении появятся два источника ошибок. –при округлении длительностей работ, для того чтобы ограничить число различных размеров предметов. –при остановке бинарного поиска. Покажем, что можно получить относительную погрешность сколь угодно близкой к 1. При этом трудоемкость алгоритма экспонециально зависит от ε, и полиномиально от n.

27 Основная процедура для фиксированного t (LB t 2LB) Input (p 1,…,p n,ε,t) 1)Определим Big = { j | p j tε} и Small = { j | p j < tε}. 2)Округлим каждый большой предмет: if p j [tε(1+ε) i, tε(1+ε) i+1 ) then p j tε(1+ε) i. 3)Используя динамическое программирование найдем оптимальную упаковку U больших предметов (p j) в ящики размера t. 4)Рассмотрим U, как упаковку предметов с исходными предметами. Тогда U допустимая упаковка в ящики размера t(1+ε). 5)Упаковать маленькие предметы, используя правило «Первый подходящий». Пусть α(I,ε,t) – число использованных ящиков в полученной упаковке. Output (α(I,ε,t) )

28 Трудоемкость основной процедуры Число различных значений p j -х k= log 1+ε 1/ε. Трудоемкость основной процедуры определяется трудоемкостью динамического программирования и равна O(n 2k ). При фиксированном ε трудоемкость процедуры полиномиально зависит от n.

29 Нижняя оценка на число ящиков Лемма 6.7 α(I,ε,t) bins(I,t).

30 Доказательство Пусть на шаге 5 процедуры (до упаковки маленьких предметов) не был открыт ни один новый ящик. Утверждение леммы верно, так как даже для округленного примера в найденном основной процедурой оптимальном решении требуется α(I,ε,t) ящиков. В противном случае, все ящики кроме одного должны быть заполнены не меньше чем на t. Следовательно сумма размеров предметов > t (α(I,ε,t) –1) и нужно как минимум α(I,ε,t) ящиков, чтобы упаковать все предметы.

31 Нижняя оценка на длину расписания Следствие 6.8 min{t: α(I,ε,t) m } OPT. Доказательство. OPT = min{t: bins(I,t) m}. По лемме 6.7 для любого t: α(I,ε,t) bins(I,t). Отсюда, min{t: α(I,ε,t) m } OPT.

32 Как найти t ? Бинарный поиск в интервале [LB, 2LB]. На каждой итерации длина интервала уменьшается вдвое. Остановим процедуру бинарного поиска, когда длина интервала станет εLB и обозначим его [T – ε LB, T]. Это потребует log 2 1/ε итераций.

33 Нижняя оценка Лемма 6.9 T (1+ε)OPT. Доказательство. min{t: α(I,ε,t) m } [T – εLB, T] T min{t: α(I,ε,t) m }+ εLB (1+ ε)OPT.

34 Приближенная схема Теорема 6.10 Для любого ε > 0, существует алгоритм A ε, который находит расписание длины не больше (1+ε) 2 OPT (1+3ε)OPT за O(n 2k log 2 1/ε ) операций, где k = log 1+ε 1/ε.