NP-трудные задачи и приближенные алгоритмы: В поисках компромисса
Когда мы сталкиваемся с NP-полными задачами, такими как задача коммивояжера или задача о рюкзаке, надежда на быстрое и абсолютно точное решение на больших данных исчезает. Но бизнес не может ждать годы, пока суперкомпьютер перебирает все варианты. В дискретной математике и проектировании алгоритмов на этот случай существует мощный план "Б" — приближенные алгоритмы и эвристики.
Если задачу нельзя решить оптимально за полиномиальное время, мы можем попытаться найти решение, которое "достаточно хорошо" и вычисляется быстро. Приближенный алгоритм (Approximation algorithm) — это алгоритм, который гарантированно работает за полиномиальное время и выдает решение, отличающееся от идеального математического оптимума не более чем на строго доказанный коэффициент (константу).
Например, в метрической задаче коммивояжера (где расстояния удовлетворяют правилу треугольника: путь напрямую всегда короче пути в обход) существует приближенный алгоритм Кристофидеса. Он гарантированно выдает маршрут, длина которого максимум в 1.5 раза (на 50%) превышает длину математически самого короткого маршрута. Алгоритм сначала находит минимальное остовное дерево, затем находит паросочетания для вершин нечетной степени и объединяет графы, находя эйлеров цикл. Все эти шаги работают очень быстро (O(V^3)).
Однако существуют задачи, для которых математически доказана невозможность создания хорошего приближенного алгоритма. Классический пример — задача поиска максимальной клики графа. Теорема Хастада (с использованием PCP-теоремы) доказывает, что эту задачу нельзя аппроксимировать с приемлемой точностью, если только P не равно NP. Это заставляет программистов прибегать к эвристикам и метаэвристикам.
Эвристики — это методы, основанные на здравом смысле (жадный подход), которые не дают никаких строгих математических гарантий, но часто хорошо работают на реальных (а не специально сгенерированных зловредных) данных. Для сложнейших оптимизаций применяются метаэвристики: генетические алгоритмы (имитация эволюции и скрещивания лучших решений), алгоритм имитации отжига (имитация физического процесса кристаллизации металлов с постепенным "остыванием" системы для выхода из локальных минимумов) и муравьиные алгоритмы. Эти методы лежат на стыке дискретной математики и искусственного интеллекта.
