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

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

Обобщенные задачи коммивояжера и планарные графы, слайд №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

Слайд 2

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

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

Слайд 3

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

ЧАСТЬ 1

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

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

Слайд 12

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

САМОСТОЯТЕЛЬНО

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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

Слайд 18

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

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

Слайд 19

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

ЧАСТЬ 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.