Методы разработки эффективных алгоритмов. Метод разделяй и властвуй. Динамическое программирование

Метод «разделяй и властвуй»
ФПМИ БГУ

«Разделение»
Задача разбивается на независимые подзадачи, т.е. подзадачи не пересекаются (две задачи назовем независимыми, если они не имеют общих подзадач).
2. «Покорение»
Каждая подзадача решается отдельно (рекурсивным методом).
Когда объем возникающих подзадач достаточно мал, то подзадачи решаются непосредственно.
3. «Комбинирование»
Из отдельных решений подзадач строится решение исходной задачи.
«Разделяй и властвуй»
ФПМИ БГУ

При разбиении задачи на подзадачи полезен принцип балансировки, который предполагает, что задача разбивается на подзадачи приблизительно равных размерностей, т. е. идет поддержание равновесия.
Обычно такая стратегия приводит к разделению исходной задачи пополам и обработке каждой из его частей тем же способом до тех пор, пока части не станут настолько малыми, что их можно будет обрабатывать непосредственно. Часто такой процесс приводит к логарифмическому множителю в формуле, описывающей трудоемкость алгоритма.
Таким образом, в основе техники рассматриваемого метода лежит процедура разделения. Если разделение удается произвести без слишком больших затрат, то может быть построен эффективный алгоритм.
«Разделяй и властвуй». Принцип балансировки
ФПМИ БГУ

«Разделяй и властвуй»
Поиск максимального и минимального элементов
Разделим массив на две части (предположим, что n=2k).
В каждой из частей этим же алгоритмом найдём локальные max1, min1, max2 , min2.
Полагаем max=наибольший (max1 ,max2 ), min=наименьший (min1 ,min2 ).
Если в рассматриваемой области меньше 2-х элементов, то деление не выполняем, а за 1 сравнение определим максимальный и минимальный элемент области.
«Разделение» (балансировка)
«Покорение»
«Комбинирование»
Последовательный поиск
Решение на основе принципа «разделяй и властвуй»
ФПМИ БГУ

«Разделяй и властвуй»
def MergeSort (l,r):
if l ≠ r:
k = (l + r) // 2
MergeSort (l,k)
MergeSort (k+1,r)
MergeList (l,k,r)
Делим последовательность элементов на две части (границы l и r включаем; если сортируемая последовательность состояла из n элементов, то первая часть может содержать первых элементов, а вторая часть – оставшиеся; порядок следования элементов в каждой из полученных частей совпадает с их порядком следования в исходной последовательности). Если в последовательности только один элемент, то деление не выполняем.
Сортируем отдельно каждую из полученных частей этим же алгоритмом.
Производим слияние отсортированных частей последовательности так, чтобы сохранилась упорядоченность.
«Покорение»
«Комбинирование»
Сортировка массива слиянием
«Разделение» (балансировка)
ФПМИ БГУ

«Разделяй и властвуй»
def QuickSort(l, r):
if l < r:
Partition QuickSort(l, j)
QuickSort(i, r)
Быстрая сортировка массива Ч. Хоара
Выбираем в качестве сепаратора x медиану рассматриваемой области (за линейное от числа элементов время). Относительно сепаратора x делим массив на три части:
в первой части - элементы, которые меньше или вравны x;
во второй части - элемент x;
в третьей части – элементы, которые больше или равны x.
Сортируем отдельно I и III части этим же алгоритмом. Если в некоторой менее одного элемента, то ничего не делаем.
Происходит слияние отсортированных сегментов в один путем присоединения сегментов.
«Покорение»
«Комбинирование»
«Разделение»
(балансировка)
ФПМИ БГУ

Динамическое программирование
ФПМИ БГУ

Динамическое программирование
Динамическое программирование применяется к задачам, в которых нужно что-то подсчитать или к оптимизационным задачам.
ФПМИ БГУ
Задачи оптимизации. В таких задачах существует много решений, каждому из которых поставлено в соответствие некоторое значение. Необходимо найти среди всех возможных решений одно с оптимальным (наибольшим или наименьшим) значением. Например, во взвешенном графе между заданной парой вершин существует несколько маршрутов, каждый маршрут характеризуется своей длиной, и нам необходимо найти маршрут кратчайшей длины.

Динамическое программирование
Стратегия метода динамического программирования – попытка свести рассматриваемую задачу к более простым задачам.
Задача может быть проще из-за того, что опущены некоторые ограничения. Она может быть проще из-за того, что некоторые ограничения добавлены. Однако, как бы ни была изменена задача, если это изменение приводит к решению более простой задачи, то, возможно, удастся, опираясь на эту более простую, решить и исходную.
ФПМИ БГУ
Метод динамического программирования часто в литературе называют табличным, а одна из клеток таблицы и даёт значение оптимального решения исходной задачи.
Так как возникающие подзадачи являются зависимыми, то данная техника находит своё применение, когда все нужные значения оптимальных решений подзадач помещаются в память. Вычисление идет от малых подзадач к большим, и ответы запоминаются в таблице, что позволяет исключить повторное решение задачи.

Этапы динамического программирования
Задача погружается в семейство вспомогательных подзадач той же природы. Возникающие подзадачи могут являться зависимыми и должны удовлетворять следующим двум требованиям:
подзадача должна быть более простой по отношению к исходной задаче;
оптимальное решение исходной задачи определяется через оптимальные решения подзадач (в этом случае говорят, что задача обладает свойством оптимальной подструктуры, и это один из аргументов в пользу применения для ее решения метода «динамического программирования»).
Каждая вспомогательная подзадача решается (рекурсивно) только один раз. Значения оптимальных решений возникающих подзадач запоминаются в таблице, что позволяет не решать повторно ранее решенные подзадачи.
Для исходной задачи строится возвратное соотношение, связывающее значение оптимального решения исходной задачи со значениями оптимальных решений вспомогательных подзадач (т. е. методом восходящего анализа от простого к сложному вычисляем значение оптимального решения исходной задачи).
Данный этап выполняется в том случае, когда требуется помимо значения оптимального решения получить и само это решение. Часто для этого требуется некоторая вспомогательная информация, полученная на предыдущих этапах метода.
ФПМИ БГУ

решаем задачу i
i
w
u
z
решённые подзадачи z, u, w
ДП «назад»
f(i)=G(f(z)+f(u)+f(w))
i
y
x
задача i уже решена
еще НЕ решённые
подзадачи x и y (зависимые)
подформировываем решение x из i
подформировываем решение y из i
f(x)=G(f(x),f(i))
f(y)=G(f(y),f(i))
ФПМИ БГУ
ДП «вперед»

10
8
не решена
4
2
3
решена
1
5
ФПМИ БГУ
6
9
7
решаем задачу i
i
w
u
z
решаем задачу i
база ДП
ДП «назад»
ДП «назад» («ленивое»)

Задача 1. Лягушка
Ответ: 14
Заданы n кочек. Лягушка сидит на первой кочке. На каждой кочке сидят комарики, известно их число.
За один прыжок лягушка может прыгнуть на 2 или 3 кочки вперёд. Оказавшись на кочке, лягушка скушает всех комариков, которые сидели там.
Необходимо определить максимальное число комариков, которые скушает лягушка, которой обязательно надо приземлиться на последней кочке.
комарики
ФПМИ БГУ

ДП назад (одномерное):
i-1
i-2
i-3
i
ФПМИ БГУ

array
i
F
2
14
18
13
6
5
ФПМИ БГУ
ДП назад (одномерное):
Ответ: 14

i+3
i+2
i+1
i
ДП вперёд (одномерное):
ФПМИ БГУ

i
F
2
7
17
13
6
5
18
14
Время работы алгоритма, основанного на методе ДП:
ФПМИ БГУ
ДП вперёд (одномерное):
array
Ответ: 14

Полный перебор всех вариантов описывается n-м числом Фибоначчи:
Время работы алгоритма для задачи «Лягушка», основанного на методе ДП:
ФПМИ БГУ

Задача 2. Задача расстановки единиц
Задана строка. Необходимо определить количество способов, для того, чтобы расставить j единиц в строке длины n (j≤n).
Количество способов можно посчитать комбинаторно:
Однако при больших значениях n и k итоговое значение уже может не помещаться в целочисленные типы данных. Например, при подсчете числа сочетаний через факториал при n = 100, k = 1 произойдет переполнение, но в тоже время при вычислении с помощью метода ДП не возникнет проблем, так как итоговое значение равно всего лишь 100.
ФПМИ БГУ

На практике, когда результат является достаточно большим числом, в задаче предлагается найти ответ по модулю (% p).
ФПМИ БГУ
Свойства модульной арифметики:
Малая теорема Ферма
Если p – простое число, а – целое число, которое не делится на p, то
эквивалентные формы записи:
Следствие из малой теоремы Ферма (a – целое, p – простое число):
Если два числа сравнимы по модулю p, т.е.
то это записывается:

+
ФПМИ БГУ

Обозначим через F[i,j] - количество способов, для того, чтобы расставить j единиц в строке длины i.
ДП назад (двумерное):
число единиц
длина строки
ФПМИ БГУ

2
3
3
4
6
4
Время работы алгоритма:
ФПМИ БГУ
ДП назад (двумерное):

Обозначим через F[i,j] - количество способов, для того, чтобы расставить j единиц в строке длины i.
ДП вперёд (двумерное):
число единиц
длина строки
ФПМИ БГУ

2
1
1
1
1
1
1
1
1
2
3
3
1
4
3
3
1
1
6
4
1
Время работы алгоритма:
ФПМИ БГУ
ДП вперёд (двумерное):

Задана строка длины n. Необходимо определить количество способов, для того, чтобы расставить j единиц в строке длины n (j≤n).
Время работы алгоритма, основанного на методе динамического программирования:
Количество способов можно посчитать и комбинаторно, но при больших значениях n и k итоговое значение может уже не помещается в целочисленные типы данных.
Например, при подсчете числа сочетаний через факториал при n = 100, k = 1 произойдет переполнение, но в тоже время при вычислении с помощью метода ДП не возникнет проблем, так как итоговое значение равно всего лишь 100.
Задача расстановки единиц
ФПМИ БГУ

Задача 3. Оптимального перемножения группы матриц
Порядок перемножения всех s матриц неоднозначен. Чтобы устранить неоднозначность, нужно расставить скобки. Порядок расстановки скобок однозначно определит последовательность перемножаемых матриц.
Поскольку матричное произведение ассоциативно, то результат не зависит от расстановки скобок, но порядок перемножения может существенно повлиять на время работы алгоритма.
Заданы s матриц:
Определить, какое минимальное число операций умножения требуется для перемножения s матриц, причем перемножать можно любые две рядом стоящие матрицы.
ФПМИ БГУ

Сведения из математики:
при перемножении двух матриц:
B [n × k] * C [k × m]
получим матрицу D [n × m]
Выполнив n·k·m операций умножения.
ФПМИ БГУ
?

Числа Каталана – это последовательность чисел,
названная в честь бельгийского математика Эжен Шарля Каталана.
Сn - обозначение n-ого числа Каталана.
Количество способов расстановки скобок в произведении из (n+1) множителя.
Количество двоичных корневых деревьев с n листьями, у которых из каждого внутреннего узла выходит ровно 2 узла.
Количество правильных скобочных последовательностей длины 2n.
Количество триангуляций выпуклого (n+2)–угольника (разбиение на треугольники непересекающимися диагоналями).
Сn

Рекуррентная и аналитическая формулы для Сn
Сn

Числа Каталана в треугольнике Паскаля
Если в чётных строках i от серединной линии отнять соседний элемент,
то получиться Ci/2 число Каталана.
Если в треугольнике Паскаля в строке n слева направо пронумеровать числа (нумерация с 0), то m-е число есть биномиальный коэффициент: (число способов выбрать m элементов из n)
Сn
ФПМИ БГУ

Количество различных способов задать однозначно порядок перемножения матриц – Сs-1 число Каталана, т.е. экспоненциальная функция.
Метод динамического программирования позволит решить задачу за время :
Задача оптимального перемножения группы матриц
ФПМИ БГУ

Обозначим через минимальное число операций умножения,
чтобы перемножить матрицы с номерами от i до j включительно:
На последнем этапе, когда формируется результирующая матрица , должны были перемножаться две матрицы.
Рассмотрим все возможные варианты того, как эти две матрицы могли быть получены.
Так как у нас оптимизационная задача, то перемножать матрицы
надо за минимально возможно число операций умножения.
ФПМИ БГУ

Справедливо следующее рекуррентное соотношение:
ФПМИ БГУ
1 вариант
2 вариант

Зависимые подзадачи
ФПМИ БГУ

ФПМИ БГУ

Время работы алгоритма оптимального перемножения группы матриц, основанного на методе динамического программирования:
вычислить s(s+1)/2 элементов таблицы;
каждый элемент таблицы вычисляется ровно один раз за не более, чем s арифметических операций.
ФПМИ БГУ

Пример
Ответ:
(A1·(A2·A3))·A4
3 100 операций умножения
ФПМИ БГУ

Задача 4. Максимальный палиндром
Задана строка длины n. Необходимо вычеркнуть минимальное число элементов, чтобы получился палиндром (палиндром - строка, которая одинаково читается слева направо и справа налево).
Для строки: a s d f s l a
Максимальный палиндром: a s d s a
ФПМИ БГУ

Обозначим через F[i,j] длину максимального палиндрома, который можно получить, если мы рассматриваем элементы строки от индекса i до j включительно.
i
j
i+1
j-1
string
F
n=6
ФПМИ БГУ

i
j
i+1
j-1
string
Строки длины 1
Строки длины 2
Строки длины >2
ФПМИ БГУ

Задачи A, B и C являются зависимыми, так как они требуют для своего решения знать длину максимального палиндрома для строки string от индекса i до j включительно.
ФПМИ БГУ
j
j+1
i
i-1

a
s
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
Время работы алгоритма :
ФПМИ БГУ
a s f s a
Пример

Задания
Тема. Динамическое программирование
0.1 Оптимальное перемножение группы матриц (двухмерное ДП)
0.2 Единицы - число сочетаний из n по k(одномерное ДП, модульная арифметика)
0.3. Единицы (большие ограничения, только для желающих)
20. Палиндром (двухмерное ДП, строки)
69. Кувшинки (простейшее одномерное ДП)
Выполнить в системе Insight Runner следующие общие задачи:
ФПМИ БГУ

ЗАДАЧА 5.
БИНАРНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
©ФПМИ, БГУ, Доскоч Роман, 2020 год

ЗАДАЧА
Пусть X и Y — две бинарных последовательности длины N и M соответственно, состоящие из нулей и единиц. Сами последовательности X и Y можно рассматривать как запись в двоичной форме некоторых двух положительных целых чисел.
Необходимо найти максимальное число Z, двоичную запись которого можно получить как из x, так и из y вычёркиванием цифр.

1 ЧАСТЬ (НАХОЖДЕНИЕ ДЛИНЫ LCS)
Сначала перевернем строки.
Дп назад
Сложность O(|Y|*|X|) Память O(|Y|*|X|)

2 ЧАСТЬ (ВОССТАНОВЛЕНИЕ ПУТИ)
i, j текущие индексы
i1,j1 индексы первых единиц
i0,j0 индексы первых нулей
X = 10101101
Y = 10110001
ans = 101101

2 СПОСОБ ВОССТАНОВЛЕНИЯ ПУТИ
Поиск в ширину
Ищем такой путь в котором “быстрее”
встречаются первые 1
Верный путь будет:
012358