Будем искать кратчайший маршрут из состояния 1 в 10.
Оптимальная стратегия (кратчайший маршрут) обладает тем свойством, что, каков бы ни был путь достижения некоторого состояния, последующие решения должны принадлежать оптимальной стратегии. Для того, чтобы учесть принцип оптимальности и его вычислительный смысл, удобно использовать следующие обозначения:
yj – стоимость, отвечающая стратегии минимальных затрат для пути от узла j до стока;
Sj – решение, позволяющее достичь yj.
Поскольку из состояния 10 число оставшихся шагов равно 0, то
.
Очень легко можно вычислить y9 и y8:
,
.
Вычислим y7:
, 
.
Теперь можно обнаружить известную методичность и алгоритм поиска оптимальной стратегии представить в виде рекуррентного состояния:
, 
.
Упорядоченная запись остальных вычислений выглядит так:
;
, 
;
, 
;
, 
;
, 
;
, 
;
Искомый маршрут имеет длину 17 и представляет собой последовательность событий: 1 – 3 – 7 – 9 – 10.
На самом деле с помощью этого алгоритма отслеживаются кратчайшие маршруты из всех узлов (состояний) в узел-сток. Для иллюстрации этого вывода результаты таблиц 1-4 сведены в таблицу 5.
Таблица 5
j | Состояние | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
yj | Расстояние до стока | 17 | 16 | 12 | 18 | 8 | 4 | 5 | 1 | 4 | 0 |
Sj | Ближайший адрес | 3 | 6 | 7 | 7 | 8 | 8 | 9 | 10 | 10 | * |
Например, маршрут 2 – 10 имеет длину 16 и представляет собой последовательность событий 2 – 6 – 8 – 10.
Пример: Пусть задана топология сети.
В результате использования алгоритма определения кратчайшего маршрута получим:
, 
;
, 
;
, 
;
, 
;
, 
;
, 
;
, 
;
, 
.
Кратчайшие маршруты из любого узла в узел-сток можно определить по таблице:
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
yj | 0 | 1 | 2 | 3 | 5 | 6 | 7 | 8 |
Sj | * | 1 | 2 | 3 | 4 | 4 | 6 | 7 |
Кратчайший маршрут в сети общего вида
В ациклической сети можно было пронумеровать узлы сети от 1 до р таким образом, что если сеть содержит дугу (i,j), то i<j. Чтобы добиться этого условия присвоим стоку номер р. Зачеркнем этот узел и все входящие в него дуги и не будем их рассматривать в дальнейшем при присвоении номеров.
Возьмем любой другой узел, имеющий теперь только входящие в него дуги, и припишем ему номер р-1. Будем продолжать этот процесс, пока все узлы не будут пронумерованы. В этом случае yk – длину маршрута k-р можно определить рекуррентно.
В сети общего вида, которая имеет петли, такую нумерацию установить не удается.
Алгоритм отыскания кратчайшего маршрута в сети общего вида может быть записан:
1. Вычислить yp=0, а все остальные yk=¥.
2. Если в сети остается хотя бы одна дуга (i,j), такая, что 
, вычислить 
. В противном случае останов.
Краткая математическая запись условий, которым должны удовлетворять все yi, имеет вид:
Вычисления можно проводить в различном порядке.
На самом узле с помощью этого алгоритма отыскиваются кратчайшие маршруты из всех узлов в конечном узле.
|
|
|
 | |
| |
|
| 4 | 2 | |||||
| 5 | 3 | 1 | |||||
¥ | ¥ | ¥ | 0 |
| ||||
i \ j | 1 | 2 | 3 | 4 |
| |||
4 | 5 | ¥ | 1 | 2 | 3 | 5 |
| |
2 | 3 | ¥ | 2 | 1 | 3 |
| ||
1 | ¥ | 3 | 1 | 1 |
| |||
0 | 4 |
| ||||||
Уточнение ближайших адресов (ai) кратчайшего маршрута | 4 | 4 | 4 | Ост |
| |||
3 | 3 |
| ||||||
| 2 |
| ||||||
Уточнение длины (yi) кратчайшего маршрута
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Основные порталы (построено редакторами)