Задача об оптимальном маршруте в сети дорог
Маршрут может быть оптимальным в различных смыслах – минимум расхода горючего, минимальное время в пути, минимум вероятности аварии и т.п. В этом разделе определим кратчайший путь между пунктами А и В. Пункты находятся вне города и их разделяет сложная сеть дорог, рис. 6.4.
С
еть
дорог разобьем на зоны путем введения
пунктирных не пересекающихся
разграничительных линий. Линии эти
можно наносить с любой частотой и
наклоном. Более выгодно разграничительные
линии проводить через узловые точки
дорог, т.к. в этом случае сокращается
количество анализируемых вариантов.
Разграничительным
линиям присвоим номер k,
,
т.о. в нашем распоряжении окажутся n
зон (см. рис. 6.4). Далее обозначим через
(
где
– количество точек на линии k)
пункты под номером i
на k-й
разграничительной линии. Исходные и
конечные пункты при этом будут обозначены
как
и
.
Далее обозначим через
расстояние между точками
,
,
а через
– кратчайшее расстояние между пунктами
и пунктом В.
В таком случае основное функциональное
уравнение Беллмана запишется как
. (6.2)
Вообще говоря, при решении конкретных задач это уравнение можно использовать в более простом виде, а именно,
.
П
ример.
Сеть дорог
с километражем представлена на рис.
6.5.
В соответствии с принципом Беллмана вначале рассмотрим этап под номером IV – переход с разграничительной линии под номером 4 в точку B. Составляем таблицу 6.7.
k = 4 Таблица 6.7
-
i
j
1
B
50
50
2
B
38
38
3
B
36
36
4
B
46
36
5
B
76
76
В колонке i
указаны номера точек на разграничительной
линии 4, а в колонке
– расстояние между
этими точками и точкой B.
Этап III. На этом этапе составляется таблица 6.8 – перехода из точек разграничительной линии 3 в точку B.
k = 3 Таблица 6.8
-
i
j
1
1
2
3
4
5
39
39
50
38
36
46
76
89
77
77
2
1
2
3
4
5
37
30
50
38
36
46
76
73
76
73
3
1
2
3
4
5
42
50
38
36
46
76
118
118
4
1
2
3
4
5
50
38
36
46
76
При составлении этой таблицы был учтен тот факт, что, например, из точки 1 линии 3 нет дороги в точку 3 разграничительной линии 4, а потому расстояние между ними принято равным бесконечности. В таком случае такие точки вообще можно не рассматривать (что в дальнейшем и будем делать) и вместо табл. 6.8 следует использовать более простую табл. 6.9.
k = 3 Таблица 6.9
-
i
j
1
1
2
39
39
50
38
89
77
77
2
3
4
37
30
36
46
73
76
73
3
5
42
76
118
118
Колонка
заполняется по табл. 6.7, величины
находятся как наилучшее значение колонки
.
Этап II. Составляется табл. 6.10.
k = 2 Таблица 6.10
-
i
j
1
1
49
77
126
126
2
1
2
49
40
77
73
126
113
113
3
2
3
47
53
73
118
120
171
120
4
2
3
45
51
73
118
118
169
118
Этап I. Составляется табл. 6.11.
k = 1 Таблица 6.11
-
i
j
A
1
2
3
4
40
32
30
34
126
113
120
118
166
145
150
152
145
П
оследовательно
используя табл. 6.11, табл. 6.10, табл. 6.9,
табл. 6.7, составляем оптимальный маршрут:
Общая протяженность пути 145 км, что подтверждается табл. 6.11.