4551
правка
Метрическая задача коммивояжера: различия между версиями
Материал из WEGA
Метрическая задача коммивояжера (посмотреть исходный код)
Версия от 15:39, 24 августа 2016
, 24 августа 2016→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда w(T) < | '''Лемма 1. Пусть T – минимальное остовное дерево G = (V, E, w). Тогда <math>w(T) \le OPT \;</math>.''' | ||
Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. | Доказательство. Если удалить любое ребро гамильтонова обхода G, получим остовное дерево G. | ||
Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения. | '''Теорема 2. Алгоритм 1 всегда возвращает гамильтонов обход, вес которого не более чем вдвое превышает вес оптимального обхода. Он имеет полиномиальное время выполнения.''' | ||
Доказательство. Согласно лемме 1, w(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>. Это доказывает утверждение по поводу эффективности аппроксимации. | ||
Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. | Время выполнения определяется главным образом временем вычисления минимального остовного дерева – которое, очевидно, является полиномиальным. | ||
