4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 11: | Строка 11: | ||
Задача коммивояжера представляет собой NP-полную задачу. Это означает, что для ее решения не существует алгоритма с полиномиальным временем выполнения, если только не окажется верным 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. | ||
Строка 19: | Строка 19: | ||
Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют алгоритмы | Соответствующая задача носит название метрической задачи коммивояжера (Metric TSP). Для этой задачи существуют аппроксимационные алгоритмы с константным коэффициентом. Отметим, что для решения метрической задачи коммивояжера достаточно найти обход, который посещает любую вершину ''не менее'' одного раза. При наличии такого обхода мы сможем найти гамильтонов обход с меньшим или равным весом, просто пропуская любую вершину, которую мы уже посещали. Согласно неравенству треугольника, вес нового обхода не может возрастать. | ||
== Основные результаты == | == Основные результаты == | ||
Простой 2-аппроксимацией метрической задачи коммивояжера является алгоритм удвоения дерева. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. [[Остовное дерево]] T графа G = (V, E, w) представляет собой связный ациклический подграф G, содержащий все вершины | Простой 2-аппроксимацией метрической задачи коммивояжера является ''алгоритм удвоения дерева''. Он использует минимальные остовные деревья для вычисления гамильтоновых обходов. [[Остовное дерево]] T графа G = (V, E, w) представляет собой связный ациклический подграф G, содержащий все вершины V. Вес w(T) такого остовного дерева равен сумме весов его ребер, т.е. <math>w(T) = \sum_{e \in T} w(e) \;</math>. Остовное дерево является минимальным, если его вес минимален среди всех остовных деревьев G. Можно эффективно вычислить минимальное остовное дерево, например, при помощи алгоритмов Прима или Крускала (см., к примеру, [5]). | ||
Алгоритм удвоения дерева известен с давних времен. Следующая лемма | Алгоритм удвоения дерева известен с давних времен. Следующая лемма необходима для доказательства верхней границы гарантии эффективности алгоритма удвоения дерева. | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и | Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовой функцей <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся | Требуется: найти гамильтонов обход для G, являющийся 2-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | 2: Продублировать каждое ребро T и получить эйлеров мультиграф T’. | ||
3: Вычислить эйлеров обход для T (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, | 3: Вычислить эйлеров обход для T' (например, при помощи поиска в глубину по T). При посещении вершины эйлерова обхода, которая ранее уже была посещена, пропускаем эту вершину | ||
и | и переходим к следующей непосещенной вершине эйлерова обхода. (Этот процесс называется ''сокращением обхода''). | ||
Вернуть полученный гамильтонов обход H. | Вернуть полученный гамильтонов обход H. | ||
Строка 43: | Строка 44: | ||
'''Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда <math>w(T) \le OPT \;</math>.''' | '''Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда <math>w(T) \le OPT \;</math>.''' | ||
Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. | Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. <math>\Box</math> | ||
'''Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.''' | '''Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.''' | ||
Доказательство. Согласно лемме 1, <math>w(T) \le OPT \;</math>. Поскольку мы удваиваем каждое ребро T, вес | Доказательство. Согласно лемме 1, <math>w(T) \le OPT \;</math>. Поскольку мы удваиваем каждое ребро T, вес T' составляет <math>w(T') = 2w(T) \le 2 OPT \;</math>. В результате сокращения обхода на шаге 3 путь в T' заменяется одним ребром. Согласно неравенству треугольника, сумма весов ребер на таком пути не меньше веса ребра, которым он заменяется. (Для произвольных весовых функций данный алгоритм оказывается недействительным). Следовательно, <math>w(H) \le w(T') \;</math>. Это доказывает утверждение по поводу эффективности аппроксимации. | ||
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. | Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. <math>\Box</math> | ||
Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. Паросочетание M для графа G называется паросочетанием на <math>U \subseteq V \;</math>, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется [[совершенное паросочетание|совершенным]], если каждая вершина из U инцидентна ребру из M. | Алгоритм Кристофидеса (алгоритм 2) представляет собой продуманное уточнение алгоритма удвоения дерева. Вначале он вычисляет минимальное остовное дерево. Затем для всех вершин, имеющих нечетную степень в T, он вычисляет совершенное паросочетание с минимальным весом. [[Паросочетание]] M для графа G называется паросочетанием на <math>U \subseteq V \;</math>, если все ребра M состоят из двух вершин подмножества U. Такое паросочетание называется [[совершенное паросочетание|совершенным]], если каждая вершина из U инцидентна ребру из M. | ||
Дано: полный неориентированный граф без циклов G = (V, E, w) с весовой | Дано: полный неориентированный граф без циклов G = (V, E, w) с взвешенными ребрами и весовой функцей <math>w: E \to \mathbb{Q}_{ \ge 0}</math>, удовлетворяющей неравенству треугольника. | ||
Требуется: найти гамильтонов обход для G, являющийся 3/ | Требуется: найти гамильтонов обход для G, являющийся 3/2-аппроксимацией. | ||
1: Вычислить минимальное остовное дерево T графа G. | 1: Вычислить минимальное остовное дерево T графа G. | ||
Строка 69: | Строка 70: | ||
'''Лемма 3. Пусть <math>U \subseteq V \;</math>, #U | '''Лемма 3. Пусть <math>U \subseteq V \;</math>, #U четно. Пусть M – совершенное паросочетание с минимальным весом на U. Тогда <math>w(M) \le OPT/2 \;</math>.''' | ||
Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем | Доказательство. Пусть H – оптимальный гамильтонов обход на G. Выполняем сокращения в H, получая обход H' на <math>G|_U \;</math> следующим образом: H порождает перестановку вершин в U, представляющую собой порядок, в котором они посещаются по ходу H. Соединим вершины U в порядке, заданном перестановкой. Каждому ребру в H' соответствует путь в H, соединяющий две вершины этого ребра. Согласно неравенству треугольника, <math>w(H') \le w(H) \;</math>. Поскольку #U является четным, H' представляет собой объединение двух паросочетаний. Вес более легкого из них не превышает <math>w(H')/2 \le OPT/2 \;</math>. <math>\Box</math> | ||
Строка 77: | Строка 78: | ||
Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения. | '''Теорема 4. Алгоритм 2 представляет собой алгоритм 3/2-аппроксимации с полиномиальным временем выполнения.''' | ||
Доказательство. Вначале отметим, что количество вершин с нечетной степенью в остовном дереве является четным, поскольку сумма степеней всех вершин равна 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> | |||
== Применение == | == Применение == | ||
Строка 88: | Строка 90: | ||
Рисунок 1. Пример для алгоритма Кристофидеса. В графе 2n + 1 вершин. Сплошные ребра имеют вес 1, пунктирные – вес <math>1 + \epsilon \;</math>. | Рисунок 1. Пример для алгоритма Кристофидеса. В графе 2n + 1 вершин. Сплошные ребра имеют вес 1, пунктирные – вес <math>1 + \epsilon \;</math>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Анализ алгоритма 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>. | ||
Вопрос о существовании алгоритма | Вопрос о существовании аппроксимационного алгоритма с лучшей гарантией эффективности является главным нерешенным вопросом в теории аппроксимационных алгоритмов. | ||
Хельд и Карп [2] разработали алгоритм на основе линейного программирования, вычисляющий нижнюю границу веса оптимального обхода для задачи коммивояжера. Была предложена гипотеза, что вес оптимального обхода для задачи коммивояжера не более чем в 4/3 раза превышает его нижнюю границу; однако эта гипотеза уже более 30 лет остается недоказанной. Алгоритмическое доказательство гипотезы позволило бы получить алгоритм 4/3-аппроксимации для метрической задачи коммивояжера. | Хельд и Карп [2] разработали алгоритм на основе линейного программирования, вычисляющий нижнюю границу веса оптимального обхода для задачи коммивояжера. Была предложена гипотеза, что вес оптимального обхода для задачи коммивояжера не более чем в 4/3 раза превышает его нижнюю границу; однако эта гипотеза уже более 30 лет остается недоказанной. Алгоритмическое доказательство гипотезы позволило бы получить алгоритм 4/3-аппроксимации для метрической задачи коммивояжера. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
В работе [3] было отмечено отклонение в 10-15% от оптимального (говоря | В работе [3] было отмечено отклонение в 10-15% от оптимального (точнее говоря, от границы Хельда-Карпа) на различных экземплярах задачи. | ||
== Наборы данных == | == Наборы данных == | ||
На странице 8-го тура задач по реализации DIMACS по адресу www.research.att.com/~dsj/chtsp/ можно найти множество экземпляров. | На странице 8-го тура задач по реализации DIMACS по адресу http://www.research.att.com/~dsj/chtsp/ можно найти множество экземпляров. | ||
Строка 111: | Строка 115: | ||
== Литература == | == Литература == | ||
Кристофидес не публиковал самостоятельно свой алгоритм. Он обычно цитируется | Кристофидес не публиковал самостоятельно свой алгоритм. Он обычно цитируется по одному из двух технических отчетов Университета Карнеги-Меллона – 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) | 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) |
правок