Loading AI tools
алгоритм поиска приближённых решений задачи коммивояжёра для случаев Из Википедии, свободной энциклопедии
Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство (симметричны и удовлетворяют неравенству треугольника)[1]. Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976[2][3][4], и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев.
Пусть будет представителем задачи коммивояжёра. То есть G является полным графом на множестве вершин V, а функция w назначает неотрицательные вещественные веса каждому ребру графа G. Согласно неравенству треугольника для любых трёх вершин u, v и x должно выполняться .
Алгоритм можно описать на псевдокоде следующим образом[1].
Стоимость решения, полученного алгоритмом, лежит в границах 3/2 от оптимального. Для доказательства этого факта предположим, что C является оптимальным обходом задачи коммивояжёра. Удаление ребра из C даёт стягивающее дерево, которое должно иметь вес, не меньший веса минимального стягивающего дерева, откуда следует, что . Далее нумеруем вершины O в циклическом порядке по C и делим C на два множества путей — одно имеет нечётные номера первых вершины в циклическом порядке, а второе имеет чётные номера. Каждый набор путей соответствует совершенному паросочетанию множества O, которое сочетает в пару две конечные точки каждого пути, а вес этого сочетания не превосходит веса путей. Поскольку эти два множества путей разбивают рёбра C, одно из этих двух множеств имеет максимум половину веса C, и благодаря неравенству треугольника их соответствующее паросочетание имеет вес, который также не менее половины веса C. Совершенное паросочетание минимального веса не может иметь больший вес, так что . Сложение весов T и M даёт вес эйлерова цикла, который не превосходит . Благодаря неравенству треугольника сокращение не увеличивает вес, так что вес результата также не превосходит [1].
Существуют экземпляры задачи коммивояжёра, на которых алгоритм Кристофидеса находит решение, которое произвольно близко 3/2. Один из таких классов задач сформирован путём из n вершин с весами рёбер 1 вместе с набором рёбер, соединяющих вершины, отстоящие вдоль пути на два шага, с весами , где выбирается близким к нулю, но положительным. Все оставшиеся рёбра полного графа имеют расстояния, равные кратчайшим путям в этом подграфе. Тогда минимальное стягивающее дерево будет задано путём длины и только две нечётные вершины будут конечными точками пути и его совершенное паросочетание состоит из одного ребра с весом примерно n/2. Объединение дерева и паросочетания является циклом без сокращений вершин и весом примерно . Однако оптимальное решение использует рёбра весом вместе с двумя рёбрами веса 1, инцидентных концам пути, и его полный вес равен , что близко к n для малых значений . Отсюда мы получаем аппроксимационный коэффициент 3/2[5].
Дано: полный граф, веса рёбер которого удовлетворяют неравенству треугольника | |
Вычисляем минимальное остовное дерево T | |
Вычисляем множество вершин O с нечётной степенью в T | |
Образуем подграф графа G, используя лишь вершины множества O | |
Строим совершенное паросочетание минимального веса M в этом подграфе | |
Объединяем паросочетание и стягивающее дерево T ∪ M для образования эйлерова мультиграфа | |
Вычисляем эйлеров обход | |
Удаляем повторяющиеся вершины и получаем результирующий обход |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.