Презентация Динамическое программирование

Август 27, 2022

Главная
Алгебра
Презентация Динамическое программирование

Содержание

2. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше
3. Динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в
4. Р. Беллман Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом. Слово «программа» в
5. Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру. Прямая линия обозначает
6. В общем случае мы можем решить задачу проделывая следующие три шага.
7. Перекрывающиеся подзадачи
8. Свойства задачи.
9. Два подхода к решению задач:
10. Классические задачи динамического программирования Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную
12. Скачать презентацию

Слайд 2

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

сложность которых чуть меньше исходной. В этом случае время вычислений можно значительно сократить.

Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.

Слайд 3

Динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые

могут повторно встретиться в дальнейшем.

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

Слайд 4

Р. Беллман
Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом.
Слово «программа»

в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи.

Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE.

Слайд 5

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

оптимальную подструктуру.
Прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь.

Оптимальная подструктура

Слайд 6

В общем случае мы можем решить задачу проделывая следующие три шага.

Слайд 7

Перекрывающиеся
подзадачи

Слайд 8

Свойства задачи.

Слайд 9

Два подхода к решению задач:

Слайд 10

Классические задачи динамического программирования
Задача о наибольшей общей подпоследовательности: даны две последовательности,

требуется найти самую длинную общую подпоследовательность.
Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
Задача о вычислении чисел Фибоначчи
Задача о порядке перемножения матриц: даны матрицы. Требуется минимизировать количество скалярных операций для их перемножения.
Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
Алгоритм Флойда-Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.