23. Алгоритмы с гарантированной оценкой точности. Задача упаковки

Эвристические алгоритмы(полиномиальный алгоритм, находящий приближенное решение)

Пусть А – алгоритм решения задачи, заключающийся в нахождении X_opt такого, что f(X_opt) минимально.

Алгоритм А имеет гарантированную оценку точности k, если для любого найденного алгоритмом решения Х f(X) <= kf(X_opt).

Задача упаковки.

Вход: мн-во из n предметов с весами w₁,…, w_n, где w_i  (0, 1].

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

Теорема. Задача упаковки является NP-трудной.

Док-во. Докажем, что «разбиение» ( полиномиально сводится к ) «упаковке». Пусть U=(w₁,…, w_n) – вход задачи «разбиение». Можно без ограничений общности считать, что w _i  (0, 1] (в противном случае разделим все w_i на w = max{w_j}).

Положим c = |1/2 * ∑w_i|, i=1,…, n и преобразуем U во вход V=(w₁/c,…, w_n/c) задачи «упаковка».

Легко видеть, что U можно разбить на 2 подмассива с одинаковыми суммами элементов iff когда предметы из V можно упаковать в 2 контейнера.

Пусть предметы можно упаковать в два контейнера.

Пусть I и J – мн-ва индексов предметов упакованных в 1 и 2 контейнерах.

Имеем:

∑(w_i/c)(iI) ≤ 1, ∑(w_j/c)(jJ) ≤ 1,

∑w_i (iI) ≤ c, ∑w_j(jJ) ≤ c

∑w_i (iI) ≤ 1/2*∑w_i (i=1,…, n), ∑w_j (jJ) ≤ 1/2*∑w_i (i=1,…, n)

Пусть теперь массив U можно разбить на 2 подмассива с одинак. суммами эл-ов. Пусть I и J – мн-ва индексов эл-ов из первого и второго подмассивов.

∑w_i (iI) = 1/2*∑w_i (i=1,…, n), ∑w_j (jJ) = 1/2*∑w_i (i=1,…, n),

∑(w_i/c)(iI) = 1, ∑(w_j/c)(jJ) = 1

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

В произвольном порядке упаковываем по следующему правилу : первый предмет помещаем в первый контейнер. На k – шаге пытаемся поместить k-ый предмет в текущий контейнер ,если предмет входит ,то помещаем его , если нет пытаемся в другой контейнер Трудоемкость : О(n)

Т-ма NF имеет гарантированную оценку точности 2

Док-во пусть w = w₁+…+ w_n и Т₁,…….,Т_n – контейнеры, найденные алгоритмом, opt- оптимальное число контейнеров

opt w .Пусть w(T_i) – общий вес предметов , упакованных в i – ый контейнер w = (w(T₁) + w(T₂))+ (w(T₃) + w(T₄))+ … сумма весов предметов , упакованных в 2 подряд идущих контейнера >1

W > k/2, opt W > k/2

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

В произвольном порядке упаковываем предметы по следующему правилу: первый предмет помещаем в первый контейнер. На k–шаге находим контейнер с наименьшим номером, куда помещаем k-ый предмет. Если такого контейнера нет , то берем новый контейнер и помещаем предмет в него. Трудоемкость : О(n²)

Т-ма FF находит упаковку в не более чем 17/10 Opt + 1 контейнер

Алгоритм Первый подходящий с упорядочиванием (FFD)

Сортируем алгоритм по не возрастанию весов и применяем алгоритм FF(NF)

Т-ма FFD находит упаковку в не более чем 11/9 Opt + 4 контейнера

Утв Если для какого-то 0 для задачи упаковкиприближенный полиномиальный алгоритм с гарантированной оценкой точности 3/2 –, тоP = NP

Док-во пусть алгоритм А для задачи упаковки с гарантированной точностью 3/2 – Мы покажем , что задача Разбиение сводится к задаче упаковки в 2 контейнера. Рассмотрим задачу упаковки в 2 контейнера. Пусть алгоритм А получает на входе задачу упаковки ,правильный ответ котором - 2. Какой ответ на этом входе даст алгоритм А? Если А даст ответ 3, то этот ответ в 3/2 раза хуже оптимального!