Составители:
Рубрика:
17
§6. Выбор оптимального маршрута
перевозки грузов
Пусть транспортная сеть состоит из 10 узлов. На рис. 5 по-
казаны сеть дорог и стоимость перевозки единицы груза
между пунктами сети. Ребра являются вариантами воз-
можного выбора решения. Необходимо определить мар-
шрут доставки груза из пункта 1 в пункт 10, обеспечиваю-
щий наименьшие транспортные расходы.
1
2
5
3
4
6
7
8
9
10
7
8
6
8
4
6
9
7
5
3
5
6
10
9
4
11
0
1
2
3
4
Рисунок 5
В задаче имеется ограничение – двигаться по изо-
браженным на схеме маршрутам можно только слева на-
право, т.е. попав, например, в пункт 8, мы имеем право пе-
реместиться только в пункт 10 и не можем возвратиться
обратно в 5-й или 6-й.
Вложим данную задачу в схему динамического про-
граммирования.
I. Строим управляемую динамическую систему:
1) под первым шагом будем понимать переход сис-
темы из пункта 1 в один из пунктов 2, 3, 4. Под вторым
шагом – переход системы из пунктов 2, 3, 4 в один из
пунктов 5, 6 и т.д. Имеем конечное число
4n
шагов;
2) под состояниями будем понимать пункты, из кото-
рых состоит транспортная сеть. Они, очевидно, заданы на
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
