Метрическая задача коммивояжера: различия между версиями

Задача коммивояжера представляет собой NP-полную задачу. Это означает, что для ее решения не существует алгоритма с полиномиальным временем выполнения, если только не окажется верным P = NP. Одним из способов разрешения этой проблемы являются алгоритмы аппроксимации. [[Алгоритм аппроксимации]] задачи TSP с полиномиальным временем выполнения называется алгоритмом <math>\alpha \;</math>-аппроксимации, если обход H, полученный с его помощью, удовлетворяет неравенству <math>w(H) \le \alpha \cdot OPT(G) \;</math>. Здесь OPT(G) – вес обхода с минимальным весом для графа G. Если граф G понятен из контекста, можно записывать его просто в виде «OPT». Алгоритм <math>\alpha \;</math>-аппроксимации всегда дает в итоге допустимое решение, целевое значение которого не более чем в <math>\alpha \;</math> раз отличается от оптимального значения. Коэффициент <math>\alpha \;</math> также называется коэффициентом аппроксимации или гарантией эффективности. <math>\alpha \;</math> не обязательно должен быть константой; он может быть функцией, зависящей от размера входного экземпляра или количества вершин n.

Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину ''не менее'' одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом, просто пропуская любую вершину, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать.

Вопрос о существовании алгоритма аппроксимации с лучшей гарантией эффективности является главным нерешенным вопросом в теории алгоритмов аппроксимации.