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

Задача коммивояжера представляет собой 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.