285
правок
Изменения
Нет описания правки
<wikitex>==Определение==Оптимальная политика обладает тем свойством{{Определение|definition = '''Принцип оптимальности для подзадач''' – важнейшее свойство задачи, чтоформулирующееся следующим образом: <br> «Если есть оптимальное решение для некоторой подзадачи, каковы бы ни были начальное состояние и принятое начальное решениекоторая возникает в процессе решения задачи, последующие <br>то именно его нужно использовать для решения должны составлять оптимальную политику относительно состояниязадачи в целом»}}<br>Рассмотрим принцип оптимальности для динамического программирования на префиксе:<br>Префикс оптимального пути из $S \rightsquigarrow U$ является оптимальным путём из $S \rightsquigarrow U$.Требуется дойти до $T$. Оптимальный путь проходит через $U$. <br>Пусть префикс $dU$ неоптимальный. Это значит, возникшего что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$,<br> а путь от $U \rightsquigarrow T$ добавим в результате первоначального решенияконец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется.</wikitex>
