Динамическое программирование — различия между версиями
Borisov (обсуждение | вклад) |
Borisov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
<wikitex> | <wikitex> | ||
| − | == | + | ==Оптимальность для подзадач== |
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так: | Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так: | ||
{{Определение | {{Определение | ||
|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}} | |definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}} | ||
| + | |||
| + | ==Оптимальная подструктура== | ||
| + | Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой | ||
| + | Задача по нахождению кратчайшего пути до некоторой вершины графа (например, $S$<sub>$i,j$</sub>) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$<sub>$1,j-1$</sub> или $S$<sub>$2,j-2$</sub>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием. | ||
| + | |||
==Принцип оптимальности для динамического программирования на префиксе== | ==Принцип оптимальности для динамического программирования на префиксе== | ||
[[Файл:ST.jpg|320px]] | [[Файл:ST.jpg|320px]] | ||
| − | Рассмотрим принцип оптимальности для динамического программирования на префиксе | + | Рассмотрим принцип оптимальности для динамического программирования на префиксе. |
Задан граф. Требуется дойти от $S$ до $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquigarrow U$ ), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. | Задан граф. Требуется дойти от $S$ до $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquigarrow U$ ), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. | ||
| Строка 15: | Строка 20: | ||
*Лекция 10.11.2011 | *Лекция 10.11.2011 | ||
*[http://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9E.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.B4.D0.BB.D1.8F_.D0.BF.D0.BE.D0.B4.D0.B7.D0.B0.D0.B4.D0.B0.D1.87|Википедия, Жадный алгоритм] | *[http://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9E.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.B4.D0.BB.D1.8F_.D0.BF.D0.BE.D0.B4.D0.B7.D0.B0.D0.B4.D0.B0.D1.87|Википедия, Жадный алгоритм] | ||
| − | *Т. Кормен. «Алгоритмы. Построение и анализ» (Глава 15 | + | *Т. Кормен. «Алгоритмы. Построение и анализ» (2<sup>ое</sup>издание, Глава 15) |
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория:Динамическое программирование]] | [[Категория:Динамическое программирование]] | ||
Версия 04:27, 27 ноября 2011
<wikitex>
Содержание
Оптимальность для подзадач
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так:
| Определение: |
| «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом» |
Оптимальная подструктура
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе кратчайшего пути от одной вершины к другой Задача по нахождению кратчайшего пути до некоторой вершины графа (например, $S$$i,j$) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$$1,j-1$ или $S$$2,j-2$). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
Принцип оптимальности для динамического программирования на префиксе
Рассмотрим принцип оптимальности для динамического программирования на префиксе.
Задан граф. Требуется дойти от $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)
