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

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

Опр. Пусть дана задача 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 не существует ε – приближенного алгоритма для задачи коммивояжера.

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

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

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

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

Дата добавления: 2015-07-11