algo-15-05-29
.pdfЛекция 34 по алгоритмам и структурам данных
Неофициальные записки лекций С.А.Объедкова
для студентов 2 потока 1 курса ПМИ ФКН НИУ ВШЭ записанные Ярославом Сергиенко
29 ìàÿ 2015 ã.
Приближенные алгоритмы
Идея приближенных алгоритмов состоит в том, что мы ищем не точный ответ OP T (который как правило невозможно найти быстро), а прибли-
женный ответ Approx, который отличается от OP T в известное количество
раз. Так, если наш алгоритм максимизирует какую-либо величину, то он может удовлетворять соотношению Approx > 12 OP T , а если минимизирует
òî Approx 6 2OP T .
Задача о вершинном покрытии. Мы приближенно ищем размер минимального вершинного покрытия графа G = (V; E), то есть такое наимень-
шее число вершин, что у любого ребра хотя бы один конец выбран. Первый алгоритм будет таким:
V1 = empty set
while exists (u, v) in E: u not in V1 and v not in V1: add u and v to V1
Для него возможно доказать соотношение Approx < 2OP T . Пусть k
размер минимального вершинного покрытия. Количество итераций цикла while не превосходит k. На каждой итерации добавляем две вершины, сле-
довательно размер найденного вершинного покрытия не превосходит 2k. Второй алгоритм:
V1 = empty set
whilte exists (u, v) in E: u not in V1, v not in V1
choose w incident to the largest number of uncovered edges: add w to V1
Он выглядит экономичнее предыдущего, но про него подобную оценку доказать нельзя. Предлагается запустить оба алгоритма, первый дает ответ гарантированно не больше 2OP T , а второй часто дает ответ лучше, но не
всегда.
Записки могут содержать ошибки.
1
Задача об обходе графа. Теперь, пусть на вход дан взвешенный граф G = (V; E) с положительными весами и нам требуется найти длину крат-
чайшего маршрута из v в себя, проходящего через каждую вершину. Пусть T минимальное остовное дерево G, R маршрут, полученный
обходом T , подвешенного за v. Если функция ! находит сумму весов ребер
ñучетом кратности, то
1)!(R) = 2!(T ), так как при обходе дерева каждое ребро посещается ровно по два раза,
2)!(T ) < OP T , так как объединение ребер оптимального маршрута яв-
ляется связным графом, следовательно его вес не меньше веса минимального остовного дерева; неравенство строгое, так как из того, что маршрут T замкнут, следует, что из него можно удалить ребро так, что объединение его ребер останется связным,
3)!(R) > OP T , так как OP T и R являются маршрутами, при том что OP T является маршрутом с минимальной стоимостью.
Связь задачи о покрытии, задачи о независимом множестве и задачи о клике. Заметим, что, если V1 вершинное покрытие графа G = (V; E), òî V n V1 независимое множество.
Åñëè V1 независимое множество (V; E), то V1 клика в графе (V; V 2 n
E).
Пусть k размер минимального вершинного покрытия в нашем графе. Тогда n k размер максимального независимого множества. Если V1 аппроксимация вершинного покрытия, то ее размер jV1j 6 2k. Но тогда V1 является аппроксимацией максимального независимого множества и имеет размер, не меньший n 2k. Тогда коэффициент аппроксимации будет равен
= |
|
n k |
= 1 + |
|
k |
|
|
n 2k . |
|||||
|
n 2k |
|
Задача о рюкзаке. Пусть у нас есть n предметов размеров s1; : : : ; sn и которые имеют ценность v1; : : : ; vn (мы будем рассматривать более простой случай, когда ценности являются натуральными числами) и рюкзак размера S. Мы хотим максимизировать суммарную ценность предметов в
рюкзаке, при том, что суммарный объем не должен превосходить S. Ответом будет максимальная стоимость.
В случае, кода ценности всех предметов являются натуральными числа- |
||||
на пересечении i-той строки и j-того |
|
n |
|
Sij |
|
P |
|
||
ми, можно рассмотреть таблицу из V = |
i=1 vi столбцов и n строк. Тогда |
|||
|
столбца будет записано число |
|
||
минимальной размер, позволяющий достичь суммарной стоимости |
j, åñëè |
брать только первые i предметов. Заметим, что рекурсивная формула будет
такой: |
(+1 |
|
; |
иначе |
1 |
S1;j = |
; |
||||
|
S |
|
åñëè j = v |
|
|
|
1 |
|
|
|
Si;j = minfSi 1;j; si + Si 1;j vi g
Этот алгоритм дает точный ответ и время его работы будет равна O(nV ), что очень плохо, так как суммарная ценность предметов V может быть
2
сколь угодно большой и в худшем случае может расти экспоненциально от размера входа.
Идея для аппроксимации состоит в том, чтобы разделить v1; : : : ; vn íà x и результат округлить вверх. Тогда рассмотрим, как этот алгоритм от-
|
|
|
|
|
|
|
|
|
|
|
|
|
vi |
|
|
|
vj |
|
|
|
|
|
|
|
|
|
÷òî jvi vjj < x. Тогда абсолютная ошибка меньше, чем nx. |
|
= |
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
||||||||||||||||||||
личается от оптимального. Ошибка возможна только если |
|
x |
|
|
x |
|
, òàê |
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тогда относи- |
|
|
|
|
||||||||
тельная ошибка будет меньше, чем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
< |
|
VOPT |
= 1+ |
nx |
|
6 1+ |
|
nx |
|
= 1+ |
nVmax(1 c) |
|
|
|
= |
1 |
; |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
VOPT nx |
VOPT nx |
Vmax nx |
|
|
|
|
c |
|||||||||||||||||||
|
|
|
|
n Vmax |
|
|
|
|
|
n |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
nVmax(1 |
|
c) |
|
|
|
|
|||||
ãäå Vmax = maxi=1;:::;n vi, òàê êàê |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
x = |
Vmax |
(1 c); |
ãäå 0 6 c < 1: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тогда сложность этого алгоритма будет описываться формулой
n3
O(nV ) ) O(n2Vmax) ) O 1 c :
3