Методы разработки алгоритмов: «разделяй и властвуй» и динамическое программирование 2012 Середа А.Н.

Разделяй и властвуй Этапы решения задачи 1.Разделяй! Задача разделяется на две или более задачи меньшей размерности, решаемых независимо одна от другой 2.Покоряй! Каждая из полученных подзадач решается рекурсивно 3.Соединяй! Из решений подзадач компонуется решение исходной задачи

Пример задачи. Пример задачи. Отсортировать массив по возрастанию. Решение Решение. 1.Делим массив на две примерно равные части 2.Сортируем каждую из них по возрастанию 3.Сливаем два отсортированных массива в один Разделяй и властвуй

15,25,14,1,10,2,0,1715,25,14,115, ,114110,2,0,1710,21020,17017 Подзадачи независимы! В процессе разделения не возникает одинаковых подзадач Разделяем

Разделяй и властвуй ,251,142,100,17 1,14,15,250,2,10,17 0,1,2,10,14,15,17,25 Покоряем и соединяем

Разделяй и властвуй А как соединяем? Выбираем меньший из верхних Количество действий пропорционально сумме количеств элементов соединяемых массивов

Динамическое программирование Задача разбивается на вспомогательные задачи меньшей размерности Эти вспомогательные задачи не являются независимыми, т.е. разные вспомогательные задачи используют решение одних и тех же подзадач Решения вспомогательных задач запоминаются в таблице, чтобы не тратить время на их повторное решение Из решений перекрывающихся вспомогательных задач получается решение исходной задачи

Фишка может двигаться только вперед по полю длины N. Длина хода фишки не более K. Найти число различных вариантов ходов, при которых фишка может пройти поле от начала до конца. Например, при N=3, K=2 возможные пути: (1,1,1), (1,2), (2,1), т.е. возможны 3 варианта. Начальное положение фишки первая клетка поля, конечное первая клетка за пределами поля. Динамическое программирование Пример задачи

Пусть длина поля N=5, максимальная длина хода K=3 Представим в виде дерева размер поля, ещё не пройденного фишкой, включая поле, на котором она стоит. Лист дерева соответствует фишке, вышедшей за пределы поля. Ответ на вопрос задачи – количество путей от корня дерева до его листьев Динамическое программирование Анализируем

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

Восходящее динамическое программирование

Нисходящее динамическое программирование Другой подход