Задача об оптимальном маршруте в сети дорог
Маршрут может быть оптимальным в различных смыслах – минимум расхода горючего, минимальное время в пути, минимум вероятности аварии и т.п. В этом разделе определим кратчайший путь между пунктами А и В. Пункты находятся вне города и их разделяет сложная сеть дорог, рис. 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.