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

Презентация на тему Презентация на тему Построение и анализ алгоритмов. Алгоритмы на графах. МОД в задаче коммивояжёра. (Лекция 6.2), предмет презентации: Информатика. Этот материал содержит 14 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

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

Слайд 1
Текст слайда:

01.03.2015

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

Построение и анализ алгоритмов

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


Слайд 2
Текст слайда:

01.03.2015

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

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

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

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


Слайд 3
Текст слайда:

01.03.2015

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

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

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


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


Слайд 4
Текст слайда:

01.03.2015

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

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

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

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


Слайд 5
Текст слайда:

01.03.2015

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

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

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

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


Слайд 6
Текст слайда:

01.03.2015

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

Пример

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

Граф

Граф и МОД

МОД



Слайд 7
Текст слайда:

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

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

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

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

Оценка:



Слайд 9
Текст слайда:

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

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

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

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

МОД графа


Слайд 11
Текст слайда:

01.03.2015

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

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

МОД графа

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


Слайд 12
Текст слайда:

01.03.2015

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

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

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

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


Слайд 13
Текст слайда:

01.03.2015

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

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

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


Слайд 14
Текст слайда:

01.03.2015

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

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика