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

Июль 27, 2022

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

Содержание

2. Содержание Примеры решаемых полным перебором задач Алгоритм полного перебора и его компоненты Примеры применения полного перебора
3. Примеры решаемых полным перебором задач
4. Обобщенная задача Прима Содержательная постановка задачи: на взвешенном неориентированном графе G(X,U) выделено подмножество вершин Х’ для
5. Формальная постановка задачи Обозначения: Выделенное подмножество вершин X’; d-й маршрут, соединяющий p-ю и q-ю вершины .
6. ПРИМЕР ОБОБЩЕННОЙ ЗАДАЧИ ПРИМА («ОБЯЗАТЕЛЬНЫЕ» ВЕРШИНЫ ВЫДЕЛЕНЫ КРАСНЫМ ЦВЕТОМ) Исходный граф Допустимое Оптимальное G(X,U) решение решение
7. Важный частный случай обобщенной задачи Прима Содержательная постановка задачи поиска кратчайшего маршрута: на взвешенном неориентированном графе
8. ПРИМЕР задачи поиска кратчайшего маршрута Исходный граф Допустимое Оптимальное G(X,U) решение решение 3 4 2 5
9. Формальная постановка задачи Обозначения: Выделенное подмножество вершин X’; d-й маршрут, соединяющий p-ю и q-ю вершины .
10. Поиск цикла минимальной длины Содержательная постановка задачи. На множестве циклов A(G), отвечающих взвешенному графу G(X,U), требуется
11. Пример задачи поиска минимального цикла Исходный граф Допустимое Оптимальное G(X,U) решение решение 3 4 2 5
12. Алгоритм полного перебора и его компоненты
13. АЛГОРИТМ ПОЛНОГО ПЕРЕБОРА Алгоритм решения любой экстремальной задачи на графах Ввод данных Все решения просмотрены Печать
14. Бинарный счетчик Шаг 5 предыдущего алгоритма i=n,1,-1 Получен новый вектор Х Конец алгоритма да нет i
15. Примеры применения полного перебора
16. Пример 1: задача о минимаксных маршрутах Граф G(X,U): 1 4 2 3 3 5 2 7
17. Пример 2: задача Прима Граф G(X,U): 1 4 2 3 3 1 2 7 4 Самостоятельно
18. Пример 3: поиск кратчайшего цикла Граф G(X,U): 1 4 2 3 3 1 5 2 7
19. Пример 4: поиск кратчайшего маршрута из h-й вершины в g-ю Граф G(X,U): 1 4 2 3
20. САМОСТОЯТЕЛЬНО Пользуясь полным перебором решить обобщенную задачу Прима на графе G(X,U) вида (красным цветом выделены вершины
21. Контрольные вопросы Какие задачи дискретной оптимизации на графах можно решить полным перебором? Достоинства полного перебора. Недостатки
22. Индивидуальные задания На заданном взвешенном неориентированном графе G(X,U) определить перебором (12 итераций): 1. Кратчайший маршрут между
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
30. Скачать презентацию

Слайд 2

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

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

Слайд 3

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

Слайд 4

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

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

Слайд 5

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

q-ю вершины .

Слайд 6

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

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

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) решение

решение

4
1 7 6 3
5 2

1
5

S = 28 S = 7 S = 6

Слайд 9

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

q-ю вершины .

Слайд 10

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

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

Слайд 11

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

решение

4
1 17 11 3
5 2

4
17 11

4
1 3
5 2

S = 43 S = 32 S = 15

Слайд 12

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

Слайд 13

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

данных

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

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

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

R0=П.З.

Вычисление R1

R0 = R1

Да
Нет

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

4
1 9 2 3
8

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

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

Слайд 20

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

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

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 №

Слайд 25

Матрицы смежности вершин
№ 5 № 6
№ 7 №

Слайд 26

Матрицы смежности вершин
№ 9 № 10
№ 11 №

Слайд 27

Матрицы смежности вершин
№ 13 № 14
№ 15 №

Слайд 28

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

Бинарный счетчикШаг 5 предыдущего алгоритмаi=n,1,-1Получен новый вектор ХКонец алгоритма да нетi

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

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

Пример 2: задача ПримаГраф G(X,U): 1423 3 1 2 74 Самостоятельно

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

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

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

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

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

Величины i, j, k

Матрицы смежности вершин № 1 № 2 № 3 №

Матрицы смежности вершин № 5 № 6 № 7 №

Матрицы смежности вершин № 9 № 10 № 11 №

Матрицы смежности вершин № 13 № 14 № 15 №

Матрицы смежности вершин № 17 № 18 № 19 №

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

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

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

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

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

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

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

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

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

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

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

Бинарный счетчик
Шаг 5 предыдущего алгоритма
i=n,1,-1
Получен новый вектор Х
Конец алгоритма
да
нет
i

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

Пример 2: задача Прима
Граф G(X,U):
1
4
2
3
3
1 2 7
4
Самостоятельно

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

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

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

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

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

Матрицы смежности вершин
№ 1 № 2
№ 3 №

Матрицы смежности вершин
№ 5 № 6
№ 7 №

Матрицы смежности вершин
№ 9 № 10
№ 11 №

Матрицы смежности вершин
№ 13 № 14
№ 15 №

Матрицы смежности вершин
№ 17 № 18
№ 19 №