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

Допустимые решения: все гамильтоновы пути, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2.

Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции.

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

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