Динамическое программирование - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Динамическое программирование, слайд №10

Динамическое программирование, слайд №11

Динамическое программирование, слайд №12

Динамическое программирование, слайд №13

Динамическое программирование, слайд №14

Динамическое программирование, слайд №15

Динамическое программирование, слайд №16

Динамическое программирование, слайд №17

Динамическое программирование, слайд №18

Динамическое программирование, слайд №19

Динамическое программирование, слайд №20

Динамическое программирование, слайд №21

Динамическое программирование, слайд №22

Динамическое программирование, слайд №23

Динамическое программирование, слайд №24

Динамическое программирование, слайд №25

Динамическое программирование, слайд №26

Динамическое программирование, слайд №27

Динамическое программирование, слайд №28

Динамическое программирование, слайд №29

Динамическое программирование, слайд №30

Динамическое программирование, слайд №31

Динамическое программирование, слайд №32

Динамическое программирование, слайд №33

Динамическое программирование, слайд №34

Динамическое программирование, слайд №35

Динамическое программирование, слайд №36

Динамическое программирование, слайд №37

Динамическое программирование, слайд №38

Динамическое программирование, слайд №39

Динамическое программирование, слайд №40

Динамическое программирование, слайд №41

Динамическое программирование, слайд №42

Динамическое программирование, слайд №43

Динамическое программирование, слайд №44

Динамическое программирование, слайд №45

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Динамическое программирование. Доклад-сообщение содержит 45 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Динамическое программирование

Слайд 2

Описание слайда:

Динамическое программирование Словосочетание динамическое программирование впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. Первоначально эта область была основана, как системный анализ и инжиниринг. Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию почти никакого отношения не имеет и происходит от словосочетания «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

Слайд 3

Описание слайда:

В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага: В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага: Разбиение задачи на подзадачи меньшего размера. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм. Использование полученного решения подзадач для конструирования решения исходной задачи. Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Слайд 4

Описание слайда:

Недостаток рекурсии: Недостаток рекурсии: Простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал. Что делать? Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэшированием.

Слайд 5

Описание слайда:

Пример 1. Числа Фибоначчи //рекурсивный вариант int fib (int n) { if (n

Слайд 6

Описание слайда:

Динамическим программированием называется способ Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи, вычисление идет от малых подзадач к большим, ответы подзадач запоминаются в таблице и используются при решении больших задач. Необходимо определить исходные данные задачи – параметры. Например, при нахождении суммы некоторого набора чисел параметрами задачи будут количество чисел и их значения. Тогда задача может быть формализована в виде некоторой функции, аргументами которой могут являться количество параметров и их значения.

Слайд 7

Описание слайда:

Под подзадачей понимается та же постановка задачи, но с меньшим числом параметров или с тем же числом параметров, но при этом хотя бы один из параметров имеет меньшее значение. Под подзадачей понимается та же постановка задачи, но с меньшим числом параметров или с тем же числом параметров, но при этом хотя бы один из параметров имеет меньшее значение. Преимущество метода состоит в том, что если подзадача решена, то ее ответ где-то хранится и никогда не вычисляется заново. Сведение решения задачи к решению некоторых подзадач может быть записано в виде соотношений, в которых значение функции, соответствующей исходной задаче, выражается через значения функций, соответствующих подзадачам. Значения аргументов у любой из функций в правой части соотношения меньше значения аргументов функции в левой части соотношения. Если аргументов несколько, то достаточно уменьшения одного из них.

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Пример 2. Найти количество последовательностей длины N из нулей и единиц, не содержащих двух единиц подряд. Пусть sec[ k ] – количество последовательностей длины k из нулей и единиц, не содержащих двух единиц подряд. k = 0 seq [ k ] = 0 k = 1 seq[ k ] = 2 1, 0 k = 2 seq[ k ] = 3 00, 01, 10 Пусть мы знаем решение для всех i < k, тогда посчитаем seq[ k ]. Чтобы получить последовательность длины k из последовательности длины k – 1, нужно в конец дописать либо 0 либо 1. Дописываем 0: seq[ k ] = seq[ k – 1] Дописываем 1: seq[ k ] = seq[ k – 2], т.к. в конце должно быть только …01 seq[ k ] = seq[ k – 1] + seq[ k – 2]

Слайд 10

Описание слайда:

Пример 3. Сумма квадратов На какое минимальное количество квадратов можно разложить число n? Пусть sq[ k ] – минимальное количество квадратов, на которые можно разложить число k. k = 0 sq [ k ] = 0 k = 1 sq [ k ] = 1 11 k = 2 sq [ k ] = 2 11 + 11 Пусть нам известно решение для всех i < k, тогда посчитаем sq[ k ]. Предположим, что нам нужно узнать, сколько квадратов будет в разложении k, если в этом разложении обязательно есть квадрат jj. sq[k] = 1 + sq[ k – j  j ], если j  j  k

Слайд 11

Описание слайда:

Пример 3. Сумма квадратов, продолжение dp[0] = 0; for (int i = 1; i

Слайд 12

Описание слайда:

Пример 4. Рюкзак 1 Имеется n неделимых предметов, вес i-го предмета есть wi . Определить, существует ли набор предметов, суммарный вес которого равен W килограммам. Если такой набор существует, то определить список предметов в наборе. Обозначим через T(n, W) функцию, значение которой равно 1, если искомый набор имеется, и равно 0, если набора нет. Аргументами функции будут количество предметов n, по которому можно определить вес каждого предмета, и суммарный вес набора W. Определим подзадачи, решением которых будут функции T(i, j), где i обозначает количество начальных предметов, j – требуемый суммарный вес, где 0 ≤ i ≤ n, 1 ≤ j ≤ W. Определим начальные значения функции T: T(0, j) = 0 при j ≥ 1 (нельзя без предметов набрать массу j > 0), T(i, 0) = 1 при i ≥ 1 (всегда можно набрать вес, равный 0).

Слайд 13

Описание слайда:

Для решения подзадачи, соответствующей функции T(i, j), Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. i-ый предмет в набор не берется. Решение задачи с i предметами сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j). 2) i-ый предмет в набор берется. Вес оставшихся предметов уменьшается на величину wi: T(i, j) = T(i -1, j - wi). При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j. Для оптимального решения из двух возможных вариантов нужно выбрать наилучший. Рекуррентное соотношение при i ≥ 1 и j ≥ 1: T(i, j) = T(i − 1, j) при j < wi T(i, j) = max (T(i − 1, j), T(i − 1, j − wi)) при j ≥ wi.

Слайд 14

Описание слайда:

W = 16; w1 = 4; w2 = 5; w3 = 3; w4 = 7; w5 = 6. W = 16; w1 = 4; w2 = 5; w3 = 3; w4 = 7; w5 = 6.

Слайд 15

Описание слайда:

Пример 5. Задача о рюкзаке Задача состоит в том, чтобы определить наиболее ценную выборку из n предметов, подлежащих упаковке в рюкзак, имеющий ограничение по весу, равное W килограмм. При этом i-ый предмет характеризуется стоимостью сi и весом wi. Итак, необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W, а суммарная стоимость была максимальна. Если перебирать всевозможные подмножества данного набора из n предметов, то получится решение сложности не менее чем O(2n). В настоящее время неизвестен алгоритм решения этой задачи, сложность которого является полиномиальной. Мы рассмотрим алгоритм решения данной задачи для случая, когда все входные данные – целые числа. Его быстродействие есть O(nW).

Слайд 16

Описание слайда:

Решение Обозначим через T(n, W) функцию, значение которой соответствует решению нашей задачи. Аргументами функции является количество предметов n, по которому можно определить стоимость и массу каждого предмета, и ограничение по весу W. Определим подзадачи, решением которых будут функции T(i, j), а именно, определим максимальную стоимость предметов, которые можно уложить в рюкзак с ограничением по весу j килограмм, если можно использовать только первые i предметов из заданных, где 0 ≤ i ≤ n, 0 ≤ j ≤ W. Определим начальные значения функции T : T(0, 0) = 0, T(0, j) = 0 при j ≥ 1 (нет предметов, максимальная стоимость равна 0), T(i, 0) = 0 при i ≥ 1 (можно брать любые из первых i предметов, но ограничение по весу равно 0).

Слайд 17

Описание слайда:

Для решения подзадачи, соответствующей функции T(i, j), Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. 1) i-ый предмет не упаковывается в рюкзак. Решение задачи с i предметами сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j). 2) i-ый предмет упаковывается в рюкзак. Масса оставшихся предметов уменьшается на величину wi, а при добавлении i-го предмета стоимость выборки увеличивается на ci: T(i, j) = T(i -1, j - wi) + ci. При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j.

Слайд 18

Описание слайда:

Для оптимального решения из двух возможных вариантов упаковки рюкзака нужно выбрать наилучший. Рекуррентное соотношение при i ≥ 1 и j ≥ 1: T(i, j) = T(i − 1, j) при j < wi T(i, j) = max (T(i − 1, j), T(i − 1, j − wi) + ci) при j ≥ wi.

Слайд 19

Описание слайда:

Пример W = 16, c1 = 5, w1 = 4; c2 = 7, w2 = 5; c3 = 4, w3 = 3; c4 = 9, w4 = 7; c5 = 8, w5 = 6.

Слайд 20

Описание слайда:

Обратный ход Требуется определить набор предметов, которые подлежат упаковке в рюкзак. Сравним значение T[n, W] со значением T[n-1, W]. 1) Если T[n, W] ≠ T[n − 1, W], то предмет c номером n обязательно упаковывается в рюкзак, после чего переходим к сравнению элементов T[n − 1, W − wn] и T[n − 2, W − wn] и т.д. 2) Если T[n − 1, W] = T[n − 1, W], то n-ый предмет можно не упаковывать в рюкзак. В этом случае следует перейти к рассмотрению элементов T[n − 1, W] и T[n − 2, W] .

Слайд 21

Описание слайда:

Пример В примере T[5, 16] = T[4, 16], поэтому 5-ый предмет в рюкзак не упаковывается. Переходим к сравнению элементов таблицы T[4, 16] и T[3, 16]. Их значения не равны, следовательно, четвертый предмет должен быть включен в искомый набор, а ограничение на вес становится равным 16 – w4= 16 – 7 =9. Далее сравним элементы T[3, 9] и T[2, 9], они равны, поэтому третий предмет в рюкзак не упаковывается и сравниваем T[2, 9] и T[1, 9], они не совпадают, следовательно, второй предмет должен быть взят в рюкзак, а ограничение на вес становится равным 9 - w2 = 9 – 5 =4. И наконец сравниваем элементы T[1, 4] и T[0, 4], они не равны, поэтому второй предмет включатся в искомый набор, при этом, ограничение по весу становится равным 0. Итак, для нашего примера в рюкзак упакуются предметы с номерами 1, 2, 4.

Слайд 22

$void Print_item(int i, int j) void Print_item(int i, int j) { if (T[i][j]==0) //максимальный рюкзак для параметров return; //имеет нулевую ценность...$

Описание слайда:

void Print_item(int i, int j) void Print_item(int i, int j) { if (T[i][j]==0) //максимальный рюкзак для параметров return; //имеет нулевую ценность else if (T[i-1][j] == T[i][j]) Print_item (i-1,j); //можно составить // рюкзак без i-го предмета else { Print_item(i-1,j-w[i]); //Предмет i //упаковывается в рюкзак Printf(“%d “, i); // печать i-го предмета } } В программе нужно вызвать функцию Print_item с параметрами (n,W). Заметим, что рассуждения были приведены для случая, когда все предметы различны. Самостоятельно рассмотрите, какие изменения будут внесены в таблицу в противном случае.

Слайд 23

Описание слайда:

Пример 6. Задача "Divisibility“ 1999-2000 ACM NEERC (подключена в системе тестирования NSUTS в школьных тренировках) Рассмотрим произвольную последовательность целых чисел. Можно поставить знаки операций + или – между целыми в данной последовательности, получая при этом различные арифметические выражения, которые при их вычислении имеют различные значения. Давайте, например, возьмем следующую последовательность: 17, 5, -21, 15. Из нее можно получить восемь различных выражений: 17+5+-21+15= 16 17-5+-21+15=6 17+5+-21-15=-14 17+5--21+15=58 17+5--21-15= 28 17-5+-21-15=-24 17-5--21+15= 48 17-5--21-15=18 Назовем последовательность делимой на K, если можно так расставить операции + или – между целыми в последовательности, что значение полученного выражения делилось бы нацело на K. В приведенном выше примере последовательность делима на 7 (17+5+-21-15=-14), но не делима на 5. Напишите программу, которая определяет делимость последовательности целых чисел.

Слайд 24

Описание слайда:

Решение Если число N делится на некоторое число К, то остаток от деления N на K равен 0. Остаток от деления суммы чисел на некоторое число равен остатку от деления суммы остатков от деления каждого числа на это число. (a + b) mod c == (a mod c + b mod c ) mod c

Слайд 25

Описание слайда:

Пример 7. Задача "Gangsters" (подключена в системе тестирования NSUTS в школьных тренировках) N гангстеров идут в ресторан. i-ый гангстер заходит в Ti-е время и имеет при себе Pi денег. Дверь ресторана имеет k+1 стадий открытия, выраженных в целых числах от 0 до k. Состояние открытия может измениться на 1 в единицу времени, т.е. либо открыться на 1, либо закрыться на 1, либо остаться прежним. В начальный момент состояние двери закрытое = 0. i-тый гангстер может войти в ресторан, если дверь открыта специально для него, т.е. состояние двери совпадает с шириной его плеч Si. Если в момент времени, когда гангстер подошел к ресторану, состояние открытия двери не совпадает с шириной его плеч, то он уходит и никогда не возвращается. ресторан работает в интервале времени [0, T]. Цель: собрать в ресторане гангстеров с максимальным количеством денег.

Слайд 26

Описание слайда:

Гангстеры , продолжение первая строка входного файла содержит значения N, K и T, разделенные пробелами (1  N  100, 1  K  100, 0  T  30000 ); вторая строка содержит моменты времени, в которые гангстеры подходят к ресторану T1, T2, ... , TN, разделенные пробелами (0  Ti  T для i = 1, 2. ..., N);в третьей строке записаны суммы денег каждого гангстера P1, P2, ... , PN, разделенные пробелами ( 0  Pi  300, для i = 1, 2. ..., N); четвертая строка содержит значения ширины плеч каждого гангстера, разделенные пробелами (0  Si  K для i = 1, 2. ..., N). Все значения целые. Выходные данные: В выходной файл выдать одно целое число — максимальное значение достатка всех гангстеров, собранных в ресторане. Если ни один гангстер не может попасть в ресторан, выдать 0. Пример 1 Пример 2 Вход: Выход: Вход: Выход: 4 10 20 26 2 17 100 0 10 16 8 16 5 0 10 11 15 1 50 33 10 7 1 8 6 1

Слайд 27

Описание слайда:

Пример t = 1 2 3 4 5 6 S = 1 2 3 4 5 1 P = 1 1 1 1 1 100

Слайд 28

Описание слайда:

Пример 8. Алгоритм Ахо Пусть даны две строки S1 и S2. Необходимо за минимальное число допустимых операций преобразовать строку S1 в строку S2. Допустимой операцией являются следующие операции удаления символа из строки и вставки символа в строку: DEL(S, i) – удалить i-ый элемент строки S; INS(S, i, c) – вставить символ c после i-го элемента строки S. Обозначим через S [i..j] – подстроку от i-го символа до j-го. Пусть M(i, j) – минимальное количество операций, которые требуются, чтобы преобразовать начальные i символов строки S1 в начальные j символов строки S2: S1[0..i] –> S2[0..j]. S1[0..0] и S2[0..0] – пустые строки.

Слайд 29

Описание слайда:

Заметим, что для преобразования пустой строки в строку длины j Заметим, что для преобразования пустой строки в строку длины j требуется j операций вставки, т.е. M (0, j) = j . Аналогично для преобразования строки длины i в пустую строку требуется i операций удаления, т.е. M (i, 0) = i. Пусть мы решили подзадачу c параметрами i –1 и j – 1. Это означает, что из строки S1[0..i–1] построена строка S2[0..j–1] за минимальное число допустимых операций M(i –1, j –1). I) Пусть S1[i] = S2[j]. Тогда для получения строки S2[0..j] из строки S1[0..i] не требуется никаких дополнительных операций. Следовательно, M (i, j) = M (i – 1, j – 1).

Слайд 30

Описание слайда:

II) Пусть S1[i] ≠ S2[j]. Возможны два способа получения строки II) Пусть S1[i] ≠ S2[j]. Возможны два способа получения строки S2[0..j]. 1. Пусть из строки S1[0..i–1] построена строка S2[0..j] за минимальное количество операций M (i–1, j ). Тогда для получения строки S2[0..j] из строки S1[0..i] требуется удалить i-ый символ из строки S1. 2. Пусть из строки S1[0..i] построена строка S2[0..j–1] за минимальное количество операций M (i, j–1). Тогда для получения строки S2[0..j] из строки S1[0..i] потребуется одна операция вставки i-го символа строки S1 после символа S2[j–1]. Из 2-х возможностей нужно выбрать лучшую. Получим следующие рекуррентные соотношения:

Слайд 31

Описание слайда:

M (0, j) = j; M (i, 0) = i; M (0, j) = j; M (i, 0) = i; M (i, j) = min (M (i – 1, j – 1), M (i – 1, j ) + 1, M (i , j – 1) +1), если S1[i] = S2[j]; M (i, j) = min (M (i – 1, j ), M (i , j – 1)) + 1, если S1[i] ≠ S2[j]; Решением задачи будет значение M(m,n), где m — длина строки S1, а n — длина строки S2.

Слайд 32

Описание слайда:

Пример S1 = ”abc”, S2 = ”aabddc” Построим таблицу M, нумерация строк и столбцов которой начинается с нуля и элементами которой будут числа, равные значениям функции, описанной выше.

Слайд 33

Описание слайда:

Обратный ход М[1,3] = 2, означает, что из строки “a” можно получить строку “aab”, используя две допустимых операции. В примере за три допустимых операции можно преобразовать строку S1 в S2. Для определения операций нужно встать на последний символ строки S1 и начать движение по таблице от правого верхнего угла. В примере движение начнется с ячейки М[3,6]. Находясь в ячейке М[i, j], будем рассматривать два случая. 1) Если М[-1, i] = М[j, -1], то будем сдвигаться по диагонали влево-вниз, попадая в ячейку М[i-1, j-1]. При этом будем перемещаться по строке S1 на один символ влево, т.е. сделаем текущим в строке символ, находящийся в i-1 позиции. 2) Если М[-1, i] ≠ М[j, -1], то будем сдвигаться по таблице на одну позицию либо влево, попадая в ячейку М[i, j-1], либо вниз в ячейку М[i-1, j]. Этот выбор будет зависеть от того, какой из элементов, находящихся в этих ячейках, меньше. При движении влево будем удалять i-ый символ в строке S1, перемещась на один символ влево. При движении вниз будем вставлять после i-го символа в строке S1 символ S2[j].

Слайд 34

Описание слайда:

Последовательность действий для примера Изначально текущим в строке S1 является последний символ – символ c. Так как М[-1, 3] = М[6, -1], то осуществляем переход в ячейку М[5, 2] и текущим в S1 становится предпослений символ – b. Далее, так как М[-1, 2] ≠ М[5, -1], передвигаемся в ячейку М[4, 2]. При этом вставим после текущего символа b символ S2 [5] = d (j=5). Продолжая этот процесс вставим символ S2 [4] = d, затем в строке S1 сделаем текущим сивол a, вставим в строку S1 символ a. Процесс продолжается до тех пор, пока не достигнем ячейки M[0,0]. Для нашего примера последовательность операций будет следующая: INS(S1, 2, ‘d’), INS(S1, 2, ‘d’), INS(S1, 1, ‘a’). abc –> abc –> abdc –> abddc –> abddc –> aabddc

Слайд 35

Описание слайда:

Отметим, что решений в данной задаче может быть несколько. Отметим, что решений в данной задаче может быть несколько. Движение по таблице представлено ниже.

Слайд 36

Описание слайда:

Задача о телефонном номере (подключена в системе тестирования NSUTS в школьных тренировках) Если вы обратили внимание, то клавиатура многих телефонов выглядит как показано –> Использование изображенных на клавишах букв позволяет представить номер телефона в виде легко запоминающихся слов. Многие фирмы пользуются этим и стараются подобрать себе номер телефона так, чтобы он содержал как можно больше букв из имени фирмы. Напишите программу, которая преобразует исходный цифровой номер телефона в соответствующую последовательность букв и цифр, содержащую как можно больше символов из названия фирмы. При этом буквы из названия фирмы должны быть указаны в полученном номере в той же последовательности, в которой они встречаются в названии фирмы. Например, если фирма называется IBM, а исходный номер телефона — 246, то замена его на BIM не допустима, тогда как замена его на 2IM или В4М является правильной. S1= “IBM”, S2= “246”. При этом, если в S1 встречаются буквы, которые соответствуют цифрам номера телефона в нужном порядке, то они останутся без изменения.

Слайд 37

Описание слайда:

Формат входных данных: Формат входных данных: Первая строка входного файла содержит название фирмы. Она состоит только из заглавных букв латинского алфавита, количество которых не превышает 80 символов. Вторая прока содержит номер телефона в виде последовательности цифр. Цифр в номере телефона также не более 80. Формат выходных данных: В единственной строке выходного файла должно содержаться число букв из измененного номера. Пример файла входных данных: IBM 246 Пример файла выходных данных: 2

Слайд 38

Описание слайда:

Пример 9. Задача о расстановке скобок Рассмотрим вычисление произведения n матриц M = M1 x M2 x ... x Mn. (1) Порядок, в котором матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления матрицы М, независимо от алгоритма, применяемого для умножения матриц. Умножение матрицы размера [р  q] на матрицу размера [q r] требует pqr операций.

Слайд 39

Описание слайда:

Пример Рассмотрим произведение матриц: М = M1  М2  М3  М4 [1020] [2050] [501] [1 100] Если вычислять матрицу М в порядке: M1  ( М2  ( М3  М4,)), то потребуется 125 000 операций. (50*1*100)  [50 100], 5000; (20*50*100)  [20 100], 100000; (10*20*100)  [10 100], 20000. Вычисление же в порядке: ( M1  (М2  М3 )) М4 требует лишь 2 200 операций. (20*50*1)  [20 1], 1000; (10*20*1)  [10 1], 200; (10*1*100)  [10 100], 1000.

Слайд 40

Описание слайда:

Перебор с целью минимизировать число операций имеет Перебор с целью минимизировать число операций имеет экспоненциальную сложность. На первом этапе определим за какое минимальное количество операций можно получить матрицу М из равенства (1). Будем считать подзадачами вычисление минимального количества операций при перемножении меньшего, чем n, количества матриц. В качестве параметров рассматриваемой задачи возьмем индексы i и j (1 i  j  n), обозначающие номера первой и последней матриц в цепочке Mi  Мi+1  ...  Мj . Сначала решим подзадачи, когда j =i+1, т.е. когда перемножаются две рядом стоящие матрицы. Решения – количество затраченных операций, запишем в ячейке таблицы T с номерами (i. j). Tij  число, равное количеству операций при умножении цепочки матриц Mi …  Мj, где 1 i  j  n.

Слайд 41

Описание слайда:

Обозначим через tij минимальную сложность вычисления Обозначим через tij минимальную сложность вычисления цепочки матриц Mi  Мi+1  ...  Мj , где 1 i  j  n. Ее можно получить следующим образом:

Слайд 42

Описание слайда:

Для примера из четырех матриц в таблице будут определены Для примера из четырех матриц в таблице будут определены следующие элементы T: t1,2, t2,3 и t3,4.

Слайд 43

Описание слайда:

Итак, tij вычисляются в порядке возрастания разностей нижних Итак, tij вычисляются в порядке возрастания разностей нижних индексов. Процесс начинается с вычисления tii для всех i, затем ti,i+1 для всех i, потом ti,i+2 и т. д. При этом tik и tk+1,j будут уже вычислены, когда мы приступим к вычислению tij. Оценка сложности данного алгоритма есть О (п3). В результате работы алгоритма для примера из четырех матриц будет построена следующая таблица T: Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке то значение k, на котором достигается минимум.

Слайд 44

Описание слайда:

Алгоритм for (i=0; i

Слайд 45

Описание слайда:

Упражнение Задана строка, состоящая из вещественных чисел, разделенных арифметическими операциями. Требуется расставить в строке скобки таким образом, чтобы значение полученного выражения было максимальнвым.

Теги Динамическое программирование

Похожие презентации