Содержание
- 2. 17.03.2014 Динамическое программирование АНАЛОГИИ Решение методом динамического программирования Задачи: Перемножение цепочки матриц Оптимальные БДП Задача Х
- 3. 17.03.2014 Динамическое программирование Оценка количества узлов дерева Оценить количество узлов дерева в общем случае можно подсчетом
- 4. 17.03.2014 Динамическое программирование Начальное условие p1 = 1. Далее p2 = p1 p1 = 1, p3
- 5. 17.03.2014 Динамическое программирование Несколько первых чисел Каталана Ср. Сn –1 и (n3 – n)/3 Например, при
- 6. 17.03.2014 Динамическое программирование Число bn структурно различных бинарных деревьев с n узлами bk bn − k
- 7. 17.03.2014 Динамическое программирование b2 = b0 b1 + b1 b0 = 2, b3 = b0 b2
- 8. Решение методом динамического программирования Структура оптимального решения Рекуррентное соотношение Вычисление оптимальной стоимости (по рекуррентному соотношению) Построение
- 9. 17.03.2014 Динамическое программирование Задача: оптимальная триангуляция выпуклого многоугольника
- 10. 17.03.2014 Динамическое программирование Триангуляция (диагонали не пересекаются внутри многоугольника) Задача: оптимальная триангуляция выпуклого многоугольника Выпуклый n-угольник
- 11. 17.03.2014 Динамическое программирование На треугольниках определена весовая функция w(Δvivjvk) Например, w(Δv1v2v3) = ⎪v1v2⎪+⎪v2v3⎪ +⎪v2v3⎪ Задача: оптимальная
- 12. 17.03.2014 Динамическое программирование Количество способов триангуляции Вершин n, диаг. = n – 3 , треуг. =
- 13. 17.03.2014 Динамическое программирование Количество способов триангуляции n = 6, диаг. =3, треуг. = 4, вариантов =
- 14. 17.03.2014 Динамическое программирование Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 1 mij – вес ОТМ
- 15. Динамическое программирование Вычисление таблиц: mi,i+1 = 0, {при i=1..n-1} mi,i+2 = w(Δi,i+1,i+2), {при i=1..n-2} mi,i+3 =…
- 16. 17.03.2014 Динамическое программирование Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 2 mij – вес ОТМ
- 17. 17.03.2014 Динамическое программирование Упражнения Доказать что триангуляция n – угольника содержит n-2 треугольника и n-3 диагоналей.
- 18. 17.03.2014 Динамическое программирование Связь задач 1 2 3 4 5 0 M1 M2 M3 M4 M5
- 19. 17.03.2014 Динамическое программирование Связь задач 1 2 3 4 5 0 (M1 M2) (( M3 M4)
- 20. 17.03.2014 Динамическое программирование Триангуляции Деревья
- 21. 17.03.2014 Динамическое программирование 0 1 0 1 0 1 0 1 0 0 1 1 0
- 22. Преобразование «Ползущий червь» 17.03.2014 Динамическое программирование 0 1 0 0 1 1 Обход в глубину: от
- 23. Литература Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ : учеб./ М.: МЦМНО, 1999.
- 25. Скачать презентацию