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

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

АиФП 5. Динамическое программирование, слайд №1

АиФП 5. Динамическое программирование, слайд №2

АиФП 5. Динамическое программирование, слайд №3

АиФП 5. Динамическое программирование, слайд №4

АиФП 5. Динамическое программирование, слайд №5

АиФП 5. Динамическое программирование, слайд №6

АиФП 5. Динамическое программирование, слайд №7

АиФП 5. Динамическое программирование, слайд №8

АиФП 5. Динамическое программирование, слайд №9

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

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

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

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

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

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

Содержание ▲

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

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

Слайд 1

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

5. Динамическое программирование Об идее, как и о привидении,… следует немного поговорить, прежде чем она явится. Ч. Диккенс

Слайд 2

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

Динамическое программирование – метод проектирования алгоритмов. Динамическое программирование – метод проектирования алгоритмов. Предложен американским математиком Ричардом Беллманом как общий метод оптимизации многостадийных процессов принятия решений. Динамическое программирование – метод решения задач с перекрещивающимися подзадачами.

Слайд 3

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

Иллюстрация метода на примере чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13… F(n)=F(n-1) + F(n-2), n≥2 (1) Начальные условия: F(0)=0, F(1)=1 (2)

Слайд 4

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

5.1. Вычисление биномиальных коэффициентов Биномиальным коэффициентом С(n, k) называется количество комбинаций (подмножеств) из k элементов из n-элементного множества (0≤k≤n). Название «биномиальные коэффициенты» происходит от участия этих чисел в формуле бинома: (a+b)n =C(n,0)an +…+ C(n,k)an-kbk +…+C(n,n)bn C(n,k)= C(n-1,k-1)+ C(n-1,k) при n>k>0 (3) C(n,0)=C(n,n)=1 (4)

Слайд 5

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

Таблица для вычислений биномиальных коэффициентов

Слайд 6

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

Алгоритм Binomial (n,k) Алгоритм Binomial (n,k) // Вх. данные: Пара неотрицательных чисел n≥k ≥0 // Вsх. данные: Значение C(n,k) for i0 to n do for j 0 to min(i,k) do if j=0 or j=I C[i,j] 1 else C[i,j]  C[i-1,j-1] + C[i-1,j] return C(n,k)

Слайд 7

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

Оценка эффективности алгоритма вычисления биномиальных коэффициентов Оценка эффективности алгоритма вычисления биномиальных коэффициентов Базовая операция – сложение. A(n,k) – общее количество сложений при вычислении C(n,k). k i-1 n k k n A(n,k)= 1 + =1= (i-1)+  k= i-1 j=1 i=k+1 j=1 i=1 i=k+1 =[(k-1)k]/2+k(n-k)O(nk)

Слайд 8

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

5.2. Задача о рюкзаке и функции с запоминанием Дано: Рюкзак вместимостью W Количество предметов: n Веса предметов: w1 , w2 , …,wn Стоимости предметов: v1 , v2 , …,vn Требуется найти: наиболее ценное подмножество, помещающееся в рюкзаке.

Слайд 9

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

Экземпляр задачи, определяемый первыми i предметами (1i  n) Веса: w1 , w2 , …,wn Стоимости: v1 , v2 , …,vn Ёмкость рюкзака: 1j  W. V[i,j] – значение оптимального решения этого экземпляра задачи, т.е. стоимость наиболее ценного подмножества предметов из первых i предметов, которые помещаются в рюкзак ёмкости j.

Слайд 10

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

Все подмножества первых i предметов, которые помещаются в рюкзак ёмкостью j делятся на две категории: Все подмножества первых i предметов, которые помещаются в рюкзак ёмкостью j делятся на две категории: те, которые не включают i-й предмет; те, которые его включают. Замечания. Среди подмножеств (ПМ), которые не включают i-й предмет, стоимость оптимального ПМ – V[i-1,j]. Среди ПМ, которые включают i-й предмет, оптимальное ПМ составляется из оптимального ПМ из этого предмета и первых (i-1) предметов, которые размещаются в рюкзаке ёмкостью (j-wi). Стоимость такого оптимального ПМ равна vi+V[i-1,j-wi].

Слайд 11

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

Рекуррентное соотношение max{V[i-1,j], vi +V[i-1, j-wi]}, если j-wi0 V[i,j]= V[i-1,j], если j-wi

Слайд 12

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

Таблица для решения задачи о рюкзаке методом динамического программирования

Слайд 13

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

Пример 1. W=5

Слайд 14

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

Ёмкость j

Слайд 15

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

Максимальная стоимость: V[4,5]=37. Максимальная стоимость: V[4,5]=37. 1.Поскольку V[4,5] V[3,5], то предмет 4 был включен в решение вместе с оптимальным подмножеством, заполняющим оставшиеся 5-2=3 единицы ёмкости рюкзака. Это элемент V[3,3]. 2.Поскольку V[3,3]= V[2,3], то предмет 3 не является частью оптимального подмножества. 3. Поскольку V[2,3]  V[1,3], то предмет 2 также является частью оптимального подмножества. 4. V[1,3-1] остается в качестве определения оставшейся части подмножества. Т.к. V[1,2]  V[0,2], то предмет 1 входит в оптимальное подмножество. Эффективность алгоритма O(n*W) Время поиска оптимального подмножества  O(n+W).