4551
правка
Метрическая задача коммивояжера: различия между версиями
Материал из WEGA
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 23:09, 29 августа 2016
, 29 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 20: | Строка 20: | ||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину ''не менее'' одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом, просто пропуская любую вершину, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину ''не менее'' одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом, просто пропуская любую вершину, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 79: | Строка 80: | ||
'''Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения.''' | '''Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения.''' | ||
Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n | Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n - 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, <math>w(T) \le OPT \;</math>. Согласно лемме 3, <math>w(M) \le OPT/2 \;</math>. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. <math>w(H) \le \frac{3}{2} OPT \;</math>. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, а его время выполнения составляет <math>O(n^3) \;</math>. <math>\Box</math> | ||
== Применение == | == Применение == | ||
| Строка 90: | Строка 92: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Анализ алгоритма 2 несложен. Примером может служить метрическое пополнение графа, изображенного на рис. 1. Его единственное минимальное остовное дерево состоит из всех сплошных ребер. Оно содержит только две вершины с нечетными степенями. Ребро между этими двумя вершинами имеет вес <math>(1 + \epsilon)(n + 1) \;</math>. | Анализ алгоритма 2 несложен. Примером может служить метрическое пополнение графа, изображенного на рис. 1. Его единственное минимальное остовное дерево состоит из всех сплошных ребер. Оно содержит только две вершины с нечетными степенями. Ребро между этими двумя вершинами имеет вес <math>(1 + \epsilon)(n + 1) \;</math>. Сокращения путей не требуется; вес обхода, вычисленного алгоритмом, равен <math>\approx 3 n \;</math>. Оптимальный обход состоит из всех пунктирных ребер, а также самого левого и самого правого сплошных ребер. Вес этого обхода составляет <math>(2n - 1)(1 + \epsilon) + 2 \approx 2n \;</math>. | ||
Вопрос о существовании алгоритма аппроксимации с лучшей гарантией эффективности является главным нерешенным вопросом а теории алгоритмов аппроксимации. | Вопрос о существовании алгоритма аппроксимации с лучшей гарантией эффективности является главным нерешенным вопросом а теории алгоритмов аппроксимации. | ||
