Аппроксимация

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Аппроксимация

В этой статье рассматриваются два алгоритма, которые дают хоть и приближенное, но достаточно точное решение задачи. Алгоритм, который при поиске максимального значения некоторой функции f(x) возвращает результат, являющийся произведением фактического значения (найти которое может оказаться сложнейшей задачей) на некоторый коэффициент "c", называется алгоритмом c-аппроксимации (c-approximation algorithm).

Аппроксимацию особенно удобно использовать для решения NP-полных задач, для которых отсутствуют известные полиномиальные алгоритмы решения. В некоторых случаях аппроксимация используется, чтобы ускорить решение задачи, когда некоторая неточность вполне допустима, а для вычисления точного решения требуется значительное время. Например, алгоритм аппроксимации со сложностью O(log n) может оказаться гораздо предпочтительнее при большом количестве исходных данных, чем точный алгоритм, имеющий сложность O(n³).

Задача коммивояжера

Чтобы выполнить формальный анализ, необходимо формализовать задачу коммивояжера. Пусть имеется граф с весовой функцией w, которая присваивает ребрам графа положительные значения - роль такой функции, например, может играть расстояние между городами. Весовая функция удовлетворяет правилу неравенства треугольника, которое остается справедливым, если считать, что пути между городами лежат на Эвклидовой поверхности:

Для всех вершин x,y,z          w(x, y) + w(y, z) > w(x, z)

Задача состоит в том, чтобы посетить каждую вершину в графе (каждый город на карте коммивояжера) только один раз и вернуться в начальную вершину (штаб-квартиру компании), чтобы сумма весов ребер, составляющих маршрут движения, была минимальной. Обозначим эту минимальную сумму как wOPT. (Как мы уже знаем, точное решение задачи является NP-полным.)

Алгоритм аппроксимации действует, как описывается далее. Сначала для графа строится минимальное связывающее дерево (Minimal Spanning Tree, MST) с общим весом wMST. (Минимальное связывающее дерево - это подграф, включающий все вершины, не образующий циклы и имеющий минимальный общий вес ребер из всех возможных деревьев.)

Можно смело утверждать, что wMST <= wOPT, потому что wOPT - это общий вес циклического пути обхода всех вершин. Удаление любого ребра из такого графа порождает связывающее дерево, a wMST - это общий вес минимального связывающего дерева. Вооружившись этим наблюдением, мы приходим к 2-аппроксимации для wOPT, как описывается ниже:

1. Создание MST. Существует известный жадный алгоритм решения этой задачи со сложностью O(n*log n).

2. Обход MST из корня с посещением каждого узла и возврат в корень. Общий вес этого пути составляет 2 wMST <= 2wOPT.

3. Корректировка получившегося пути так, чтобы никакая вершина не посещалась более одного раза. Если возникнет ситуация, представленная на рисунке ниже - вершина y посещается более одного раза - тогда путь корректируется удалением ребер (x,y) и (y,z) и заменой их ребром (x,z). Согласно правилу треугольника, такая замена может только уменьшить общий вес пути.

   

В результате получился алгоритм 2-аппроксимации, потому что общий вес найденного пути превосходит вес оптимального пути не более чем в два раза.

Задача о максимальном разрезе

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

Мы выработали очень простой и понятный алгоритм 2-аппроксимации:

1. Разделить вершины на два произвольных непересекающихся множества, A и B.

2. Найти вершину v в A, имеющую больше связанных с ней вершин в A, чем в B. Если такая вершина не найдена, поиск максимального разреза завершается.

3. Перенести вершину v из A в B и перейти к шагу 2.

Пусть A - подмножество вершин и v - вершина в множестве A. Обозначим через deg_A(v) количество вершин в A, с которыми вершина v связана ребрами (то есть, количество ее соседей в множестве A). Имеется два подмножества, A и B. Обозначим как e(A, B) количество ребер между вершинами в разных подмножествах, и как e(A) - количество ребер между вершинами в множестве A.

Когда поиск по данному алгоритму завершается, для каждой вершины v в А будет выполняться соотношение deg_B(v) >= deg_A(v)? иначе алгоритм перейдет к шагу 2. Суммируя все вершины, получаем: e(A, B) > deg_B(v1) + ... + deg_B(vk) > deg_A(v1) + ... + deg_A(vk) > 2e(A), потому что каждое ребро справа было подсчитано дважды. Аналогично, e(A, B) > 2e(B) и, соответственно, 2e(A, B) > 2e(A) + 2e(B). Отсюда получаем 2e(A, B) > e(A, B) + e(A) + e(B), но справа находится общее количество ребер в графе. Таким образом, количество ребер, пересекающих границу двух подмножеств, будет не меньше половины всех ребер в графе. Количество ребер, пересекающих границу, не может быть больше общего количества ребер в графе, поэтому мы получили 2-аппроксимацию.

В заключение следует отметить, что алгоритм выполняет количество шагов, прямо пропорциональное количеству ребер в графе. Всякий раз, когда повторяется шаг 2, количество ребер, пересекающих границу, увеличивается как минимум на 1. А так как количество ребер, пересекающих границу, ограничено общим количеством ребер, общее количество шагов также ограничено этим числом.