45. Задача коммивояжера для полного графа с неравенством треугольника. Основные шаги алгоритма решения задачи. Утверждение 5.1 максимально погрешности алгоритма.

Пусть функция стоимости ребер в положительном графе удовлетворяет: в графе G=(V,X) для любых 3-х вершин u, v, w принадлежащие V выполняющих условие С(u, w) ≤ C(u, v) + C(v, w) (*) В частности это неравенство справедливо если вершина является точками, а стоимости = расстоянию между вершинами.

Можно показать, что и в этом случае задача остается NP – полной => поиск приближенного алгоритма актуален.

Мы рассмотрим приближенный алгоритм, основанный на использовании остовного дерева минимальной стоимости.

Шаги алгоритма:

1. Строим ОДМС, например с помощью алгоритма Прима

2. Выберем произвольную вершину в качестве корневой

3. Совершим полный обход всех вершин дерева. Такой обход начинается с корня и идет по всем ребрам «левой» ветви до листа, после возвращается по этой же ветви до вершины у которой имеется более одного сына, от этой вершины продолжает движение по ребру ведущему ко 2-мы сыну и т.д. На всем пути переписываем все встречающиеся вершины, в том числе и повторяющиеся. (см. рис. 5.4)

4. Проходя получившийся список вершин вычеркнуть повторяющиеся вершины, кроме последнего повтора корня, измененный список и будет последовательностью вершин гамильтонова цикла, его примем в качестве приближенного задачи коммивояжера.

Полный обход на рис. 5.4 даст такую последовательность вершин:

v_1, v₂, v₃, v₈, v₂, v₁, v₄, v₅, v₆, v₅, v₇, v₅, v₇, v₅, v₄, v₁ (**)

Вычеркнув повторы, получим:

v_1, v₂,v₃, v₈, v₄, v₅, v₆, v₇, v₁

Соответствующий гамильтонов цикл показан на рис. 5.5. Его стоимость = 19,74

Для сравнения на рис. 5.6 показан гамильтонов цикл являющийся точным решением задачи 14,75.

Данный алгоритм не дает однозначного решения, т.к во-первых ОДМС может быть не единственным, во-вторых порядок нахождения списка вершин может быть разным, например оптимальный гамильтонов цикл на рис. 5.6 можно было бы получить если последовательность (**) пройти в 2 этапа. Сначала слева на право до v₃ включительно, а потом оставшуюся часть справа на лево.

Утверждение 5.1:

Алгоритм поиска приближенного решения в полном графе с неравенством треугольника. Решение задается с ошибкой не более чем в 2 раза по стоимости найденного гамильтонова цикла.

Доказательство:

Пусть Н* - минимальный гамильтонов цикл, Н – гамильтонов цикл, найденный при помощи приближенного алгоритма. Необходимо доказать, что стоимость Н не превышает 2-х стоимостей Н* (С(Н) ≤ 2С(Н*))

Если удалить из Н* любое ребро, то мы получим остовное дерево (не обязательно минимальное), стоимость этого дерева не будет превосходить С(Н*) тем более это будет верно для любого ОДМС, т.е для любого ОДМС справедливо:

С(Т) ≤ С(Н*)

Пусть мы совершили полный обход W дерева Т, в этом случае каждое ребро будет пройдено дважды, т.е С(W) ≤ 2C(W)

В следствии неравенства треугольника при удалении W любая вершина стоимость может только уменьшаться => С(Н) ≤ С(W) => C(H) ≤ 2C(H*)

Ч.Т.Д.