Презентация на тему: ЖАДНЫЕ АЛГОРИТМЫ

ЖАДНЫЕ АЛГОРИТМЫ
ПОНЯТИЕ
ПРИМЕР
ПРИНЦИПЫ
ПРИНЦИПЫ
Задача №113188. Авторитеты
ЖАДНЫЕ АЛГОРИТМЫ
ЖАДНЫЕ АЛГОРИТМЫ
ЖАДНЫЕ АЛГОРИТМЫ
1/9
Средняя оценка: 4.6/5 (всего оценок: 22)
Код скопирован в буфер обмена
Скачать (196 Кб)
1

Первый слайд презентации: ЖАДНЫЕ АЛГОРИТМЫ

Изображение слайда
2

Слайд 2: ПОНЯТИЕ

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

Изображение слайда
3

Слайд 3: ПРИМЕР

Задача, решаемая жадными алгоритмами: имеется ряд задач x 1..x k с определенной прибылью за их выполнение, а также количество дней N на их выполнение, при этом k>N. Одно задание можно выполнить за один день. Необходимо составить расписание с максимальной прибылью. Задача, не решаемая жадными алгоритмами: имеется рюкзак вместимостью 100 л, а также набор вещей с весами 10 л, 30 л, 50 л и ценностью 10, 33, 50 соответственно. Необходимо заполнить рюкзак с достижением максимальной ценности.

Изображение слайда
4

Слайд 4: ПРИНЦИПЫ

Задачи, решаемые жадными алгоритмами обладают следующими свойствами: 1. Глобально оптимальное решение задачи содержит в себе решение всех её подзадач. 2. Последовательность локально оптимальных выборов дает глобально оптимальное решение.

Изображение слайда
5

Слайд 5: ПРИНЦИПЫ

Глобальное оптимальное решение можно получить, делая локально оптимальный (жадный) выбор. Выбор, сделанный в жадном алгоритме, может зависеть от сделанных ранее выборов, но он не может зависеть от каких бы то ни было выборов или решений последующих подзадач Необходимо доказать, что жадный выбор на каждом этапе приводит к глобальному оптимальному решению Обычно исследуется глобальное оптимальное решение некоторой подзадачи Затем демонстрируется, что решение можно преобразовать так, чтобы в нем использовался жадный выбор, в результате чего, получится аналогичная, но более простая подзадача Часто благодаря предварительной обработке входных данных или применению подходящей структуры данных можно ускорить процесс жадного выбора

Изображение слайда
6

Слайд 6: Задача №113188. Авторитеты

Толик придумал новую технологию программирования. Он хочет уговорить друзей использовать ее. Однако все не так просто. i-й друг согласится использовать технологию Толика, если его авторитет будет не меньше ai (авторитет выражается целым числом). Как только i-й друг начнет ее использовать, к авторитету Толика прибавится число bi (попадаются люди, у которых bi < 0). Помогите Толику наставить на путь истинный как можно больше своих друзей.

Изображение слайда
7

Слайд 7

Изображение слайда
8

Слайд 8

Изображение слайда
9

Последний слайд презентации: ЖАДНЫЕ АЛГОРИТМЫ

Изображение слайда