Решение экстремальных задач теории графов перебором - презентация, доклад, проект скачать

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

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

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

ЛЕКЦИЯ 6

Слайд 2

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

Содержание Примеры решаемых полным перебором задач Алгоритм полного перебора и его компоненты Примеры применения полного перебора Решить самостоятельно Контрольные вопросы

Слайд 3

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

Примеры решаемых полным перебором задач

Слайд 4

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

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

Слайд 5

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

Формальная постановка задачи Обозначения: Выделенное подмножество вершин X’; d-й маршрут, соединяющий p-ю и q-ю вершины .

Слайд 6

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

ПРИМЕР ОБОБЩЕННОЙ ЗАДАЧИ ПРИМА («ОБЯЗАТЕЛЬНЫЕ» ВЕРШИНЫ ВЫДЕЛЕНЫ КРАСНЫМ ЦВЕТОМ) Исходный граф Допустимое Оптимальное G(X,U) решение решение

Слайд 7

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

Важный частный случай обобщенной задачи Прима Содержательная постановка задачи поиска кратчайшего маршрута: на взвешенном неориентированном графе G(X,U) выделены две вершины, р-я и q-я, для которых следует выделить подмножество ребер U’, такое, что: На графе G(X,U’) существует маршрут между этими вершинами. Суммарный вес ребер подмножества U’ минимален.

Слайд 8

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

ПРИМЕР задачи поиска кратчайшего маршрута Исходный граф Допустимое Оптимальное G(X,U) решение решение

Слайд 9

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

Слайд 10

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

Поиск цикла минимальной длины Содержательная постановка задачи. На множестве циклов A(G), отвечающих взвешенному графу G(X,U), требуется выбрать такой, суммарный вес ребер которого минимален.

Слайд 11

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

Пример задачи поиска минимального цикла Исходный граф Допустимое Оптимальное G(X,U) решение решение

Слайд 12

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

Алгоритм полного перебора и его компоненты

Слайд 13

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

АЛГОРИТМ ПОЛНОГО ПЕРЕБОРА Алгоритм решения любой экстремальной задачи на графах

Слайд 14

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

Бинарный счетчик Шаг 5 предыдущего алгоритма

Слайд 15

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

Примеры применения полного перебора

Слайд 16

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

Пример 1: задача о минимаксных маршрутах Граф G(X,U):

Слайд 17

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

Пример 2: задача Прима Граф G(X,U):

Слайд 18

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

Пример 3: поиск кратчайшего цикла Граф G(X,U):

Слайд 19

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

Пример 4: поиск кратчайшего маршрута из h-й вершины в g-ю Граф G(X,U):

Слайд 20

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

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

Слайд 21

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

Контрольные вопросы Какие задачи дискретной оптимизации на графах можно решить полным перебором? Достоинства полного перебора. Недостатки полного перебора. Какова верхняя граница объема полного перебора при решении им задачи Прима на графе G(X,U), если Х = n ?

Слайд 22

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

Индивидуальные задания На заданном взвешенном неориентированном графе G(X,U) определить перебором (12 итераций): 1. Кратчайший маршрут между i-й и j-й вершинами. 2. Минимальную базу ребер, связывающих три вершины: i, j, k. 3. Минимальный простой цикл на графе. 4. Минимаксную базу ребер, связывающих все вершины графа. 5. Минимаксный простой цикл на графе