Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[283]

При этом степень и коэффиценты полинома, ограничивающего время работы, могут сколь угодно быстро расти с уменьшением е. Более сильное ограничение таково: схема приближения называется полностью полиномиальной (fully polynomial-time approximation scheme), если время работы обраничено некоторым полиномом от га и от 1/е, где га - размер входа, ае - оценка относительной ошибки.

Например, время работы может быть ограничено величиной (1/е)2га3. В этом случае уменьшение е, скажем, в 3 раза приводит к увеличению времени работы в 9 раз.

План главы

В первых трёх разделах рассматриваются полиномиальные приближённые алгоритмы для трёх NP-полных задач. Последний раздел содержит пример полностью полиномиальной схемы приближения. В разделе 37.1 приводится полиномиальный приближенный алгоритм, решающий задачу о минимальном вершинном покрытии с ошибкой не более чем в 2 раза. В разделе 37.2 рассматривается задача о коммивояжёре. Если расстояния удовлетворяют неравенству треугольника, то имеется приближённый алгоритм, решающий эту задачу с ошибкой не более чем в 2 раза. В общем случае (когда неравенство треугольника не обязательно) такого алгоритма не существует ни для какой фиксированной оценки ошибки (если только Р не равно NP). В разделе 37.3 строится жадный приближённый алгоритм для задачи о покрытии множествами. Даваемое им решение отличается от оптимального не более чем логарифмическим (от числа элементов) множителем. Наконец, в разделе 37.4 мы приводим полностью полиномиальную схему приближения для задачи о сумме подмножества.

37.1. Задача о вершинном покрытии

Эта задача описана в разделе 36.5.2. Там же доказана её NP-полнота. Напомним, что вершинным покрытием (vertex cover) неориентированного грана G = (V, Е) мы называем некоторое семейство его вершин V С V с таким свойством: для всякого ребра (и, v) графа G хотя бы один из концов и, v этого ребра содержится в V. Размером вершинного покрытия считаем количество входящих в него вершин.

Задача о вершинном покрытии (vertex-cover problem) состоит в нахождении оптимального вершинного покрытия (optimal vertex cover), то есть вершинного покрытия минимального размера. Эта проблема является NP-трудной, поскольку соответствующая проблема разрешения является NP-полной (по теореме 36.12).

Несмотря на это несложно найти вершинное покрытие, которое


Рис. 37.1 37.1 Работа алгоритма APPROX-VERTEX-COVER (а) Исходный граф G с 7 вершинами и 8 рёбрами. (Ь) На первом шаге выбрано ребро (Ь, с) (жирное). Его концы Ъ и с (серые) включаются в вершинное покрытие С. Пунктирные рёбра (а, Ь), (с, е) и (с, d) покрыты и удаляются, (с) Ребро (е, /) добавляется к С. (d) Ребро (d, g) добавляется к С. (е) Результат работы алгоритма, множество С, содержит 6 вершин Ь, с, d, е, /, g. (f) Оптимальное вершинное покрытие этого графа содержит только три вершины (b,d,e).

хуже оптимального не более чем в 2 раза. Это делает алгоритм Approx-Vertex-Cover:

4 возьмём произвольное ребро (и, v) из Е

6 удалим из Е все рёбра, инцидентные и или v

На рисунке 37.1 приведюн пример работы алгоритма Approx-Vertex-Cover. Алгоритм строит вершинное покрытие С постепенно. Вначале С пустое (строка 1), а множество Е содержит все рёбра графа (строка 2). Затем в цикле (строки 3-6) мы берём ребро из Е, добавляем его концы и и v в С, а из Е изымаем все рёбра, имеющие своим концом и или v. Время работы этого алгоритма есть О(Е) (при соответствующем представлении множества Е).

Теорема 37.1. Алгоритм Approx-Vertex-Cover работает с ошибкой не более чем в 2 раза.

Доказательство. Прежде всего заметим, что даваемое им мно-ежство С является вершинным покрытием. В самом деле, цикл в строках 3-6 продолжается до тех пор, пока множество непокрытых рёбер Е не станет пустым.

Чтобы убедиться, что число вершин в С не более чем вдвое хуже оптимально, посмотрим на множество А рёбер, выбираемых в ходе работы алгоритма. Никакие два из них не имеют общей вершины (после того, как ребро выбрано в строке 4, все имеющие с ним общую вершину удаляются в строке 6). Поэтому общее число вершин в С вдвое больше числа рёбер в А. Заметим теперь, что любое вершинное покрытие (в частности, оптимальное покрытие С*) содержит хотя бы одну вершину каждого выбранного ребра, и для разных рёбер эти вершины разные. Таким образом, А С*, и, следовательно, \С\ = 2\А\ 2С*. Что и требовалось доказать.

Упражнения.

37.1-1. Приведите пример графа, для которого этот алгоритм всегда даёт неоптимальное решение.

37.1-2. Профессор Шипилов предлагает такой алгоритм решения задачи о вершинном покрытии: взять вершину наибольшей степени, включить её в покрытие, удалить все смежные рёбра, повторить это ещё раз и так далее. Приведите пример графа, для которого этот способ даёт решение, отличающееся от оптимального более чем в 2 раза.

37.1-3. Постройте жадный алгоритм, который находит оптимальное вершинное покрытие для графа, являющегося деревом, за


линейное время.

37.1-4. Как мы видели в доказательстве теоремы 6.12, задача о вершинном покрытии и задача о клике взаимно дополнительны: минимальное вершинное покрытие является дополнением к максимальной клике в дополнительном графе. Можно ли отсюда заключить, что и для задачи о клике имеется приближённый алгоритм с ошибкой не более чем в константу раз? Почему?

37.2. Задача коммивояжёра

Эта задача описана в разделе 36.5.5 и состоит в следующем. Для каждого ребра (и, v) полного неориентированного графа G = (V, Е) известна его стоимость c(u,v). Необходимо найти гамильтонов цикл минимальной стоимости. Стоимостью цикла (и вообще любого множества рёбер АСЕ) мы считаем сумму стоимостей его рёбер:

(u,v)EA

На практике функция стоимости рёбер обычно удовлетворяет неравенству треугольника, которое говорит, что промежуточная остановка w на пути из и в v увеличивает его стоимость:

с(и, w) с(и, v) + c(v, w)

для любых трёх вершин и, v, w. Например, это неравенство выполнено, если вершинами графа являются точки плоскости и стоимостью ребра считается его длина (расстояние между его концами).

Как показывает упражнение 37.2-1, даже в предположении неравенства треугольника задача коммивояжёра остаётся NP-полной. Тем самым мало шансов найти полиномиальный алгоритм, дающий оптимальный путь, и имеет смысл искать приближённые алгоритмы.

В разделе 37.2.1 мы рассмотрим приближённый алгоритм, решающий эту задачу (в предположении неравенства треугольника) с ошибкой не более чем в 2 раза. Неравенство треугольника существенно: в общем случае алгоритма, решающего её с ошибкой не более чем в С раз, не существует ни для какого фиксированного С (если только Р не равно NP).

37.2.1. Задача коммивояжёра (с неравенством треугольника)

Мы можем воспользоваться алгоритмом MST-Prim отыскания минимального покрывающего дерева из раздела 24.2, переделав его в цикл. Если выполнено неравенство треугольника, то этот цикл не более чем вдвое длиннее оптимального.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]