4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 00:08, 22 августа 2016
, 22 августа 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 5: | Строка 5: | ||
Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | Допустимые решения: все гамильтоновы обходы, т.е. подграфы H графа G, которые являются связными и каждая вершина которых имеет степень 2. | ||
Целевая функция: весовая функция 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 также называется коэффициентом аппроксимации или | Задача коммивояжера представляет собой NP-полную задачу. Это означает, что для ее решения не существует алгоритма с полиномиальным временем выполнения, если только не окажется верным P = NP. Одним из способов разрешения этой проблемы являются алгоритмы аппроксимации. Алгоритм аппроксимации задачи TSP с полиномиальным временем выполнения называется алгоритмом a-аппроксимации, если обход H, полученный с его помощью, удовлетворяет неравенству w(H) < a ■ OPT(G). Здесь OPT(G) – вес обхода с минимальным весом для графа G. Если граф G понятен из контекста, можно записывать его просто в виде «OPT». Алгоритм a-аппроксимации всегда дает в итоге допустимое решение, целевое значение которого не более чем в a раз отличается от оптимального значения. a также называется коэффициентом аппроксимации или гарантией эффективности. a не обязательно должно быть константой; оно может быть функцией, зависящей от размера входного экземпляра или количества вершин n. | ||
| Строка 16: | Строка 16: | ||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину не менее одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом за счет | Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы аппроксимации с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину не менее одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом за счет пропускания любой вершины, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 23: | Строка 24: | ||
Алгоритм удвоения дерева известен с давних времен. Следующая лемма доказывает верхнюю границу гарантии эффективности алгоритма удвоения дерева. | Алгоритм удвоения дерева известен с давних времен. Следующая лемма доказывает верхнюю границу гарантии эффективности алгоритма удвоения дерева. | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника. | Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовая функция w: E ! Q>o, удовлетворяющая неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся 2”-аппроксимацией. | Требуется: найти гамильтонов обход для G, являющийся 2”-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | 2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | ||
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода.) Вернуть полученный гамильтонов обхода H. | |||
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, эта вершина пропускается, и мы переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется сокращением обхода) | |||
Алгоритм 1. Алгоритм удвоения дерева | Алгоритм 1. Алгоритм удвоения дерева | ||
| Строка 46: | Строка 45: | ||
Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения обхода на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации. | Доказательство. Согласно лемме 1, w(T) < OPT. Поскольку мы удваиваем каждое ребро T, вес T’ составляет w(T0) = 2w(T) < 2OPT. В результате сокращения обхода на шаге 3 путь в T’ заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, w(T) < OPT. Это доказывает утверждение по поводу эффективности аппроксимации. | ||
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □ | Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. □ | ||
| Строка 51: | Строка 51: | ||
Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на U С V, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется совершенным, если каждая вершина из U инцидентна ребру из M. | Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на U С V, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется совершенным, если каждая вершина из U инцидентна ребру из M. | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника. | Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой функцией w: E ! Q>o, удовлетворяющей неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией. | Требуется: найти гамильтонов обход для G, являющийся 3/2”-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U. | 2: Пусть U С V – множество всех вершин, имеющих нечетную степень в T. Для графа G вычислить совершенное паросочетание с минимальным весом M на U. | ||
3: Вычислить эйлеров обход для T [ M (рассматриваемый как мультиграф). | |||
4: Выполнить сокращение путей этого эйлерова обхода до гамильтонова обхода H. | |||
Алгоритм 2. Алгоритм Кристофидеса | |||
Лемма 3. Пусть U С V;#U нечетно. Пусть M – совершенное паросочетание с минимальным весом на U. Тогда w(M) < OPT/2. | |||
Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □ | Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращение в H, получая обход H0 на G|U следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H0 соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, w(H0) < w(H). Поскольку #U является четным, H0 представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает w(H0)/2 < OPT/2. □ | ||
| Строка 80: | Строка 76: | ||
Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n — 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, w(T) < OPT. Согласно лемме 3, w(M) < OPT/2. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. w(H) < |OPT. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, время выполнения которого составляет O(n3). □ | Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 2(n — 1), а это четное число. Таким образом, совершенное паросочетание на U существует. Вес эйлерова обхода, очевидно, составляет w(T) + w(M). Согласно лемме 1, w(T) < OPT. Согласно лемме 3, w(M) < OPT/2. Вес w(H) вычисленного обхода H не превышает веса эйлерова обхода согласно неравенству треугольника, т.е. w(H) < |OPT. Таким образом, полученный алгоритм представляет собой алгоритм 3/2-аппроксимации, время выполнения которого составляет O(n3). □ | ||
== Применение == | |||
Экспериментальный анализ показывает, что алгоритм Кристофидеса сам отклоняется от оптимального обхода на величину от 10 до 15% [ ]. Однако он может служить хорошей отправной точкой для других эвристик обхода – таких как эвристика Лина-Кернигана. | |||
Рисунок 1. Пример для алгоритма Кристофидеса. В графе 2n + 1 вершин. Сплошные ребра имеют вес 1, пунктирные – вес 1 + e. | |||
== Открытые вопросы == | |||
Анализ алгоритма 2 несложен. Примером может служить метрическое пополнение графа, изображенного на рис. 1. Его единственное минимальное остовное дерево состоит из всех склошных ребер. Оно содержит только две вершины с нечетными степенями. Ребро между этими двумя вершинами имеет вес (1 + е)(и + 1). Сокращений не требуется; вес обхода, вычисленного алгоритмом, равен £rf n. Оптимальный обход состоит из всех пунктирных ребер, а также самого левого и самого правого сплошных ребер. Вес этого обхода составляет (2n - 1)(1 + e) + 2 & 2n. | |||
Вопрос о существовании алгоритма аппроксимации с лучшей гарантией эффективности является главным нерешенным вопросом а теории алгоритмов аппроксимации. | |||
Хельд и Карп [ ] разработали алгоритм на основе линейного программирования, вычисляющий нижнюю границу веса оптимального обхода для задачи коммивояжера. Была предложена гипотеза, что вес оптимального обхода для задачи коммивояжера не более чем в 4/3 раза превышает его нижнюю границу; однако эта гипотеза уже более 30 лет остается недоказанной. Алгоритмическое доказательство гипотезы позволило бы получить алгоритм 4/3-аппроксимации для метрической задачи коммивояжера. | |||
== Экспериментальные результаты == | |||
В работе [3] было отмечено отклонение в 10-15% от оптимального (говоря точнее – от границы Хельда-Карпа) на различных экземплярах задачи. | |||
== Наборы данных == | |||
На странице 8-го тура задач по реализации DIMACS по адресу www.research.att.com/~dsj/chtsp/ можно найти множество экземпляров. | |||
== См. также == | |||
*'' [[Минимальные остовные деревья]] | |||
== Литература == | |||
Кристофидес не публиковал самостоятельно свой алгоритм. Он обычно цитируется как один из двух технических отчетов Университета Карнеги-Меллона – TR 388 Института индустриальных исследований (теперь он называется Школой бизнеса Теппера) и CS-93-13. Ни один из них в настоящее время не доступен в Университете Карнеги-Меллона [из личной переписки с Фрэнком Бальбахом Balbach, 2006 г.]. В материалах конференции были приведены тезисы объемом в 1 страницу. Однако алгоритм быстро проложил себе дорогу в учебники по теории алгоритмов; см., например, [7]. | |||
1. Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, (1976). Also: Carnegie-Mellon University Technical Report CS-93-13, 1976. Abstract in Traub, J.F. (ed.) Symposium on new directions and recent results in algorithms and complexity, pp. 441. Academic Press, New York (1976) | |||
2. Held, M., Karp, R.M.: The traveling salesman problem and minimum spanning trees. Oper. Res. 18,1138-1162 (1970) | |||
3. Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht (2002) | |||
4. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985) | |||
5. Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982) | |||
6. Sahni, S., Gonzalez, T.: P-complete approximation problems. J.ACM 23, 555-565 (1976) | |||
7. Vazirani,V.V.: Approximation Algorithms. Springer, Berlin (2001) | |||
8. Traveling Salesman Problem. www.tsp.gatech.edu (2006). Accessed 28 Mar 2008 | |||