11.2.Приближенные алгоритмы

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

Опр. Пусть дана задача Z=(F,c) и – c(x*) значение функции стоимости c на оптимальном решении x*. Пусть дан некоторый алгоритм W, результатом работы которого будет выдача некоторого решения x’, а c_W(x’)– значение функции стоимости на решении x’. Будем говорить, что алгоритм W является ε-приближенным (или алгоритмом с оценкой точности ε), если выполняется следующее соотношение:|( c_W(x’)- c(x*))/ c(x*) |≤ ε.

Опр. Пусть дана задача Z=(F,c) и – c(x*) значение функции стоимости c на оптимальном решении x*. Пусть дан некоторый алгоритм W, результатом работы которого будет выдача некоторого решения x’, а c_W(x’)– значение функции стоимости на решении x’. Будем говорить, что алгоритм W является эвристическим, если про соотношение c_W(x’) и c(x*) ничего не известно.

Часто эвристические алгоритмы называют приближенными без оценки точности. Примером эвристического алгоритма для задачи коммивояжера называется жадный алгоритм или алгоритм иди в ближайшую.

Пример. Дана задача коммивояжера на n городах с матрицей попарных расстояний. Будем строить решение x’ следующим образом.

Из вершины 1 идем в вершину i₁ такую, что ребро (1,i₁) имеет минимальный вес среди всех ребер вида (1,j), на втором шаге из вершины i₁ идем в вершину i₂ 1 такую, что ребро (i₁,i₂) имеет минимальный вес среди всех ребер вида (i₁,j), j 1; из вершины i₂ идем в вершину i₃ 1, i₂ такую, что ребро (i₂,i₃) имеет минимальный вес среди всех ребер вида (i₂,j), j 1,i₂. И так далее. На последнем шаге замыкаем цикл.

Легко привести пример того, что этот алгоритм может не находить оптимального решения. Трудоемкость алгоритма не превосходит O(n²), но мы ничего не можем сказать про соотношение c_W(x’) и c(x*).

А как обстоят дела с приближенными алгоритмами для этой задачи?

Теорема. Если P NP, то при любом ε >0 не существует ε – приближенного алгоритма для задачи коммивояжера.

Доказательство. От противного. Пусть такой алгоритм W для некоторого ε >0 существует. Покажем, что тогда P=NP. Для этого мы докажем, что алгоритм W решает задачу гамильтонов цикл. Так как эта последняя является NP-полной, то отсюда и будет следовать равенство P=NP.

Пусть входом задачи гамильтонов цикл является граф G=(V,E). Постоим на его основе условие некоторой вспомогательной задачи коммивояжера на |V| городах, а расстояние между городами i и j положим равным 1, если ребро (i,j) есть в графе G, и равным 2+ ε|V|, если такого ребра в графе нет.

Применим наш полиномиальный алгоритм W для получения ε –приближенного решения вспомогательной задачи коммивояжера. Докажем, что этот алгоритм выдаст обход коммивояжера длины |V| тогда и только тогда, когда в G есть гамильтонов цикл. Очевидно, что, если такой обход выдан, то каждое ребро в нем имеет длину единица, т.е. соответствует ребру графа G, а выданный обход, таким образом, гамильтонову циклу этого графа. И наоборот, если в графе G есть гамильтонов цикл, то алгоритм обязательно выдаст обход длины |V|потому, что в случае выдачи любого другого обхода (а в этом случае минимальное значение длины такого обхода не меньше |V|-1+2+ ε|V|) нарушается свойство ε –приближенности алгоритма:

(|V|-1+2+ ε|V|-|V|)/|V|=1/|V|+ ε > ε.

Теорема доказана.

В некотором смысле ситуация с приближенными алгоритмами для задачи коммивояжера типична для NP-трудных задач: полиномиальные эвристические алгоритмы всегда есть, а полиномиальных приближенных (для общего случая) нет.

Теорема. Если для задачи о клике существует ε – приближенный алгоритм для некоторого ε>0, то тгда для этой задачи можно будет построить ε – приближенный алгоритм для любого 1> ε>0.

Однако, в отличие от точных алгоритмов, полиномиальные приближенные можно построить для интересных частных случаев NP-трудных задач. Например, для задачи коммивояжера с неравенством треугольника (для любых трех вершин i,j,k длина ребра (i,j) не превосходит суммы длин ребер (i,k)и (k,j)) существуют приближенные алгоритмы. Одним из самых первых был 1/2-приближенный алгоритм Кристофидеса.

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