Минимальное остовное дерево (МОД), как приближение в задаче коммивояжера

графах
Тема лекции:
Часть 1.
Минимальное остовное дерево (МОД), как приближение

в задаче коммивояжера ё

2 рассматривались приближенные алгоритмы решения задачи коммивояжера (ЗК):
АБС

– алгоритм ближайшего соседа
АВБГ – алгоритм включения ближайшего города

Если рассматривается евклидов (частный) случай ЗК, то существуют оценки отклонения стоимости приближенного решения от стоимости точного решения.
Евклидова ЗК:
Матрица стоимостей {Cij}:
(а) симметрична
(б) удовлетворяет неравенству треугольника
Cij ≤ Cik + Ckj , ∀i, j, k

задачей коммивояжера с неравенством треугольника (ЗКНТ)
На плоскости при использовании евклидова

расстояния неравенство треугольника выполняется (но есть и другие случаи с НТ)

Если стоимости вычисляются как евклидово расстояние, то это и есть евклидова задача коммивояжера (ЕЗК).
Т.о. оценки верны в случае ЗКНТ, и в т.ч. в евклидовом случае.

АВБГ в евклидовом случае
Nn – маршрут АБС, ⏐Nn⏐ – его

длина (стоимость).
In – маршрут АВБГ, ⏐In⏐ – его длина (стоимость).
On – оптимальный маршрут, ⏐On⏐ – его длина (стоимость).

Было ранее без доказательства!

ЗК
Для заданного графа ЗКНТ построить МОД
Начиная с любой вершины обойти

по ребрам МОД все вершины, «спрямляя пути» при возвратах к уже посещенным вершинам, и вернуться в стартовую вершину

Другие формулировки п.2:
2’) Сделать двойной обход МОД. В списке пройденных вершин вычеркнуть повторения (оставить первые вхождения).
2”) Обойти МОД в прямом порядке, фиксируя первые посещения вершин.

+ 4 + 18 + 5 = 43
Граф
Граф и МОД
МОД

6 + 4 + 18 = 44
5
18
Σ= 4 + 6

+ 6 + 4 + 18 + 5 = 43

5

10

Σ= 2 + 6 + 6 + 4 + 10 + 5 = 33

10

МОД)
Пусть
On – оптимальный маршрут, ⏐On⏐– его длина (стоимость);
OДn –

остовное дерево, ⏐OДn⏐ – его длина (стоимость);
МOДn – минимальное остовное дерево, ⏐МOДn⏐ – его стоимость;
Мn – маршрут АДО МОД, ⏐Мn⏐ – его стоимость.

Оценка:

.
Удалим одно из ребер этого цикла – получим ОДn .
При

этом ⎜On ⎜≥ ⎜OДn ⎜≥ ⎜МOДn ⎜.
В силу неравенства треугольника и смысла АДО МОД имеем 2 ⎜МOДn ⎜≥ ⎜Мn ⎜.
Из неравенств 2 ⎜On ⎜≥ 2 ⎜МOДn ⎜ и 2 ⎜МOДn ⎜≥ ⎜Мn ⎜ следует, что 2 ⎜On ⎜≥ ⎜Мn ⎜, т.е.

(продолжение)
Двойной обход МОД графа

на ≈23%.
Если начать АДО МОД с вершины 7, то можно

получить …

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ