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

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

Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ, слайд №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 Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ

Слайд 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

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

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