110 |
Глава 2. АППРОКСИМАЦИЯ С ГАРАНТИРОВАННОЙ ТОЧНОСТЬЮ |
Очевидно, что существует тривиальное допустимое решение — округлить цены всех товаров, но требуется найти именно решение с минимальными потерями.
Алгоритм должен работать быстро, за линейное от количества товаров время — это должен быть мгновенный расчет на кассе.
Упражнение 2.2.7. DVS технология позволяет снижать напряжение на процессоре, и добиваться экономии электроэнергии за счет увеличения времени выполнения задачи.
Пусть процессор поддерживает два уровня напряжения — UL < UH . Есть набор из n задач, каждая из которых имеет энергоемкость и время выполнения для обоих режимов — т. е. 8i, энергоемкости cHi и cLi
и длительности tHi и tLi .
Нужно выполнить все задачи на одном процессоре за время не более T , при этом добиться минимального энергопотребления.
2.2.2Полностью полиномиальная приближенная схема для «Рюкзака»
"-оптимальные алгоритмы для задачи о рюкзаке с выбираемой точностью и временем выполнения, полино-
миальным по n и 1" (FPT AS — Fully Polynomial Time Approxima on Scheme).
Одним из общих подходов к решению переборных задач является разработка приближенных алгоритмов с гарантированными оценками качества получаемого решения (см. определение 2.1.1 «C-приб- лиженный алгоритм»).
Dynamic Voltage Scaling
Напомним, что алгоритм, не гарантирующий точность решения, однако применяемый на практике из-за хороших практических результатов, принято называть эвристикой (см. определение 1.1.1).
2.2. АППРОКСИМАЦИЯ С ЗАДАННОЙ ТОЧНОСТЬЮ |
111 |
Особую роль среди приближенных алгоритмов играют те, которые способны находить решения с любой, заданной как параметр, точностью.
Определение 2.2.2. Алгоритм с мультипликативной ошибкой не более (1 + "), где " > 0, называется
"-оптимальным.
Тот же термин "-оптимальное используется для обозначения допустимого решения со значением целевой функции, отличающимся от оптимума не более чем в (1+") раз (таким образом, задача, стоящая перед "-оптимальным алгоритмом, состоит в отыскании какого-либо "-оптимального решения).
Определение 2.2.3. Полностью полиномиальной аппроксимационной схемой (FPTAS) называется при-
ближенный алгоритм, в котором уровень точности " выступает в качестве нового параметра, и алгоритм находит "-оптимальное решение за время, ограниченное полиномом от длины входа и величины " 1.
Только одно обстоятельство является препятствием для построения полностью полиномиальной аппроксимационной схемы для задачи 13 «Knapsack» методом динамического программирования (см. раздел 2.2.1). Это наличие «больших» коэффициентов в целевой функции. Действительно, как мы видели в разделе 2.2.1, динамическое программирование дает точный псевдополиномиальный алгоритм для задачи о рюкзаке со сложностью O(nB) или O(nf ). Если f не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты стоимостей), то этот псевдополиномиальный алгоритм 26 не является полиномиальным.
Но к счастью, существует общий метод (который условно можно назвать масштабированием), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно отличается от оптимума исходной задачи. Зададимся вопросом: что произойдет, если мы округлим стоимости c1; : : : ; cn, взяв целые части от деления их на некоторый параметр scale 2 Q и затем домножив снова на scale (c~i = ci/scale scale)?
112 |
Глава 2. АППРОКСИМАЦИЯ С ГАРАНТИРОВАННОЙ ТОЧНОСТЬЮ |
Алгоритм 26 «Рюкзак» с отбором «легких» решений
def knapsack_dynprog_lightest(items, B): |
|
T = {0: ItemSet()} # Цена → самый легкий набор |
|
for item in items: # По всем предметам |
|
newT = [] |
|
for sol in T.values(): # по всем частичным |
|
test = sol + item |
# тестовый набор |
if test.weight <= B and ( |
|
test.cost not in T |
|
or test.weight < T[test.cost].weight): |
|
newT.append(test) # подходит! |
|
for sol in newT: |
# регистрируем |
T[sol.cost] = sol |
# новые решения |
return T[max(T.keys())] |
# самое дорогое |
|
|
|
|
Предметы ( |
стоимость |
|
6 |
, |
3 |
2 |
5 |
, |
5 |
, |
1 |
], B = 9 |
|
|
|
|
|
|||||||||
|
|
|
вес |
|
): [ 3 |
4 , |
5 , |
6 |
7 |
8 |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
T |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
item |
newT |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0: |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
[ 6 |
] |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
3 |
|
|
|
|
|
0: |
0 |
, 6: |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
[ 3 |
, |
9 |
] |
|
|
|
0 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
4 |
|
7 |
|
|
|
0: |
0 |
, 9: |
9 |
, 3: |
3 |
, 6: |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
[ 2 |
, |
5 |
, |
8 |
] |
|
0 |
|
7 |
|
4 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
5 |
|
9 |
|
8 |
|
0: |
0 |
, 2: |
2 |
, 3: |
3 |
, 5: |
5 |
, 6: |
6 |
, 8: |
8 |
, 9: |
9 |
|
|
|
|
|
|
|
5 |
[ 5 |
, |
11 |
] |
|
||
|
0 |
|
5 |
|
4 |
|
9 |
|
3 |
|
8 |
|
7 |
|
|
|
|
|
|
|
6 |
6 |
|
9 |
|
|
||
0: |
0 |
, 2: |
2 |
, 3: |
3 |
, 5: |
5 |
, 6: |
6 |
, 8: |
8 |
, 9: |
9 |
, 11: |
11 |
|
|
|
5 |
[] |
|
|
|
|
|
|||
|
0 |
|
5 |
|
4 |
|
6 |
|
3 |
|
8 |
|
7 |
|
|
9 |
|
|
|
|
7 |
|
|
|
|
|
|
|
0: |
0 |
, 2: |
2 |
, 3: |
3 |
, 5: |
5 |
, 6: |
6 |
, 8: |
8 |
, 9: |
9 |
, 11: |
11 |
|
|
|
1 |
[ 1 |
] |
|
|
|
|
|||
|
0 |
|
5 |
|
4 |
|
6 |
|
3 |
|
8 |
|
7 |
|
|
9 |
|
|
|
|
8 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
Оптимальное решение: |
|
11 |
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
•Задачу можно решать, «отмасштабировав» все стоимости c~i на величину scale (т. е. поделив, причем без потерь, т.к. все c~i делятся на scale нацело), и это не изменит оптимального набора.
•Время работы алгоритма динамического программирования с отбором наиболее «легких» подмножеств (алгоритм 26) будет ограничено O(scalenf ).
•Веса ai мы не меняли, значит, любое допустимое решение «округленной» задачи является также допустимым решением исходной задачи.
2.2. АППРОКСИМАЦИЯ С ЗАДАННОЙ ТОЧНОСТЬЮ |
113 |
•Из-за потерь «округления» оптимум получившейся задачи может стать меньше исходной, т.к. предметы стали стоить несколько «дешевле».
Осталось понять, как связан выигрыш во времени работы алгоритма с потерей точности решения, «стоит ли игра свеч».
Итак, формально, пусть для «округленной» задачи:
c~i
x~i
xi
f~
—стоимости, c~i = ci/scale scale;
—показывает включение предмета в оптимальный набор «округленной» задачи, x~i 2 f0; 1g;
—показывает включение предмета в оптимальный набор исходной задачи, xi 2 f0; 1g;
∑
— оптимум «округленной» задачи, f~ = ni=1 c~ix~i.
Посмотрим, насколько может быть хуже «оптимум» округленной задачи f~по сравнению с оптимумом исходной задачи f .
Максимальная абсолютная погрешность из-за «округления» только одного j-го предмета, входящего в оптимальный набор для исходной задачи, строго меньше scale.
Имеем
∑ |
∑i |
∑ |
n |
n |
n |
f~ = c~ix~i |
c~ixi |
(ci scale)xi f n scale: |
i=1 |
=1 |
i=1 |
∑ Заметим, для стоимости «рюкзака» при подстановке x~i в исходную задачу выполняется:
ni=1 c~ix~i = f~, поэтому дальше в этом разделе мы будем использовать f~ как нижнюю оценку аппроксимации исходной задачи.
114 |
Глава 2. АППРОКСИМАЦИЯ С ГАРАНТИРОВАННОЙ ТОЧНОСТЬЮ |
|||||||
т. е. получаем неравенство для абсолютной погрешности: |
|
|
||||||
|
f |
f~ n scale: |
|
|
||||
Если потребовать, чтобы абсолютная погрешность не превосходила |
" |
f , то аппроксимация будет |
||||||
1+" |
||||||||
"-оптимальным решением: |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
|
f~ f |
" |
f = |
f |
|
|
||
|
|
|
: |
|
|
|||
|
1 + " |
(1 + ") |
|
|
||||
Чтобы максимально ограничить время работы аппроксимирующего алгоритма O(scalenf ), мы должны максимизировать параметр scale. При этом для сохранения "-оптимальности надо соблюдать ограничение scale n(1+"f ") . Однако проблема состоит в том, что в момент масштабирования величина оптимума f неизвестна, и непонятно, как выбрать оптимальный коэффициент scale .
Но можно усилить ограничение на scale, рассматривая вместо f нижнюю оценку оптимума flb:
{}
"flb
scale = max 1; n(1 + ") : (2.2)
Тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу. Таким образом, стоит задача выбора нижней оценки flb, которую, с одной стороны, можно найти быстро, а с другой — желательно, чтобы она была как можно ближе к f , т.к. это даст возможность увеличить коэффициент scale, и тем самым сильнее уменьшить коэффициенты c~1; : : : ; c~n и время выполнения алгоритма.
Общая схема представлена в алгоритме 27, где функции «KnapsackFPTAS» на вход, кроме обычных параметров рюкзака и точности аппроксимации ", передают функцию, используемую для получения нижней оценки стоимости решения.
2.2. АППРОКСИМАЦИЯ С ЗАДАННОЙ ТОЧНОСТЬЮ |
115 |
Осталось найти такие функции. Например, можно рассмотреть тривиальную аппроксимацию «MaxItemCost»:
flb cmax = max ci:
i
Получим функцию «KnapsackF P T ASMaxItemCost» в алгоритме 27. Сложность «KnapsackF P T ASMaxItemCost» будет:
O |
|
nf~ |
|
= O |
n ncmax |
= O |
|
n ncmax |
= |
||
|
(scale) |
( |
scale |
) |
( |
|
cmax" |
|
) |
||
|
|
n(1+") |
|||||||||
=O (n3(1 + ")) = O (n3 ) :
""
Можно ли улучшить эту оценку? Ответ на этот вопрос положителен. Для этого рассмотрим менее наивную аппроксимацию величины f . Вспомним алгоритм 19 «Рюкзак-Жадный» из раздела 2.1.3.
Для значения решения fG, полученного модифицированным жадным алгоритмом для задачи о рюкзаке, и оптимального значения f выполняется f2 fG f .
Таким образом, мы получаем более точную нижнюю оценку flb для f , которая, как правило, больше тривиальной оценки cmax. Посмотрим, поможет ли это нам улучшить верхнюю оценку времени выполне-
ния алгоритма.
( )
Теорема 8. Алгоритм «KnapsackF P T ASKnapsackGreedy» имеет сложность O n"2 .
Доказательство. Используя неравенство f~
O |
|
nf~ |
|
= O |
|
n f~ |
|
(scale) |
( |
" fG |
|||||
|
|
||||||
|
|
n(1+") |
|||||
f 2fG и (2.2), получаем оценку сложности алгоритма
) = O (2n2(1 + ")) = O (n2 ) :
" "
116 |
|
Глава 2. АППРОКСИМАЦИЯ С ГАРАНТИРОВАННОЙ ТОЧНОСТЬЮ |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 2.8: Карта-памятка раздела 2.2.2
2.2. АППРОКСИМАЦИЯ С ЗАДАННОЙ ТОЧНОСТЬЮ |
117 |
Алгоритм 27 PTAS для рюкзака
def knapsack_fptas(items, B, epsilon, lower_bound):
#Вычисляем нижнюю оценку стоимости
F_lb = lower_bound(items, B)
#параметр округления $scale$
scale = epsilon * F_lb / len(items) / (1 + epsilon)
# Набор c округленными стоимостями
Ds = [Item(item.cost/scale, item.weight) for item in items] knapset, indices = knapsack_dynprog_lightest(Ds, B) ApproxCost = sum(items[i].cost for i in indices)