Презентация Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ абсолютно бесплатно. Урок-презентация на эту тему содержит всего 29 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:29 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:218.65 kB
- Просмотров:81
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Лекция 14
Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ
№2 слайд
Содержание слайда: СОДЕРЖАНИЕ
1. Постановки задач коммивояжера.
2. Решение замкнутой задачи коммивояжера методами типа ветвей и границ.
3. Решение разомкнутой задачи коммивояжера методами типа ветвей и границ.
№3 слайд
Содержание слайда: Часть 1
Постановки задач коммивояжера
№4 слайд
Содержание слайда: Содержательные постановки «классических» задач коммивояжера
1. Разомкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу, и затратив: - минимум средств на путешествие либо
- минимум средств на максимальный переход.
2. Замкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу и вернуться в город из которого стартовал, затратив: -минимум средств на путешествие (аддитивная задача коммивояжера)
- минимум средств на максимальный переход (минимаксная задача коммивояжера).
№5 слайд
Содержание слайда: Графовая интерпретация замкнутой задачи коммивояжера
№6 слайд
Содержание слайда: Обозначения и определения
№7 слайд
Содержание слайда: Формальная постановка аддитивной замкнутой задачи коммивояжера
№8 слайд
Содержание слайда: Формальная постановка аддитивной разомкнутой задачи коммивояжера
№9 слайд
Содержание слайда: Формальная постановка минимаксной разомкнутой задачи коммивояжера
№10 слайд
Содержание слайда: Переменные для формальной постановки разомкнутой задачи коммивояжера как функции от перестановки
Пусть π = {i1, i2, …., in} – некоторая перестановка вершин графа G(X,U), |X| = n, где ij – номер вершины, стоящей на j-м месте в перестановке π.
Пусть переменная y(ij,i(j+1)) определена следующим образом:
r(ij,i(j+1)), если дуга (ij. i(j+1)) принадлежит
множеству U;
y(ij,i(j+1)) =
∞ в противном случае.
№11 слайд
Содержание слайда: формальные постановки задач коммивояжера как функции от перестановки
Формальная постановка разомкнутой задачи коммивояжера:
Формальная постановка замкнутой задачи коммивояжера:
№12 слайд
Содержание слайда: Часть 2.
Методы типа ветвей и границ, осуществляющие поиск решения замкнутой задачи коммивояжера на сильносвязном взвешенном ориентированном графе.
№13 слайд
Содержание слайда: ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ
Оценкой является суммарный вес удаленных дуг.
Пусть I – подмножество удаленных дуг.
Тогда оценка Δ равна:
№14 слайд
Содержание слайда: Простой способ вычисления оценки и фронтальный спуск
Граф G(X,U) Дерево поиска
№15 слайд
Содержание слайда: Решить замкнутую задачу коммивояжера самостоятельно, пользуясь МВГ, реализующим фронтальный спуск по дереву ветвлений
№16 слайд
Содержание слайда: УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ
Оценкой является сумма, включающая суммарный вес удаленных дуг и суммарный вес дуг с минимальным весом, заходящих в вершины, соответствующие городам, в которые коммивояжер еще не въезжал.
Пусть I – подмножество удаленных дуг, а J – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал.
Тогда оценка Δ равна:
№17 слайд
Содержание слайда: ПРИМЕР ВЫЧИСЛЕНИЯ УТОЧНЕННОЙ ОЦЕНКИ
Пусть I = {(3,1)} – подмножество удаленных дуг, а J = {2,3,4} – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал.
Тогда оценка Δ равна: Δ = 4 + {1+3+5} = 13.
№18 слайд
Содержание слайда: Уточненный способ вычисления оценки и фронтальный спуск
Граф G(X,U) Дерево поиска
№19 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Решить замкнутую задачу коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U), пользуясь простым и усложненным методами вычисления оценки:
№20 слайд
Содержание слайда: Простой способ вычисления оценки и поиск с возвратом
Граф G(X,U) Дерево поиска
№21 слайд
Содержание слайда: Уточненный способ вычисления оценки и поиск с возвратом
Граф G(X,U) Дерево поиска
№22 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Определить решение замкнутой задачи коммивояжера, осуществляя поиск с возвратом по дереву ветвлений на графе G(X,U), и пользуясь простым и усложненным методами вычисления оценки.
№23 слайд
Содержание слайда: ЧАСТЬ 3
РЕШЕНИЕ РАЗОМКНУТОЙ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДАМИ ТИПА ВЕТВЕЙ И ГРАНИЦ
№24 слайд
Содержание слайда: АЛГОРИТМ ПЕРЕХОДА ОТ РАЗОМКНУТОЙ «КЛАССИЧЕСКОЙ» ЗАДАЧИ КОММИВОЯЖЕРА К ЗАМКНУТОЙ
Пусть задан орграф G’(X’,U’) на котором следует решить разомкнутую задачу коммивояжера при условии, что выделена стартовая вершина xs и терминальная вершина xt .
Преобразуем G’(X’,U,) в орграф G”(X’,U”) добавлением дуги (t,s), обладающей нулевым весом.
На орграфе G”(X’,U”) ищется оптимальное решение замкнутой задачи коммивояжера.
Отбрасывая в полученном на предыдущем шаге подмножестве дуг, дугу (t,s), получим решение разомкнутой задачи коммивояжера.
№25 слайд
Содержание слайда: ПРИМЕР
№26 слайд
Содержание слайда: Эквивалентные преобразования графа, на котором решается разомкнутая задача коммивояжера
1. Если на исходном графе существует дуга, ведущая из стартовой вершины в терминальную, то она может быть отброшена.
Если на исходном графе существуют дуги, ведущие в стартовую вершину, то они могут быть отброшены.
Если на исходном графе существуют дуги, ведущие из терминальной вершины, то они могут быть отброшены.
№27 слайд
Содержание слайда: ПРИМЕР ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАФА
№28 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Определить решение методом типа ветвей и границ разомкнутой задачи коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U) и поиском с возвратом, пользуясь: а) переходом к замкнутой задаче;
б) простым и усложненным методами вычисления оценки. G(X,U)
№29 слайд
Содержание слайда: САМОСТОЯТЕЛЬНО
Предложите свой способ решения разомкнутой задачи коммивояжера, опирающийся на метод типа ветвей и границ и не требующий перехода к замкнутой задаче.
Скачать все slide презентации Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ одним архивом:
