🗊Презентация Алгоритмы нахождения независимого множества

Категория: Математика
Нажмите для полного просмотра!
Алгоритмы нахождения независимого множества, слайд №1Алгоритмы нахождения независимого множества, слайд №2Алгоритмы нахождения независимого множества, слайд №3Алгоритмы нахождения независимого множества, слайд №4Алгоритмы нахождения независимого множества, слайд №5Алгоритмы нахождения независимого множества, слайд №6Алгоритмы нахождения независимого множества, слайд №7Алгоритмы нахождения независимого множества, слайд №8Алгоритмы нахождения независимого множества, слайд №9Алгоритмы нахождения независимого множества, слайд №10Алгоритмы нахождения независимого множества, слайд №11Алгоритмы нахождения независимого множества, слайд №12Алгоритмы нахождения независимого множества, слайд №13Алгоритмы нахождения независимого множества, слайд №14Алгоритмы нахождения независимого множества, слайд №15Алгоритмы нахождения независимого множества, слайд №16
Скачать
Вы можете ознакомиться и скачать презентацию на тему Алгоритмы нахождения независимого множества. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Курсовая работа
Описание слайда:
Курсовая работа

Слайд 2


ФОРМУЛИРОВКА ЗАДАЧИ
Описание слайда:
ФОРМУЛИРОВКА ЗАДАЧИ

Слайд 3


ФОРМУЛИРОВКА ЗАДАЧИ
Описание слайда:
ФОРМУЛИРОВКА ЗАДАЧИ

Слайд 4


ФОРМУЛИРОВКА ЗАДАЧИ
Описание слайда:
ФОРМУЛИРОВКА ЗАДАЧИ

Слайд 5


МЕТОД ПОЛНОГО ПЕРЕБОРА Алгоритм полного перебора проверяет все подмножества вершин, являются ли они независимыми множествами. Этот способ является самым простым и очевидным.
Описание слайда:
МЕТОД ПОЛНОГО ПЕРЕБОРА Алгоритм полного перебора проверяет все подмножества вершин, являются ли они независимыми множествами. Этот способ является самым простым и очевидным.

Слайд 6


МЕТОД ПОЛНОГО ПЕРЕБОРА Алгоритм проверяет каждую вершину на независимость с другими вершинами и составляет для нее независимое множество. Каждое найденное множество необходимо проверять на максимальную независимость. Для этого нужно определять, является ли оно подмножеством какого-либо другого найденного независимого множества. Вычислительная сложность полного перебора O(n2 2n).
Описание слайда:
МЕТОД ПОЛНОГО ПЕРЕБОРА Алгоритм проверяет каждую вершину на независимость с другими вершинами и составляет для нее независимое множество. Каждое найденное множество необходимо проверять на максимальную независимость. Для этого нужно определять, является ли оно подмножеством какого-либо другого найденного независимого множества. Вычислительная сложность полного перебора O(n2 2n).

Слайд 7


АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА Различное количество вершин (Плотность 0.3)
Описание слайда:
АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА Различное количество вершин (Плотность 0.3)

Слайд 8


АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА Различная плотность (Количество вершин 50)
Описание слайда:
АНАЛИЗ МЕТОДА ПОЛНОГО ПЕРЕБОРА Различная плотность (Количество вершин 50)

Слайд 9


АЛГОРИТМ БРОНА-КЕРБОША Способом уменьшения количества рассматриваемых вариантов является поиск с возвращением, этот метод лежит в основе алгоритма Брона-Кербоша. Находит все максимальные по включению независимые множества.
Описание слайда:
АЛГОРИТМ БРОНА-КЕРБОША Способом уменьшения количества рассматриваемых вариантов является поиск с возвращением, этот метод лежит в основе алгоритма Брона-Кербоша. Находит все максимальные по включению независимые множества.

Слайд 10


АЛГОРИТМ БРОНА-КЕРБОША На каждом шаге алгоритма множество V разбито на четыре части: M — текущее независимое множество; Γ(M) — множество вершин, смежных с M; K – множество кандидатов, т. е. вершин, каждая из которых может быть добавлена в M; P – множество просмотренных вершин, каждая из которых не может быть добавлена в текущее M, так как уже добавлялась ранее.
Описание слайда:
АЛГОРИТМ БРОНА-КЕРБОША На каждом шаге алгоритма множество V разбито на четыре части: M — текущее независимое множество; Γ(M) — множество вершин, смежных с M; K – множество кандидатов, т. е. вершин, каждая из которых может быть добавлена в M; P – множество просмотренных вершин, каждая из которых не может быть добавлена в текущее M, так как уже добавлялась ранее.

Слайд 11


АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША Случайный граф плотностью 70%.
Описание слайда:
АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША Случайный граф плотностью 70%.

Слайд 12


АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША Различная плотность (Количество вершин 50)
Описание слайда:
АНАЛИЗ АЛГОРИТМА БРОНА-КЕРБОША Различная плотность (Количество вершин 50)

Слайд 13


СРАВНЕНИЕ АЛГОРИТМОВ Сравнение алгоритмов при различном количестве вершин:
Описание слайда:
СРАВНЕНИЕ АЛГОРИТМОВ Сравнение алгоритмов при различном количестве вершин:

Слайд 14


СРАВНЕНИЕ АЛГОРИТМОВ Сравнение алгоритмов при различной плотности графа:
Описание слайда:
СРАВНЕНИЕ АЛГОРИТМОВ Сравнение алгоритмов при различной плотности графа:

Слайд 15


ВЫВОД На основании проведенного исследования можно сделать вывод, что алгоритм Брона-Кербоша остается одним из самых эффективных на сегодняшний день для поиска наибольшего независимого множества.
Описание слайда:
ВЫВОД На основании проведенного исследования можно сделать вывод, что алгоритм Брона-Кербоша остается одним из самых эффективных на сегодняшний день для поиска наибольшего независимого множества.

Слайд 16


Курсовая работа
Описание слайда:
Курсовая работа

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию