Построение и анализ алгоритмов. Алгоритмы на графах. МОД в задаче коммивояжёра. (Лекция 6.2) презентация

Содержание

Слайд 2

01.03.2015 МОД в задаче коммивояжёра МОД как приближение в задаче

01.03.2015

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

МОД как приближение в задаче коммивояжёра

На лекции 2

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

01.03.2015 МОД в задаче коммивояжёра Более точная терминология Лучше (более

01.03.2015

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

Более точная терминология

Лучше (более точно) называть это задачей

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

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

Слайд 4

01.03.2015 МОД в задаче коммивояжёра Оценка степени приближения алгоритмов АБС

01.03.2015

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

Оценка степени приближения алгоритмов АБС и АВБГ в

евклидовом случае

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

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

Слайд 5

01.03.2015 МОД в задаче коммивояжёра Новое: Приближённый алгоритм двойного обхода

01.03.2015

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

Новое: Приближённый алгоритм двойного обхода МОД при решении ЗК

Для

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

01.03.2015 МОД в задаче коммивояжёра Пример Σ= 4 + 6

01.03.2015

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

Пример

Σ= 4 + 6 + 6 +

4 + 18 + 5 = 43

Граф

Граф и МОД

МОД

Слайд 7

01.03.2015 МОД в задаче коммивояжёра Σ= 2 + 4 +

01.03.2015

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

Σ= 2 + 4 + 10 + 6

+ 4 + 18 = 44

5

18

Σ= 4 + 6 + 6 + 4 + 18 + 5 = 43

5

10

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

10

Слайд 8

01.03.2015 МОД в задаче коммивояжёра Оценка приближения алгоритма двойного обхода

01.03.2015

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

Оценка приближения алгоритма двойного обхода МОД (АДО МОД)

Пусть


On – оптимальный маршрут, ⏐On⏐– его длина (стоимость);
OДn – остовное дерево, ⏐OДn⏐ – его длина (стоимость);
МOДn – минимальное остовное дерево, ⏐МOДn⏐ – его стоимость;
Мn – маршрут АДО МОД, ⏐Мn⏐ – его стоимость.
Оценка:
Слайд 9

01.03.2015 МОД в задаче коммивояжёра Доказательство оценки Пусть есть оптимальный

01.03.2015

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

Доказательство оценки

Пусть есть оптимальный маршрут (цикл) On .
Удалим

одно из рёбер этого цикла – получим ОДn .
При этом ⎜On ⎜≥ ⎜OДn ⎜≥ ⎜МOДn ⎜.
В силу неравенства треугольника и смысла АДО МОД имеем 2 ⎜МOДn ⎜≥ ⎜Мn ⎜.
Из неравенств 2 ⎜On ⎜≥ 2 ⎜МOДn ⎜ и 2 ⎜МOДn ⎜≥ ⎜Мn ⎜ следует, что 2 ⎜On ⎜≥ ⎜Мn ⎜, т.е.
Слайд 10

01.03.2015 МОД в задаче коммивояжёра Другие примеры АДО МОД Граф (вершины) МОД графа

01.03.2015

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

Другие примеры АДО МОД

Граф (вершины)

МОД графа

Слайд 11

01.03.2015 МОД в задаче коммивояжёра Пример (продолжение) МОД графа Двойной обход МОД графа

01.03.2015

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

Пример (продолжение)

МОД графа

Двойной обход МОД графа

Слайд 12

01.03.2015 МОД в задаче коммивояжёра Маршрут в ЗК. Приближение АДО

01.03.2015

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

Маршрут в ЗК.
Приближение АДО МОД.
Стоимость = 19.074

Пример (продолжение)

Двойной

обход МОД графа
Слайд 13

01.03.2015 МОД в задаче коммивояжёра Оптимальный маршрут. Стоимость = 14.715

01.03.2015

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

Оптимальный маршрут.
Стоимость = 14.715
Меньше, чем АДО МОД, на

≈23%.

Если начать АДО МОД с вершины 7, то можно получить …

Имя файла: Построение-и-анализ-алгоритмов.-Алгоритмы-на-графах.-МОД-в-задаче-коммивояжёра.-(Лекция-6.2).pptx
Количество просмотров: 100
Количество скачиваний: 0