Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Проблема путешествующего продавца с узким горлом (bottleneck traveling salesman problem, TSP) — это задача дискретной или комбинаторной оптимизации. Задача состоит в поиске гамильтонова цикла (посещающего каждый узел ровно один раз) во взвешенном графе, который минимизирует вес ребра с максимальным весом в этом цикле. Впервые она была сформулирована с некоторыми дополнительными ограничениями, а в полной мере — .
The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle (visiting each node exactly once) in a weighted graph which minimizes the weight of the highest weight edge of the cycle. It was first formulated by with some additional constraints, and in its full generality by .
Сложность
Известно, что задача является NP-трудной. Вариант этой задачи принятия решения: "для заданной длины x существует ли гамильтонов цикл в графе G, не содержащем ребер длиннее x?". NP-полнота следует непосредственно из сведения к задаче поиска гамильтонова цикла.
The problem is known to be NP hard. The decision problem version of this, "for a given length x is there a Hamiltonian cycle in a graph G with no edge longer than x? ", is NP complete. NP completeness follows immediately by a reduction from the problem of finding a Hamiltonian cycle.
Алгоритмы
Другое сведение, от задачи о TSP с узким местом к обычной задаче TSP (где целью является минимизация суммы длин ребер), позволяет использовать любой алгоритм для обычной TSP для решения задачи о TSP с узким местом. Если веса ребер в задаче о TSP с узким местом заменены любыми другими числами, сохраняющими тот же относительный порядок, решение для узкого места останется неизменным. Если, кроме того, каждое число в последовательности превышает сумму всех меньших чисел, то решение для узкого места также будет совпадать с решением обычной TSP. Например, такого результата можно достичь, присвоив каждому весу значение n^(i), где n — количество вершин в графе, а i — ранг исходного веса ребра в отсортированной последовательности весов. Например, после такого преобразования алгоритм Хельд-Карпа можно использовать для решения задачи о TSP с узким местом за время O(n^(2)2^(n)). Это наилучшее возможное приближение. Любой неориентированный граф можно преобразовать в метрическое пространство, установив веса его ребер равными 1 и расстояние между всеми несмежными парами вершин равным 2. Приближение с коэффициентом лучше 2 в этом метрическом пространстве можно использовать для определения, содержит ли исходный граф гамильтонов цикл, задачу, являющуюся NP-полной. Без предположения о том, что входные данные являются метрическим пространством, невозможно получить конечное отношение приближения.
Another reduction, from the bottleneck TSP to the usual TSP (where the goal is to minimize the sum of edge lengths), allows any algorithm for the usual TSP to also be used to solve the bottleneck TSP. If the edge weights of the bottleneck TSP are replaced by any other numbers that have the same relative order, then the bottleneck solution remains unchanged. If, in addition, each number in the sequence exceeds the sum of all smaller numbers, then the bottleneck solution will also equal the usual TSP solution. For instance, such a result may be attained by resetting each weight to n^(i) where n is the number of vertices in the graph and i is the rank of the original weight of the edge in the sorted sequence of weights. For instance, following this transformation, the Held–Karp algorithm could be used to solve the bottleneck TSP in time O(n^(2)2^(n)). This approximation ratio is best possible. For, any unweighted graph can be transformed into a metric space by setting its edge weights to 1 and setting the distance between all nonadjacent pairs of vertices to 2. An approximation with ratio better than 2 in this metric space could be used to determine whether the original graph contains a Hamiltonian cycle, an NP complete problem. Without the assumption that the input is a metric space, no finite approximation ratio is possible.