Динамическое программирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<wikitex>
 
<wikitex>
 
==Процесс разработки алгоритмов динамического программирования==
 
==Процесс разработки алгоритмов динамического программирования==
В процессе составления алгоритма задачи с динамическим программированием, требуется следовать последовательности из четырёх шагов:
+
В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:
 
# Описать структуру оптимального решения
 
# Описать структуру оптимального решения
 
# Рекурсивно определить значение оптимального решения
 
# Рекурсивно определить значение оптимального решения
 
# Вычислить значение оптимального решения с помощью метода восходящего анализа
 
# Вычислить значение оптимального решения с помощью метода восходящего анализа
# Составление оптимального решения на основе полученной информации
+
# Составить оптимального решения на основе полученной информации
  
 
==Оптимальная подструктура==
 
==Оптимальная подструктура==

Версия 07:37, 29 ноября 2011

<wikitex>

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

В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:

  1. Описать структуру оптимального решения
  2. Рекурсивно определить значение оптимального решения
  3. Вычислить значение оптимального решения с помощью метода восходящего анализа
  4. Составить оптимального решения на основе полученной информации

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

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

Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе кратчайшего пути от одной вершины к другой.

Задача по нахождению кратчайшего пути между некоторыми вершинами графа (например, $S$$i,j$) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$$1,j-1$ или $S$$2,j-2$). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.

Оптимальность для подзадач

Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:

Определение:
«Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»


Принцип оптимальности для динамического программирования на префиксе

ST.jpg

Рассмотрим принцип оптимальности для динамического программирования на префиксе.

Задан граф. Требуется дойти от $S$ до $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquigarrow U$), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. </wikitex>

Ссылки

  • Лекция 10.11.2011
  • Жадный алгоритм
  • Т. Кормен. «Алгоритмы. Построение и анализ» (2оеиздание, Глава 15)
  • T. H. Cormen. «Introduction to Algorithms» (3rdedidion, Chapter 15)