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

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Минимальное остовное дерево (МОД), как приближение в задаче коммивояжера. Доклад-сообщение содержит 14 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Построение и анализ алгоритмов Лекция 7.1 Раздел: Алгоритмы на графах Тема лекции: Часть 1. Минимальное остовное дерево (МОД), как приближение в задаче коммивояжера ё

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Оценка степени приближения алгоритмов АБС и АВБГ в евклидовом случае Nn – маршрут АБС, Nn – его длина (стоимость). In – маршрут АВБГ, In – его длина (стоимость). On – оптимальный маршрут, On – его длина (стоимость).

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Пример

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Оценка приближения алгоритма двойного обхода МОД (АДО МОД) Пусть On – оптимальный маршрут, On– его длина (стоимость); OДn – остовное дерево, OДn – его длина (стоимость); МOДn – минимальное остовное дерево, МOДn – его стоимость; Мn – маршрут АДО МОД, Мn – его стоимость. Оценка:

Слайд 9

Описание слайда:

Доказательство оценки Пусть есть оптимальный маршрут (цикл) On . Удалим одно из ребер этого цикла – получим ОДn . При этом On  OДn  МOДn . В силу неравенства треугольника и смысла АДО МОД имеем 2 МOДn  Мn . Из неравенств 2 On  2 МOДn  и 2 МOДn  Мn  следует, что 2 On  Мn , т.е.