Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Көшіп жүрген сатушының түймелі түйіні (bottleneck travelling salesman problem) – дискретті немесе комбинаторлық оңтайландыру мәселесі. Мәселе – салмақты графтың ішіндегі Гамильтон циклін табу (әрбір түйінге дәл бір рет кіру), бұл циклдың ең ауыр жиегінің салмағын азайтады. Ол алғаш рет кейбір қосымша шектеулермен және толыққанды түрінде формулаланды.
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-толық. 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 – салмақтардың сұрыпталған тізбесіндегі жиектің бастапқы салмағының орны. Мысалы, осы түрлендіруден кейін Held-Karp алгоритмін бөтелке мойны 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.