ЗАДАЧА  О  ПУТЕШЕСТВИЯХ
     В качестве дальнейшего примера приложения этих идей рассмотрим следующую задачу о путешествиях, которая возникает в самых разнообразных прикладных вопросах.
     Предположим, что имеются N городов, занумерованных индексом 
i=1,2, ..., N в некотором порядке, и задан ряд чисел  ,где —время, потребное на путешествие из i-го города в j-й. 
     Начав с первого города, мы хотим провести путь в N-й, который потребует минимального времени. Мы можем идти прямо или заходить по пути в любой другой город.
     В тех случаях, когда между некоторыми городами не имеется никакой 
связи, мы будем считать соответствующее ,бесконечным или, при использовании цифровых вычислительных машин, очень большим положительным числом.
      Если N велико, то любое решение путем простого перебора невозможно. Попытаемся решить задачу с помощью метода функциональных уравнений. Рассмотрим общую задачу об определении минимального времени, потребного для перехода из i-го города в N-й. Пусть — время, потребное для путешествия из i-го в N-й город при использовании оптимальной политики.
Тогда те же самые доводы, которые мы использовали при рассмотрении предшествующей траекторией задачи, приведут к соотношению

     Легко можно показать, что эта система уравнений имеет единственное решение, а следовательно, что решение этого ряда задач эквивалентно решению исходной задачи.
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
     Уравнение (б.32) обладает особенностью, которая ранее не встречалась; именно здесь неизвестная функция появляется и в левой и в правой частях уравнения. Следовательно, мы не имеем готовой итерационной схемы для его решения.
     Необходимо использовать какой-либо метод последовательных приближений. Мы могли бы, например, положить

     Это приводит к монотонной сходимости снизу. С другой стороны, мы можем мыслить в терминах политик. Рассмотрим сначала те пути, которые ведут прямо из i в N, затем те, в которых делается одна остановка, и т. д. Это приводит к следующей схеме: 

при которой осуществляется монотонная сходимость сверху, причем за конечное число шагов.
     Метод (6.33) оценивает наилучший путь длины k, начинающийся от города i. Однако уравнения имеют то свойство, что N является стоком, и если путь достигает N менее чем за k шагов, то там можно остановиться. Для любого другого города путь не может оборваться ранее k шагов.
     Следовательно, когда k становится большим, все пути стремятся прийти в город N, а минимизация гарантирует, что они сделают это наилучшим образом.
     В методе (6. 34) считается, что каждый город достижим на каждой итерации, но потребное время не обязательно является оптимальным. Последовательные приближения сходятся к наилучшему пути.
Этот пример иллюстрирует различие между итерациями в пространстве функций и в пространстве политик (поведений), рассмотренное в П. дает при каждой итерации оптимальное решение задачи, отличающейся от исходной. Метод (1), прежде чем осуществится сходимость, дает неоптимальное решение исходной задачи. Оба метода пригодны для ручного или машинного счета при умеренных значениях N, т.е. N< 100, и для машинного счета для N порядка нескольких тысяч. 26, n-Й ПО КРАТКОСТИ ПУТЬ
     Иногда бывает интересно определить не только кратчайший путь, но и второй по краткости, третий по краткости и т.п. Тем самым мы сможем оценить, насколько важно использовать наикратчайший путь по сравнению, скажем, с десятым по краткости. Для того чтобы проиллюстрировать метод, введем последовательность величин Vi, равных времени, потребному на переход от i к  N,    (6.35) при использовании   второго по краткости пути,
i=1, 2,…, N-1, 
     Для получения соотношений для vt заметим, что если первая остановка на пути из i в N делается в j, то продолжение движения из j в N должно происходить ' либо по пути, который минимизирует время путешествия от j к N, либо по пути, который является вторым по краткости для перехода из у в N. Пусть - есть абсолютный минимум  (i=1, 2,..., N), - есть вторая по малости величина .
Тогда мы имеем уравнение

a  определены. Аналогичные, но несколько более громоздкие уравнения можно вывести для n-го по краткости пути.