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

Содержание

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

Слайд 1РЕШЕНИЕ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ ТЕОРИИ ГРАФОВ ПОЛНЫМ ПЕРЕБОРОМ
ЛЕКЦИЯ 6

Слайд 2Содержание
Примеры решаемых полным перебором задач
Алгоритм полного перебора и его компоненты
Примеры применения

полного перебора
Решить самостоятельно
Контрольные вопросы


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

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

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

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

и q-ю вершины .




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

Оптимальное
G(X,U) решение решение

3

4

2

5

1

1

4

3

1

5

4

3

4


1 7 6 3



5 2

7 6

4


3



2

S = 28 S = 13 S = 9

Слайд 7Важный частный случай обобщенной задачи Прима
Содержательная постановка задачи поиска кратчайшего маршрута:

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

Слайд 8ПРИМЕР задачи поиска кратчайшего маршрута
Исходный граф Допустимое Оптимальное

G(X,U) решение решение

3

4

2

5

1

1

3

1

5

3

4


1 7 6 3



5 2

7



1



5







S = 28 S = 7 S = 6

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

и q-ю вершины .




Слайд 10Поиск цикла минимальной длины
Содержательная постановка задачи.
На множестве циклов A(G),

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

Слайд 11Пример задачи поиска минимального цикла
Исходный граф Допустимое Оптимальное

G(X,U) решение решение

3

4

2

5

1

1

4

3

1

5

4

3

4


1 17 11 3



5 2

4




17 11

4


1 3



5 2

S = 43 S = 32 S = 15

2

Слайд 12Алгоритм полного перебора и его компоненты

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



Ввод данных

Все решения просмотрены

Печать результатов

Выбор ранее не просмотренного решения


R0=П.З.

Вычисление R1

R0 = R1

1

2

3

4

5

6

7

8

Да




Нет

Да



Нет

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


i=n,1,-1



Получен новый вектор Х

Конец алгоритма

да

нет

i

Слайд 15Примеры применения полного перебора

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

3

5 2 7


4


Базовая вершина

Самостоятельно просмотреть следующие 10 планов.

i = 1, 2, 3…, 32.

Слайд 17Пример 2: задача Прима
Граф G(X,U):
1
4
2
3

3

1 2 7


4

Самостоятельно просмотреть следующие 10 планов.

i = 1, 2, 3…, 32.

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

3

1 5 2 7


4

Самостоятельно просмотреть следующие 10 планов.

i = 1, 2, 3…, 64.
При i=8 найден цикл, длина которого равна 12.

Слайд 19Пример 4: поиск кратчайшего маршрута из h-й вершины в g-ю
Граф

G(X,U):

1

4

2

3

4

1 9 2 3


8

Самостоятельно просмотреть следующие 10 планов.

i = 1, 2, 3…, 64.
Поиск кратчайшего маршрута из 1-й вершины в 4-ю.

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

(красным цветом выделены вершины X’):

1

5

4

2

3

7 9
3

4 1

2 6
3

Слайд 21Контрольные вопросы
Какие задачи дискретной оптимизации на графах можно решить полным перебором?
Достоинства

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

Слайд 22Индивидуальные задания
На заданном взвешенном неориентированном
графе G(X,U) определить перебором (12 итераций):
1.

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

Слайд 23Величины i, j, k

Слайд 24Матрицы смежности вершин
№ 1

№ 2

№ 3 № 4

Слайд 25Матрицы смежности вершин
№ 5

№ 6

№ 7 № 8

Слайд 26Матрицы смежности вершин
№ 9

№ 10

№ 11 № 12

Слайд 27Матрицы смежности вершин
№ 13

№ 14

№ 15 № 16

Слайд 28Матрицы смежности вершин
№ 17

№ 18

№ 19 № 20

Слайд 29Матрицы смежности вершин
№ 21

№ 22

№ 23 № 24

Похожие презентации

Площадь треугольника 302
Решение задач на применение аксиом стереометрии. (10 класс) 942
Решение экономических задач в рамках ЕГЭ 462
Классификация игр 255
Решение занимательных задач по математике 440
Преобразования графиков функций 372

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика