Динамическое программирование

<wikitex>

Определение

Определение:

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

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

Источник

• Лекция 10.11.2011
• Жадные алгоритмы