🗊Презентация АиФП 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. Динамическое программирование Об идее, как и о привидении,… следует немного поговорить, прежде чем она явится. Ч. Диккенс
Описание слайда:
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)
Описание слайда:
Иллюстрация метода на примере чисел Фибоначчи 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.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)
Описание слайда:
Алгоритм 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)
Описание слайда:
Оценка эффективности алгоритма вычисления биномиальных коэффициентов Оценка эффективности алгоритма вычисления биномиальных коэффициентов Базовая операция – сложение. 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 Требуется найти: наиболее ценное подмножество, помещающееся в рюкзаке.
Описание слайда:
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.
Описание слайда:
Экземпляр задачи, определяемый первыми 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].
Описание слайда:
Все подмножества первых 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<0 Начальные условия: V[0,j]=0 при j0 V[i,0]=0 при i0 Цель: Найти V[n,W], т.е. максимальную стоимость подмножества из n предметов, которое помещается в рюкзак ёмкостью W, и само это подмножество.
Описание слайда:
Рекуррентное соотношение max{V[i-1,j], vi +V[i-1, j-wi]}, если j-wi0 V[i,j]= V[i-1,j], если j-wi<0 Начальные условия: V[0,j]=0 при j0 V[i,0]=0 при i0 Цель: Найти V[n,W], т.е. максимальную стоимость подмножества из n предметов, которое помещается в рюкзак ёмкостью W, и само это подмножество.

Слайд 12


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

Слайд 13


Пример 1. W=5
Описание слайда:
Пример 1. W=5

Слайд 14


Ёмкость j
Описание слайда:
Ёмкость 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).
Описание слайда:
Максимальная стоимость: 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).

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию