4551
правка
Метрическая задача коммивояжера: различия между версиями
Материал из WEGA
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 22:57, 20 августа 2016
, 20 августа 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
Целевая функция: весовая функция w(H) = Pe2H w(e) пути. Цель: минимизация значения весовой функции. | Целевая функция: весовая функция 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. | |||
Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является неравенство треугольника, которое выглядит следующим образом: | |||
w(u, v) < w(u, x) + w(x, v) для всех u, v, x 2 V. | |||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти путь, который посещает любую вершину не менее одного раза. При наличии такого пути мы сможем найти гамильтонов путь с меньшим или равным весом за счет отбрасывания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового пути не может возрастать. | |||
