Изменения

Перейти к: навигация, поиск

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

2 байта добавлено, 04:29, 26 ноября 2011
Нет описания правки
[[Файл:ST.jpg]]
Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Требуется дойти до $T$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquiarrow rightsquigarrow U$), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется.
</wikitex>
285
правок

Навигация