Изменения

 Рассмотрим принцип оптимальности для динамического программирования некий необратимый процесс производства, например, производство консервов и представим его в виде ориентированного и ациклического графа. Предположим, что есть свиноферма и свиньи, которые выращиваются и отправляются на префиксезавод, чтобы стать консервами. Началом производства обозначим вершину графа $S$, а конец производства $T$. Процесс требует оптимизации, т. Задан графе. Требуется дойти от некоторой начальной вершины требуется найти наиболее оптимальный путь $S\rightsquigarrow T$ до конечной . Он проходит через вершину графа $TU$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префиксТеперь рассмотрим принцип оптимальности для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Рассмотрим Пусть префикс $\Delta U$, т.е. путь от $S \rightsquigarrow U$, пусть он неоптимальный. Это значит, что есть более оптимальный путьне оптимален. Тогда заменим этот префикс на более оптимальный путь до неоптимальную часть $S \rightsquigarrow U$пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получится Получим более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. То есть, Т.е. чтобы получить оптимальный путь $S \rightsquigarrow T$ был оптимальнымиз одной вершины графа в другую, нужно чтобы префиксы перед $T$ меньших путей должны быть оптимальными, иными словами, оптимальные префиксы путей между соседними вершинами составляют оптимальный путь от начальной вершины до конечной.