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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<wikitex>
 
<wikitex>
==Оптимальность для подзадач==
+
 
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве,  термин оптимальности для подзадач может быть различным.
+
 
  
 
==Определение==
 
==Определение==
 +
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве,  термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так:
 
{{Определение
 
{{Определение
|definition = '''Принцип оптимальности для подзадач''' – важнейшее свойство задачи, формулирующееся следующим образом:
+
|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}
«Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}
+
==Принцип оптимальности для динамического программирования на префиксе==
  
 
Рассмотрим принцип оптимальности для динамического программирования на префиксе:
 
Рассмотрим принцип оптимальности для динамического программирования на префиксе:

Версия 04:19, 26 ноября 2011

<wikitex>


Определение

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

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

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

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

ST.jpg

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

Ссылки

  • Лекция 10.11.2011
  • Жадный алгоритм
  • Т. Кормен. «Алгоритмы. Построение и анализ» (Глава 15.3)