4551
правка
Метрическая задача коммивояжера: различия между версиями
Перейти к навигации
Перейти к поиску
м
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 23:13, 29 августа 2016
, 29 августа 2016нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 90: | Строка 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>. Сокращения путей не требуется; вес обхода, вычисленного алгоритмом, равен <math>\approx 3 n \;</math>. Оптимальный обход состоит из всех пунктирных ребер, а также самого левого и самого правого сплошных ребер. Вес этого обхода составляет <math>(2n - 1)(1 + \epsilon) + 2 \approx 2n \;</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/ можно найти множество экземпляров. | ||
| Строка 113: | Строка 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) | ||