Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

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

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

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

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

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

Содержание

СодержаниеПримеры решаемых полным перебором задачАлгоритм полного перебора и его компонентыПримеры применения полного перебораРешить самостоятельноКонтрольные вопросы
РЕШЕНИЕ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ ТЕОРИИ ГРАФОВ ПОЛНЫМ ПЕРЕБОРОМЛЕКЦИЯ 6 СодержаниеПримеры решаемых полным перебором задачАлгоритм полного перебора и его компонентыПримеры применения полного перебораРешить самостоятельноКонтрольные вопросы Примеры решаемых полным перебором задач Обобщенная задача ПримаСодержательная постановка задачи: на взвешенном неориентированном графе G(X,U) выделено подмножество Формальная постановка задачи Обозначения:Выделенное подмножество вершин X’;d-й маршрут, соединяющий p-ю и ПРИМЕР ОБОБЩЕННОЙ ЗАДАЧИ ПРИМА («ОБЯЗАТЕЛЬНЫЕ» ВЕРШИНЫ ВЫДЕЛЕНЫ КРАСНЫМ ЦВЕТОМ)Исходный граф Допустимое Оптимальное Важный частный случай обобщенной задачи ПримаСодержательная постановка задачи поиска кратчайшего маршрута: на ПРИМЕР задачи поиска кратчайшего маршрутаИсходный граф Допустимое Оптимальное G(X,U) Формальная постановка задачи Обозначения:Выделенное подмножество вершин X’;d-й маршрут, соединяющий p-ю и Поиск цикла минимальной длиныСодержательная постановка задачи. На множестве циклов A(G), отвечающих Пример задачи поиска минимального циклаИсходный граф Допустимое Оптимальное G(X,U) Алгоритм полного перебора и его компоненты АЛГОРИТМ ПОЛНОГО ПЕРЕБОРА Алгоритм решения любой экстремальной задачи на графах Ввод Бинарный счетчикШаг 5 предыдущего алгоритмаi=n,1,-1Получен новый вектор ХКонец алгоритма Примеры применения полного перебора Пример 1: задача о минимаксных маршрутахГраф G(X,U): 1423 Пример 2: задача ПримаГраф G(X,U): 1423 Пример 3: поиск кратчайшего циклаГраф G(X,U): 1423 Пример 4: поиск кратчайшего маршрута из h-й вершины в g-юГраф G(X,U): САМОСТОЯТЕЛЬНОПользуясь полным перебором решить обобщенную задачу Прима на графе G(X,U) вида (красным Контрольные вопросыКакие задачи дискретной оптимизации на графах можно решить полным перебором?Достоинства полного Индивидуальные заданияНа заданном взвешенном неориентированном графе G(X,U) определить перебором (12 итераций):1. Кратчайший Величины i, j, k Матрицы смежности вершин № 1 Матрицы смежности вершин № 5 Матрицы смежности вершин № 9 Матрицы смежности вершин № 13 Матрицы смежности вершин № 17 Матрицы смежности вершин № 21
Слайды презентации

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

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

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


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

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

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

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

графе G(X,U) выделено подмножество вершин Х’ для которого следует

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

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

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

маршрут, соединяющий 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)


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-й

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

маршрут, соединяющий p-ю и q-ю вершины

.




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

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

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

такой, суммарный вес ребер которого минимален.

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

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


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



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

Конец

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

алгоритма

да

нет

i

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

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

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

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


1
4
2
3

3

5 2 7


4


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

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

i = 1, 2, 3…, 32.

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

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


1
4
2
3

3

1 2 7


4

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

i = 1, 2, 3…, 32.

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

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


1
4
2
3

3

1 5 2 7


4

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

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

Слайд 19 Пример 4: поиск кратчайшего маршрута из h-й

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

вершины в 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) вида

графе 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) определить

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

перебором (12 итераций):
1. Кратчайший маршрут между i-й и j-й

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

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

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

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

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

№ 1

№ 2

№ 3 № 4

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

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

№ 5

№ 6

№ 7 № 8

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

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

№ 9

№ 10

№ 11 № 12

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

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

№ 13

№ 14

№ 15 № 16

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

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

№ 17

№ 18

№ 19 № 20

  • Имя файла: reshenie-ekstremalnyh-zadach-teorii-grafov-pereborom.pptx
  • Количество просмотров: 113
  • Количество скачиваний: 0
- Предыдущая Фишбоун – эффективный прием работы с текстом
Следующая - Особенности культурно-досуговой программы в учреждении дополнительного образования

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

Сечения пирамиды Сечения пирамиды 96
Округление чисел Округление чисел 139
Великие математики Великие математики 99
Синус, косинус, тангенс и котангенс Синус, косинус, тангенс и котангенс 138
Презентация по математике на темуСмешанные числа Презентация по математике на темуСмешанные числа 93
Интегрированный урок (математика + изо), 2 класс методическая разработка по математике (2 класс) Интегрированный урок (математика + изо), 2 класс методическая разработка по математике (2 класс) 133
Геометрические преобразования и паркеты Геометрические преобразования и паркеты 126
Презентация на урок математика тема: Название компонентов и результата деления Презентация на урок математика тема: Название компонентов и результата деления 109
Замечательные кривые вокруг нас Замечательные кривые вокруг нас 128
Презентация из опыта работы использование ИКТ на уроках математики Презентация из опыта работы использование ИКТ на уроках математики 125
Графический диктант: Формулы Графический диктант: Формулы 121
Презентация по математике на тему Сложение чисел на координатной прямой Презентация по математике на тему Сложение чисел на координатной прямой 94
ПОНЯТИЕ ДВИЖЕНИЯ (9 КЛАСС) ПОНЯТИЕ ДВИЖЕНИЯ (9 КЛАСС) 84
Возведение в степень произведения и степени (7 класс) Возведение в степень произведения и степени (7 класс) 113
Презентация Приемы устных вычислений 3 класс Презентация Приемы устных вычислений 3 класс 174
Метод вспомогательной окружности Метод вспомогательной окружности 124
Линейные уравнения с одной переменной Линейные уравнения с одной переменной 104
Влияет ли геометрия города на его образ? Влияет ли геометрия города на его образ? 202
Тренажёр Единицы измерения длины тренажёр по математике (4 класс) по теме Тренажёр Единицы измерения длины тренажёр по математике (4 класс) по теме 186
Старые русские меры Старые русские меры 131
Урок 17. Подготовка к решению задач. Выбор схемы Урок 17. Подготовка к решению задач. Выбор схемы 92
Показательная функция и её свойства Показательная функция и её свойства 118
Учебно методический комплект по математике : Закрепление. Подготовка к умножению 2 класс (конспект + презентация) план-конспект урока по математике (2 класс) Учебно методический комплект по математике : Закрепление. Подготовка к умножению 2 класс (конспект + презентация) план-конспект урока по математике (2 класс) 118
Презентация для урока математики во 2 классе. Числа 11 - 13. Закрепление презентация к уроку по математике (2 класс) Презентация для урока математики во 2 классе. Числа 11 - 13. Закрепление презентация к уроку по математике (2 класс) 140
Учебно-методический комплект ПНШ для проведения урока математика в 3 классе по теме: Деление разности на число. Закрепление изученного план-конспект урока по математике (3 класс) по теме Учебно-методический комплект ПНШ для проведения урока математика в 3 классе по теме: Деление разности на число. Закрепление изученного план-конспект урока по математике (3 класс) по теме 100
Урок-путешествие по математике в 1 классе по учебнику Л.Г.Петерсон. план-конспект урока по математике по теме Урок-путешествие по математике в 1 классе по учебнику Л.Г.Петерсон. план-конспект урока по математике по теме 117
Решение задач на применение основных тригонометрических формул и преобразование выражений Решение задач на применение основных тригонометрических формул и преобразование выражений 133
Презентация Уголок занимательной математики презентация к уроку по математике Презентация Уголок занимательной математики презентация к уроку по математике 165
Презентация к уроку математики.2 класс. презентация к уроку по математике (2 класс) по теме Презентация к уроку математики.2 класс. презентация к уроку по математике (2 класс) по теме 130
Доли.Обыкновенные дроби. Доли.Обыкновенные дроби. 108