🗊Презентация Обобщенные задачи коммивояжера и планарные графы

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

Содержание ▲

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

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

Слайд 1


ОБОБЩЕННЫЕ ЗАДАЧИ КОММИВОЯЖЕРА и планарные графы Лекция 15
Описание слайда:
ОБОБЩЕННЫЕ ЗАДАЧИ КОММИВОЯЖЕРА и планарные графы Лекция 15

Слайд 2


СОДЕРЖАНИЕ Обобщенные задачи коммивояжера и их решение перебором. Связь обобщенной задачи коммивояжера и задачи о максимальной циркуляции.
Описание слайда:
СОДЕРЖАНИЕ Обобщенные задачи коммивояжера и их решение перебором. Связь обобщенной задачи коммивояжера и задачи о максимальной циркуляции.

Слайд 3


ЧАСТЬ 1
Описание слайда:
ЧАСТЬ 1

Слайд 4


Содержательные постановки обобщенных задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать заданное подмножество городов, затратив минимум средств на путешествие либо минимум средств на максимальный переход. 2. Замкнутая постановка задачи: коммивояжер должен объехать заданное подмножество городов вернуться в город из которого стартовал, затратив минимум средств на путешествие либо минимум средств на максимальный переход.
Описание слайда:
Содержательные постановки обобщенных задач коммивояжера 1. Разомкнутая постановка задачи: коммивояжер должен объехать заданное подмножество городов, затратив минимум средств на путешествие либо минимум средств на максимальный переход. 2. Замкнутая постановка задачи: коммивояжер должен объехать заданное подмножество городов вернуться в город из которого стартовал, затратив минимум средств на путешествие либо минимум средств на максимальный переход.

Слайд 5


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

Слайд 6


Графовая интерпретация «классической» замкнутой задачи коммивояжера
Описание слайда:
Графовая интерпретация «классической» замкнутой задачи коммивояжера

Слайд 7


Подмножество «обязательных» вершин : {1, 2, 4}. Подмножество «обязательных» вершин : {1, 2, 4}.
Описание слайда:
Подмножество «обязательных» вершин : {1, 2, 4}. Подмножество «обязательных» вершин : {1, 2, 4}.

Слайд 8


Обозначения и определения
Описание слайда:
Обозначения и определения

Слайд 9


Формальная постановка «классической» аддитивной замкнутой задачи коммивояжера
Описание слайда:
Формальная постановка «классической» аддитивной замкнутой задачи коммивояжера

Слайд 10


Формальная постановка обобщенной аддитивной замкнутой задачи коммивояжера
Описание слайда:
Формальная постановка обобщенной аддитивной замкнутой задачи коммивояжера

Слайд 11


Решение обобщенной замкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2, 3.)
Описание слайда:
Решение обобщенной замкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2, 3.)

Слайд 12


САМОСТОЯТЕЛЬНО
Описание слайда:
САМОСТОЯТЕЛЬНО

Слайд 13


Графовая интерпретация «классической» разомкнутой задачи коммивояжера
Описание слайда:
Графовая интерпретация «классической» разомкнутой задачи коммивояжера

Слайд 14


Формальная постановка «классической» аддитивной разомкнутой задачи коммивояжера
Описание слайда:
Формальная постановка «классической» аддитивной разомкнутой задачи коммивояжера

Слайд 15


Подмножество «обязательных» вершин : {1, 2, 4}, стартовая вершина – «1», терминальная – «4». Подмножество «обязательных» вершин : {1, 2, 4}, стартовая вершина – «1», терминальная – «4».
Описание слайда:
Подмножество «обязательных» вершин : {1, 2, 4}, стартовая вершина – «1», терминальная – «4». Подмножество «обязательных» вершин : {1, 2, 4}, стартовая вершина – «1», терминальная – «4».

Слайд 16


Формальная постановка «обобщенной» аддитивной разомкнутой задачи коммивояжера
Описание слайда:
Формальная постановка «обобщенной» аддитивной разомкнутой задачи коммивояжера

Слайд 17


Решение обобщенной разомкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2, 3; стартовая – 1, терминальная - 3)
Описание слайда:
Решение обобщенной разомкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2, 3; стартовая – 1, терминальная - 3)

Слайд 18


Самостоятельно Решить перебором разомкнутую обобщенную задачу коммивояжера на графе G(X,U) при условии, что : стартовой вершиной является первая, терминальной – третья, обязательными вершинами: 1, 2, 3.
Описание слайда:
Самостоятельно Решить перебором разомкнутую обобщенную задачу коммивояжера на графе G(X,U) при условии, что : стартовой вершиной является первая, терминальной – третья, обязательными вершинами: 1, 2, 3.

Слайд 19


ЧАСТЬ 2 Связь задачи на разрыв контуров в сильносвязном орграфе и обобщенной задачи коммивояжера
Описание слайда:
ЧАСТЬ 2 Связь задачи на разрыв контуров в сильносвязном орграфе и обобщенной задачи коммивояжера

Слайд 20


Алгоритм 1 Шаг 1. На сильносвязном планарном взвешенном орграфе G(X,U) определить величину минимального разреза R или максимальной циркуляции S. Шаг 2. Построить орграф G’(X’,U’), двойственный графу G(X,U). Шаг 3. Модифицировать G’(X’,U’), добавив к каждой дуге множества U’ параллельную и встречно ориентированную дугу с нулевым весом. Полученный орграф обозначить G”(X”,U”). Шаг 4. На G”(X”,U”) решить обобщенную замкнутую задачу коммивояжера при условии, что множество обязательных вершин равно Х”. Длину пути коммивояжера обозначить R1. Шаг 5. Сравнить величины R, S, и R1.
Описание слайда:
Алгоритм 1 Шаг 1. На сильносвязном планарном взвешенном орграфе G(X,U) определить величину минимального разреза R или максимальной циркуляции S. Шаг 2. Построить орграф G’(X’,U’), двойственный графу G(X,U). Шаг 3. Модифицировать G’(X’,U’), добавив к каждой дуге множества U’ параллельную и встречно ориентированную дугу с нулевым весом. Полученный орграф обозначить G”(X”,U”). Шаг 4. На G”(X”,U”) решить обобщенную замкнутую задачу коммивояжера при условии, что множество обязательных вершин равно Х”. Длину пути коммивояжера обозначить R1. Шаг 5. Сравнить величины R, S, и R1.

Слайд 21


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

Слайд 22


ПРИМЕР 1 ШАГИ 2 - 4
Описание слайда:
ПРИМЕР 1 ШАГИ 2 - 4

Слайд 23


САМОСТОЯТЕЛЬНО
Описание слайда:
САМОСТОЯТЕЛЬНО

Скачать

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