4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 01:22, 24 августа 2016
, 24 августа 2016→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | ||
Целевая функция: весовая функция <math>w(H) = \sum_{e \in H} w(e) \;</math> обхода. | |||
Цель: минимизация значения весовой функции. | |||
Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является неравенство треугольника, которое выглядит следующим образом: | Задача коммивояжера представляет собой 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. | ||
w(u, v) | |||
Если существует алгоритм с полиномиальным временем выполнения для решения задачи TSP, коэффициент аппроксимации которого зависит от n, то P = NP. Таким образом, следует рассматривать ограниченные экземпляры. Наиболее естественным ограничением является [[неравенство треугольника]], которое выглядит следующим образом: | |||
<math>w(u, v) \le w(u, x) + w(x, v) \;</math> для всех <math>u, v, x \in V \;</math>. | |||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину не менее одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом за счет пропускания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину не менее одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом за счет пропускания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | ||
== Основные результаты == | == Основные результаты == | ||