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

Материал из Викиконспекты
Перейти к: навигация, поиск

<wikitex>

Определение

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

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

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

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
  • Жадный алгоритм
  • Т. Кормен. «Алгоритмы. Построение и анализ» (Глава 15.3)