🗊Презентация Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №1Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №2Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №3Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №4Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №5Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №6Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №7Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №8Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №9Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №10Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №11Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №12Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №13Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №14Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №15Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №16Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №17Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №18Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №19Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №20Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №21Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №22Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №23Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №24Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №25Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №26Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №27Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №28Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №29
Скачать

Содержание ▲

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

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

Слайд 1


Лекция 14 Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ
Описание слайда:
Лекция 14 Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ

Слайд 2


СОДЕРЖАНИЕ 1. Постановки задач коммивояжера. 2. Решение замкнутой задачи коммивояжера методами типа ветвей и границ. 3. Решение разомкнутой задачи коммивояжера методами типа ветвей и границ.
Описание слайда:
СОДЕРЖАНИЕ 1. Постановки задач коммивояжера. 2. Решение замкнутой задачи коммивояжера методами типа ветвей и границ. 3. Решение разомкнутой задачи коммивояжера методами типа ветвей и границ.

Слайд 3


Часть 1 Постановки задач коммивояжера
Описание слайда:
Часть 1 Постановки задач коммивояжера

Слайд 4


Содержательные постановки «классических» задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу, и затратив: - минимум средств на путешествие либо - минимум средств на максимальный переход. 2. Замкнутая постановка задачи: коммивояжер должен объехать все n городов, побывав в каждом по одному разу и вернуться в город из которого стартовал, затратив: -минимум средств на путешествие (аддитивная задача коммивояжера) - минимум средств на максимальный переход (минимаксная задача коммивояжера).
Описание слайда:
Содержательные постановки «классических» задач коммивояжера 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)) = ∞ в противном случае.
Описание слайда:
Переменные для формальной постановки разомкнутой задачи коммивояжера как функции от перестановки Пусть π = {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. Методы типа ветвей и границ, осуществляющие поиск решения замкнутой задачи коммивояжера на сильносвязном взвешенном ориентированном графе.
Описание слайда:
Часть 2. Методы типа ветвей и границ, осуществляющие поиск решения замкнутой задачи коммивояжера на сильносвязном взвешенном ориентированном графе.

Слайд 13


ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ Оценкой является суммарный вес удаленных дуг. Пусть I – подмножество удаленных дуг. Тогда оценка Δ равна:
Описание слайда:
ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ Оценкой является суммарный вес удаленных дуг. Пусть I – подмножество удаленных дуг. Тогда оценка Δ равна:

Слайд 14


Простой способ вычисления оценки и фронтальный спуск Граф G(X,U) Дерево поиска
Описание слайда:
Простой способ вычисления оценки и фронтальный спуск Граф G(X,U) Дерево поиска

Слайд 15


Решить замкнутую задачу коммивояжера самостоятельно, пользуясь МВГ, реализующим фронтальный спуск по дереву ветвлений
Описание слайда:
Решить замкнутую задачу коммивояжера самостоятельно, пользуясь МВГ, реализующим фронтальный спуск по дереву ветвлений

Слайд 16


УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ Оценкой является сумма, включающая суммарный вес удаленных дуг и суммарный вес дуг с минимальным весом, заходящих в вершины, соответствующие городам, в которые коммивояжер еще не въезжал. Пусть I – подмножество удаленных дуг, а J – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал. Тогда оценка Δ равна:
Описание слайда:
УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ Оценкой является сумма, включающая суммарный вес удаленных дуг и суммарный вес дуг с минимальным весом, заходящих в вершины, соответствующие городам, в которые коммивояжер еще не въезжал. Пусть I – подмножество удаленных дуг, а J – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал. Тогда оценка Δ равна:

Слайд 17


ПРИМЕР ВЫЧИСЛЕНИЯ УТОЧНЕННОЙ ОЦЕНКИ Пусть I = {(3,1)} – подмножество удаленных дуг, а J = {2,3,4} – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал. Тогда оценка Δ равна: Δ = 4 + {1+3+5} = 13.
Описание слайда:
ПРИМЕР ВЫЧИСЛЕНИЯ УТОЧНЕННОЙ ОЦЕНКИ Пусть I = {(3,1)} – подмножество удаленных дуг, а J = {2,3,4} – подмножество вершин, соответствующих городам, в которые коммивояжер еще не въезжал. Тогда оценка Δ равна: Δ = 4 + {1+3+5} = 13.

Слайд 18


Уточненный способ вычисления оценки и фронтальный спуск Граф G(X,U) Дерево поиска
Описание слайда:
Уточненный способ вычисления оценки и фронтальный спуск Граф G(X,U) Дерево поиска

Слайд 19


САМОСТОЯТЕЛЬНО Решить замкнутую задачу коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U), пользуясь простым и усложненным методами вычисления оценки:
Описание слайда:
САМОСТОЯТЕЛЬНО Решить замкнутую задачу коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U), пользуясь простым и усложненным методами вычисления оценки:

Слайд 20


Простой способ вычисления оценки и поиск с возвратом Граф G(X,U) Дерево поиска
Описание слайда:
Простой способ вычисления оценки и поиск с возвратом Граф G(X,U) Дерево поиска

Слайд 21


Уточненный способ вычисления оценки и поиск с возвратом Граф G(X,U) Дерево поиска
Описание слайда:
Уточненный способ вычисления оценки и поиск с возвратом Граф G(X,U) Дерево поиска

Слайд 22


САМОСТОЯТЕЛЬНО Определить решение замкнутой задачи коммивояжера, осуществляя поиск с возвратом по дереву ветвлений на графе G(X,U), и пользуясь простым и усложненным методами вычисления оценки.
Описание слайда:
САМОСТОЯТЕЛЬНО Определить решение замкнутой задачи коммивояжера, осуществляя поиск с возвратом по дереву ветвлений на графе G(X,U), и пользуясь простым и усложненным методами вычисления оценки.

Слайд 23


ЧАСТЬ 3 РЕШЕНИЕ РАЗОМКНУТОЙ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДАМИ ТИПА ВЕТВЕЙ И ГРАНИЦ
Описание слайда:
ЧАСТЬ 3 РЕШЕНИЕ РАЗОМКНУТОЙ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДАМИ ТИПА ВЕТВЕЙ И ГРАНИЦ

Слайд 24


АЛГОРИТМ ПЕРЕХОДА ОТ РАЗОМКНУТОЙ «КЛАССИЧЕСКОЙ» ЗАДАЧИ КОММИВОЯЖЕРА К ЗАМКНУТОЙ Пусть задан орграф G’(X’,U’) на котором следует решить разомкнутую задачу коммивояжера при условии, что выделена стартовая вершина xs и терминальная вершина xt . Преобразуем G’(X’,U,) в орграф G”(X’,U”) добавлением дуги (t,s), обладающей нулевым весом. На орграфе G”(X’,U”) ищется оптимальное решение замкнутой задачи коммивояжера. Отбрасывая в полученном на предыдущем шаге подмножестве дуг, дугу (t,s), получим решение разомкнутой задачи коммивояжера.
Описание слайда:
АЛГОРИТМ ПЕРЕХОДА ОТ РАЗОМКНУТОЙ «КЛАССИЧЕСКОЙ» ЗАДАЧИ КОММИВОЯЖЕРА К ЗАМКНУТОЙ Пусть задан орграф G’(X’,U’) на котором следует решить разомкнутую задачу коммивояжера при условии, что выделена стартовая вершина xs и терминальная вершина xt . Преобразуем G’(X’,U,) в орграф G”(X’,U”) добавлением дуги (t,s), обладающей нулевым весом. На орграфе G”(X’,U”) ищется оптимальное решение замкнутой задачи коммивояжера. Отбрасывая в полученном на предыдущем шаге подмножестве дуг, дугу (t,s), получим решение разомкнутой задачи коммивояжера.

Слайд 25


ПРИМЕР
Описание слайда:
ПРИМЕР

Слайд 26


Эквивалентные преобразования графа, на котором решается разомкнутая задача коммивояжера 1. Если на исходном графе существует дуга, ведущая из стартовой вершины в терминальную, то она может быть отброшена. Если на исходном графе существуют дуги, ведущие в стартовую вершину, то они могут быть отброшены. Если на исходном графе существуют дуги, ведущие из терминальной вершины, то они могут быть отброшены.
Описание слайда:
Эквивалентные преобразования графа, на котором решается разомкнутая задача коммивояжера 1. Если на исходном графе существует дуга, ведущая из стартовой вершины в терминальную, то она может быть отброшена. Если на исходном графе существуют дуги, ведущие в стартовую вершину, то они могут быть отброшены. Если на исходном графе существуют дуги, ведущие из терминальной вершины, то они могут быть отброшены.

Слайд 27


ПРИМЕР ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАФА
Описание слайда:
ПРИМЕР ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАФА

Слайд 28


САМОСТОЯТЕЛЬНО Определить решение методом типа ветвей и границ разомкнутой задачи коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U) и поиском с возвратом, пользуясь: а) переходом к замкнутой задаче; б) простым и усложненным методами вычисления оценки. G(X,U)
Описание слайда:
САМОСТОЯТЕЛЬНО Определить решение методом типа ветвей и границ разомкнутой задачи коммивояжера фронтальным спуском по дереву ветвлений на графе G(X,U) и поиском с возвратом, пользуясь: а) переходом к замкнутой задаче; б) простым и усложненным методами вычисления оценки. G(X,U)

Слайд 29


САМОСТОЯТЕЛЬНО Предложите свой способ решения разомкнутой задачи коммивояжера, опирающийся на метод типа ветвей и границ и не требующий перехода к замкнутой задаче.
Описание слайда:
САМОСТОЯТЕЛЬНО Предложите свой способ решения разомкнутой задачи коммивояжера, опирающийся на метод типа ветвей и границ и не требующий перехода к замкнутой задаче.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию