Динамическое программирование
Версия от 07:40, 23 ноября 2011; Borisov (обсуждение | вклад)
<wikitex>
Определение
| Определение: |
| Принцип оптимальности для подзадач – важнейшее свойство задачи, формулирующееся следующим образом: «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом» |
Рассмотрим принцип оптимальности для динамического программирования на префиксе:
Префикс оптимального пути из $S \rightsquigarrow U$ является оптимальным путём из $S \rightsquigarrow U$. Требуется дойти до $T$. Оптимальный путь проходит через $U$. Пусть префикс $dU$ неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$,
а путь от $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется.
</wikitex>
Ссылки
- Лекция 10.11.2011
- Жадный алгоритм
- Т. Кормен. «Алгоритмы. Построение и анализ» (Глава 15.3)
