Краткий обзор задач динамического программирования

РефератПомощь в написанииУзнать стоимостьмоей работы

Задача о порядке перемножения матриц: даны матрицы A1, …, A_n, требуется минимизировать количество скалярных операций для их перемножения. Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа. Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами. Методом динамического программирования… Читать ещё >

Краткий обзор задач динамического программирования (реферат, курсовая, диплом, контрольная)

Методом динамического программирования решается очень много задач. Вот краткий их перечень:

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

Показать весь текст

Заполнить форму текущей работой

Другие работы

Численное интегрирование функций

В завершении работы, хочется отметить ряд особенностей применения рассмотренных выше методов. Каждый способ приближённого решения определённого интеграла имеет свои преимущества и недостатки, в зависимости от поставленной задачи следует использовать конкретные методы. Если необходимо быстро получить решение, но нет необходимости в большой точности ответа, следует воспользоваться методом трапеций…

Курсовая