03-04. Презентация ДП (1)

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

«Разделение»
Задача разбивается на независимые подзадачи, т.е. подзадачи не пересекаются (две задачи назовем независимыми, если они не имеют общих подзадач).
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 части этим же алгоритмом. Если в некоторой менее одного элемента, то ничего не делаем.
Происходит слияние отсортированных сегментов в один путем присоединения сегментов.
«Покорение»
«Комбинирование»
«Разделение»
(балансировка)
ФПМИ БГУ

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

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

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

1
2
x
зависимые задачи (1) и (2)

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

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

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

Задача 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. Задача расстановки единиц
ФПМИ БГУ

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

+
ФПМИ БГУ

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

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 и k промежуточные результаты вычислений могут уже не помещается в целочисленные типы данных.
ФПМИ БГУ

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

Задача 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
аналитическая формулы для Сn

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

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

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

Так как у нас оптимизационная задача, то перемножать матрицы
надо за минимально возможно число операций умножения.
ФПМИ БГУ

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

ФПМИ БГУ
1 вариант
2 вариант
i
j

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

ФПМИ БГУ

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

Пример
ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

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

Задача 4.
Наибольшая общая подпоследовательность (НОП)
англ. longest common subsequence (LCS)
ФПМИ БГУ

ФПМИ БГУ
Крайние случаи:
самая короткая - пустая подпоследовательность (удалены все элементы последовательности Z);
самая длинная - совпадает с самой последовательностью (удалено нулевое множество элементов).

ФПМИ БГУ

ФПМИ БГУ
X=Ф,Б,П,Г,М,У,И
Y=А,Ф,И,П,С,Д,М,И,Б,Г,У
LCS (X,Y) = Ф,П,М,И
|LCS (X,Y)|= 4
В общем случае задача может иметь неоднозначное решение.
X=0,2,0,9,1,9,6,7,22
Y=2,5,0,1,1,9,5,5,22
LCS (X,Y)=2,0,1,9,22
|LCS (X,Y)|= 5
Пример 1.
Пример 2.

ФПМИ БГУ
Сколько подпоследовательностей будет сгенерировано?
Задачу LCS можно решить полным перебором
X=Ф Б П Г М У И Р
Y=А Ф И П С Д М И Б Г Л У В
Время работы алгоритма LCS (X,Y), основанного на полном переборе:
(элементы последовательности разделяются пробелом)

ФПМИ БГУ
F
Задачу LCS можно решить динамическим программированием
Обозначим через F[i,j] длину наибольшей общей подпоследовательности для двух префиксов:
Граничные условия (один из префиксов пустой):

ФПМИ БГУ
1
i
j
j
k
i

ФПМИ БГУ
1
i
j
i-1
j-1

ФПМИ БГУ
1
i
j
i-1
j
i
j-1

ФПМИ БГУ
1
i
j
Получаем для Случая 2 следующее рекуррентное соотношение:

ФПМИ БГУ
Объединяя оба случая, получаем следующее рекуррентное соотношение:

ФПМИ БГУ
F
если не нужно восстанавливать саму подпоследовательность, то можно в памяти хранить только предыдущую строку матрицы и текущую (предыдущий столбец и текущий)
1-й способ
2-й способ
Время работы алгоритма, основанного на ДП:
ДП назад

ФПМИ БГУ
а
т
м
(в примере при неоднозначности движение шло вверх)

Задача 5.
Наибольшая подпоследовательность-палиндром
ФПМИ БГУ

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

ФПМИ БГУ
Неявное решение задачи
a
s
d
f
s
l
a
a
l
s
f
d
s
a
Х=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
ФПМИ БГУ
Ответ:

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

Задачи 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
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
ФПМИ БГУ

a
s
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
ФПМИ БГУ

a
s
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
ФПМИ БГУ

a
s
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
ФПМИ БГУ

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

a
s
d
f
s
l
a
a
s
d
f
s
l
a
a s d f s l a
ФПМИ БГУ
a
Восстановление палиндрома
a s
a s f
a s f s a

Задача 6.
Наибольшая возрастающая подпоследовательность
Longest increasing subsequence, LIS
ФПМИ БГУ

ФПМИ БГУ
Х= 0, 2, 9, 1, 9, 6, 7, 22
НВП(Х)= 0, 2, 6, 7, 22

ФПМИ БГУ
Неявное решение задачи (двумерное ДП)
0
2
9
1
9
6
7
0
1
2
7
9
9
22
НВП (0, 2, 9, 1, 9, 6, 7, 22)=(22, 9, 9, 2,0)
Х= 0, 2, 9, 1, 9, 6, 7, 22
Y= 0, 1, 2, 6, 7, 9, 9, 22
22
6

Явное решение задачи (одномерное ДП)
1
i
i-1
F
ФПМИ БГУ
n
Тогда получаем следующее рекуррентное соотношение:
Ответ:

ФПМИ БГУ
Построить НВП для последовательности:
Х= 0, 2, 9, 1, 9, 6, 7, 22, 1
НВП( 0, 2, 9, 1, 9, 6, 7, 22, 1)=(0,1,6,7,22)
Как восстановить саму НВП(Х)?

9
1
9
6
7
22
1
0
2
среди подпоследовательностей
одинаковой длины оставляем одну – самую перспективную из них: ту, к которой можно подсоединить больше элементов;

Х=6
i
i=UpperBound (х)
Время работы алгоритма построения НВП(Х):

Задача 7.
Преобразование строк
вычисление расстояния Левенштейна
(редакционное расстояние)
ФПМИ БГУ

Заданы две строки, как сравнить их, чтобы определить насколько они похожи?
ФПМИ БГУ
Приложения:
для исправления ошибок при наборе слова;
для сравнения текстовых файлов («символы» – строки файла; «строки» - файлы);
в биоинформатике при сравнении аминокислот.

число позиций, в которых соответствующие символы двух строк одинаковой длины отличаются.
Если строки имеют одинаковую длину,
то для их сравнения можно использовать следующую метрику: расстояние Хэмминга
Ричард Уэсли Хэмминг
Richard Wesley Hamming
1915-1998
США, Чикаго
Если расстояние Хэмминга равно 1, то говорят, что строки являются «соседними».

Если строки имеют разную длину:
Расстояние Левенштейна для двух строк равно минимальному числу односимвольных «редакторских правок»:
Владимир Иосифович Левенштейн
1935-2017
СССР (Россия), Москва
доктор физ.-мат.наук
то для их сравнения можно использовать следующую метрику: расстояние Левенштейна (др. словами редакционное расстояние).

d(Х,Y)=4

ФПМИ БГУ
F
Задачу можно решить динамическим программированием
Граничные условия (один из префиксов пустой):

ФПМИ БГУ

Предположим, что одиночные операции вставки, удаления и замены имеют разную стоимость:

ФПМИ БГУ

ФПМИ БГУ
Действительно, из приведенной выше формулы следуют два неравенства:
Из (1) и (2) следует, что всегда будет выполняться неравенство:
Обоснование корректности упрощенной формулы Кощенко Владиславом, 2022 год.

ФПМИ БГУ
Время работы алгоритма:
Требуемая память:

ФПМИ БГУ
Пример
Рекуррентное соотношение:

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ

ФПМИ БГУ
R(a)
I(a)
D
D
Как восстановить редакторские правки?

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