ВУЗ:
Составители:
101
- второй раз – от начала к концу (находятся оптимальные шаго-
вые управления и действительный выигрыш на всех шагах).
Применение динамического программирования для выбора оп-
тимальной трассы кабельной линии
Рассмотрим применение динамического программирования для
решения конкретной задачи.
Необходимо проложить кабельную линию в условиях крупного
города из точки А в точку А
1
. Рассматриваемая часть города разбита на
кварталы (см. рис. 6.1). Прокладку можно производить только вдоль
улиц и проездов. Затраты на прокладку линии по участкам в условных
единицах указаны на рис. 6.1.
Решение задачи. В нашем случае вся операция легко разбивается
на отдельные шаги. За шаг можно принять прокладку линии на отдель-
ном участке улицы или проезда.
Следует выбрать
трассу прокладки таким образом, чтобы сум-
марные затраты по всей линии были бы наименьшими. Таким образом,
как следует из рис. 6.1, вся задача разбивается на восемь шагов. Начнем
решение с последнего восьмого шага. Сначала посмотрим, каким обра-
зом мы можем попасть в точку А
1
за один шаг. Очевидно, что это мож-
но сделать только из точек В
1
и В
2
(рис. 6.1), при этом из каждой из
41
33
23 12
44 38 37 22 13
25
33 45 53
60
68 62 53
45
41
53 58 64 71
75
A
7
12
10
11 9
12
13
9
10 11
8 7
16
12
10
9
11
8
16
6
9
15
8
16
11
14
12
13
12
10
11
14
10
5
8
7
D
2
C
1
B
1
Рис. 6.1. Оптимальный путь по сетке
А
1
B
2
C
2
Е
D
3
C
3
D
4
D
1
Страницы
- « первая
- ‹ предыдущая
- …
- 99
- 100
- 101
- 102
- 103
- …
- следующая ›
- последняя »
