T(1 2) T(1 3) T(1 4) T(1 5) T(2 6) T(2 7)

Разбиваем сеть на пояса и каждый из пунктов отнесем к одному из 4-х поясов. Будем говорить, что пункт принадлежит k-му поясу, если из него можно попасть в конечный 11 пункт ровно за k шагов, т. е. с заездом ровно в k-1 промежуточный пункт. Таким образом, п. п. 8, 9, 10 принадлежат 1 поясу, 6, 7 – ко 2-му, 2, 3, 4, 5 – к третьему и 1 – к четвертому. Н k-ом шаге будем находить оптимальные маршруты из городов k-го пояса до конечного пункта . Номер S города, принадлежащего k-му поясу – переменная состояния. Номер J города (k-1) пояса будет являться переменной управления на k-ом шаге.
1 этап. Условная оптимизация.
1-й шаг. K=1, F1S=ts11
S
J=11
F1(S)
J*
8 12 12 8
9 11 11 9
10 6 6 10
3-й шаг. K=3
Функциональное уравнение имеет вид
F2S=mintsj+F1(j)
S
J=8
J=9
J=10
F2S
J*
6 13+12 11+11 5+6 11 10
7 14+12 10+11 9+6 15 19
2-й шаг