Лекция: Жадные и динамические алгоритмы.
Все мы знаем, что такое жадный алгоритм. Жадный алгоритм выбирает самое локально оптимальное решение. Ну, например. У вас есть монеты достоинством 25, 10, 5, 1 копейка. Надо отдать сдачу 61 копейку. Жадный алгоритм отдаст 25, 25, 10, 1 монетки, а не, например, 61 монетку достоинством 1 копейка. То есть выбрал сначала самые большие, а потом поменьше.
Стоит подчеркнуть, что не каждый жадный алгоритм дает выгоду в целом. Как на практике бывает, жадный алгоритм в сию минуту может оказаться выгодным, но в целом результат может быть неблагоприятным.
Примерами жадных алгоритмов являются так же алгоритм Дейкстры и Краскала.
Пример.
Видим на рисунке граф с отрицательной стоимостью между вершинами b и c. Если источником является вершина s, то алгоритм Дейкстры сначала правильно находит минимальное расстояние 1 от s до a. Теперь, рассматривая ребра от s (или a) до b (или c), алгоритм рассчитывает, что мин-ое расстояние s->a->b имеет длину 3. Но далее получаем, что c имеет кратчайший путь до s длиной 1. Однако, жадный выбор b вместо c является неоправданным. Оказывается, что путь s->a->c->b имеет длину лишь 2, поэтому вычисленное нами мин-ое расстояние для b является неправильным.
А еще очень круто жадный алгоритм решает задачу коммивояжера, так как это считается самый оптимальный алгоритм для данной задачи. Здесь, жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Динамические алгоритмы.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
И еще раз основная идея: Решаем задачу в несколько шагов, «ветвясь в ширину».На следующем шаге пользуемся частичными данными со всех ветвей предыдущих шагов.
С точки зрения реализации иногда бывает проще создать таблицу решений всех подзадач, которые нам когда-либо придется решать. Мы заполняем таблицу в не зависимости от того, нужна ли нам на самом деле конкретная подзадача для получения общего решения. Заполнение таблицы подзадач для получения решения определенной задачи получило название динамическое программирование.
Классические примеры:
§ Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
§ Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
§ Задача о редакционном расстоянии (Расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
§ Задача о Вычислении чисел Фибоначчи