Что такое 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
  • Количество просмотров: 111
  • Количество скачиваний: 0
- Предыдущая Фишбоун – эффективный прием работы с текстом
Следующая - Особенности культурно-досуговой программы в учреждении дополнительного образования

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

Конспект занятия по ФЭМП c ИКТ в средней группе. Тема: Магазин план-конспект занятия по математике (средняя группа) Конспект занятия по ФЭМП c ИКТ в средней группе. Тема: Магазин план-конспект занятия по математике (средняя группа) 137
Конспект урока математики по теме: Деление многозначного числа на однозначное 4 класс, УМК Перспектива план-конспект урока по математике (4 класс) Конспект урока математики по теме: Деление многозначного числа на однозначное 4 класс, УМК Перспектива план-конспект урока по математике (4 класс) 156
Презентация Таблица единиц времени(обобщающий урок) презентация к уроку по математике (4 класс) Презентация Таблица единиц времени(обобщающий урок) презентация к уроку по математике (4 класс) 118
по математике Внеклассное мероприятие по математике Внеклассное мероприятие 127
ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ 223
Презентация по теме Объемы многогранников Презентация по теме Объемы многогранников 151
Поймай звезду Поймай звезду 137
Презентация по математике 5 класс Презентация по математике 5 класс 93
Учебно - методический комплект по математике Письменное сложение и вычитание столбиком план-конспект урока по математике (2 класс) Учебно - методический комплект по математике Письменное сложение и вычитание столбиком план-конспект урока по математике (2 класс) 50
Презентация по теме: Вычитание натуральных чисел Презентация по теме: Вычитание натуральных чисел 115
Учебно - методический комплект - Единица массы - тонна, центнер (3 класс Перспектива) Конспект + презентация план-конспект урока по математике (3 класс) по теме Учебно - методический комплект - Единица массы - тонна, центнер (3 класс Перспектива) Конспект + презентация план-конспект урока по математике (3 класс) по теме 119
Интерактивный тренажёр Навстречу звёздам по теме Сложение и вычитание чисел в пределах 20 Интерактивный тренажёр Навстречу звёздам по теме Сложение и вычитание чисел в пределах 20 85
Квадрат 8 класс Квадрат 8 класс 163
Особенности геометрических построений на компьютере Особенности геометрических построений на компьютере 96
Развитие логического мышления презентация к уроку по математике по теме Развитие логического мышления презентация к уроку по математике по теме 105
Обобщающий урок по теме Таблицы и диаграммы Обобщающий урок по теме Таблицы и диаграммы 120
Презентация Оқыту мен оқуда ақпараттық технологияны пайдалану Презентация Оқыту мен оқуда ақпараттық технологияны пайдалану 160
математические диктанты 1 клас презентация урока для интерактивной доски по математике (1 класс) математические диктанты 1 клас презентация урока для интерактивной доски по математике (1 класс) 104
Математический КВН презентация к уроку по математике Математический КВН презентация к уроку по математике 109
Презентация.Цифра 3.Железо. презентация к уроку по математике (средняя группа) Презентация.Цифра 3.Железо. презентация к уроку по математике (средняя группа) 114
Проект по математике 2 класс Оригами Проект по математике 2 класс Оригами 146
matematicheskaya shkatulka 17 zanyatie matematicheskaya shkatulka 17 zanyatie 140
Задачи на смеси, растворы и сплавы Задачи на смеси, растворы и сплавы 125
Множители. Произведение. план-конспект урока по математике (2 класс) по теме Множители. Произведение. план-конспект урока по математике (2 класс) по теме 112
Числовые неравенства Числовые неравенства 124
Презентация по математике Изображение обыкновенных дробей точками на координатной прямой Презентация по математике Изображение обыкновенных дробей точками на координатной прямой 191
Свойства степени Свойства степени 104
Устный счёт 6 класс математика Устный счёт 6 класс математика 139
Презентация к уроку проектов по математике на тему Любимое число (1 класс) Презентация к уроку проектов по математике на тему Любимое число (1 класс) 111
Умники и умницы Умники и умницы 114