3.5. задача о проектировании дороги

3.5. задача о проектировании дороги

Условие задачи. Пункт Б (город, завод, порт, электростанция и т. п.) расположен на 30 км севернее и на 40 км восточнее пункта А. Между этими пунктами требуется проложить дорогу так, чтобы стоимость ее строительства была минимальной.

Стоимость строительства дороги зависит от ряда факторов: рельефа местности и характера грунта, удаленности места строительства от карьера, асфальтового завода и т. п. Для расчета стоимости строительства были проведены специальные исследования на местности, в результате которых на карте на север и на восток от пункта А была построена условная сетка шагом 10 км, и была оценена стоимость строительства 1 км дороги между каждыми двумя смежными узлами сетки. Полученные данные приведены на рис. 3.10. Например, в соответствии с приведенными данными стоимость строительства 1 км дороги от точки, находящейся в 10 км восточнее и 20 км севернее пункта А, составляет в северном направлении 23, а в восточном — 16 усл. ден. ед.

Для некоторого упрощения задачи и сокращения объема вычислений будем считать, что от каждого узла сетки направление строительства дороги может быть выбрано только по горизонтали и по вертикали, что соответствует на местности направлениям сторон света (север, юг, восток, запад). Будем также предполагать, что дорога не может проходить севернее или восточнее пункта Б и южнее или западнее пункта А. Иными словами, дорога на карте должна располагаться в прямоугольнике, для которого точки А и Б являются соответственно левой нижней и правой верхней вершинами. Такого типа ограничения могут быть обусловлены прохождением административно-территориальных границ, расположением закрытых военных полигонов, наличием рек, озер, морей и других препятствующих строительству объектов.

Решение. Данная задача является примером общей задачи о кратчайшем пути, в которой роль длины пути играет стоимость строительства соответствующего участка дороги. Представленная на рис. 3.10

КМ £

29

23

31

15

30 • 38 - • 34 - • 29 - • 23 •

24

20 • -24- • -16- • -17— • -19•

U

22

о. о о о

U

I I I I |

26

27

25

14

12

10 •-15-«-41-«-5-«-32

11 - • 42 - • 13 •

10 20 30

19

40 км

Восток —» Рис. 3.10

схема является взвешенным графом специального вида. Каждая вершина графа однозначно определяется парой координат, равных числу шагов от начальной вершины, соответствующей пункту А, на восток и на север к рассматриваемой вершине. Один шаг по схеме соответствует отрезку в 10 км на местности. Например, вершины, соответствующие пунктам А и Б, имеют координаты (0;0) и (4;3) (далее будем коротко говорить «вершина (0;0)» и т. д.).

Решим задачу методом ДП, проводя запись на самом графе. В соответствии с этим определим функцию L(v) как длину кратчайшего пути от вершины v до конечной вершины Б. Выполним детально первые шаги алгоритма.

Полагаем Ь(Б) = L(4; 3) = 0, записываем 0 на место вершины (4;3) (см. рис. 3.11) и объявляем данную вершину занятой, а все остальные — свободными.

Поскольку начальная вершина (0;0) не является занятой, то приступаем к расчету оценок незанятых вершин. Для занятой вершины (4;3) с уже известным значением функции L(v) смежными

и незанятыми являются вершины (3;3) и (4;2), причем обе они являются свободными, т. е. ни для одной из них оценки еще не рассчитаны. Для вершины (3;3) имеется лишь одно ребро, идущее в восточном направлении и инцидентное вершине (4;3). Стоимость строительства всего участка дороги между этими смежными вершинами равна произведению стоимости строительства 1 км дороги (23 усл. ден. ед.) на длину участка (10 км). По надлежащей формуле вычисляем оценку

Е(3; 3) = 23 • 10 + L(4; 3) = 230 + 0 = 230.

Ставим стрелку, идущую от (3;3) к (4;3). Аналогично, для вершины (4;2) получаем:

Е(4; 2) = 24 • 10 + L(4; 3) = 240 + 0 = 240.

Из двух найденных оценок значение 230 является минимальным; соответствующую вершину (3;3) объявляем занятой, полагаем

L(3;3) = Е(3;3) = 230

и записываем это число на место вершины (3;3). (Проводя аналогию с классическим методом ДП, можно сказать, что для вершины (3;3) восточное направление представляет собой значение условно-оптимального управления.) Таким образом, значение функции L(y) вычислено уже для двух вершин.

Начальная вершина (0;0) не стала занятой, поэтому продолжаем расчет оценок. Занятыми являются вершины (3;3) и (4;3), а смежными с ними —вершины (2;3), (3;2) и (4;2), причем первые две—свободные, а третья — пробная. Вычисляем оценки свободных вершин: Е(2; 3) = 29 • 10 + L(3; 3) = 290 + 230 = 520, Е(3; 2) = 15 • 10 + L(3; 3) = 150 + 230 = 380.

Ставим стрелки, идущие от этих вершин к (3;3). Для вершины (4;2) имеющаяся оценка 240 не нуждается в корректировке, поскольку с момента ее вычисления не появилось новых занятых вершин, смежных с (4;2). Из трех имеющихся оценок значение 240 является минимальным; соответствующую вершину (4;2) объявляем занятой, полагаем 1,(4; 2) = Е(4; 2) = 240 и записываем это число на место вершины (4;2).

Начальная вершина (0;0) еще не стала занятой, поэтому расчет оценок продолжается. Занятыми являются вершины (3;3), (4;2) и (4;3), а смежными с ними и незанятыми — вершины (2;3), (3;2) и (4;1), причем первые две пробные, а третья — свободная. Вычисляем оценку свободной вершины:

Е(4; 1) = 22 • 10 + L(4; 2) = 220 + 240 = 460,

и ставим стрелку, идущую от (4;1) к (4;2). Рассмотрим пробные вершины (2;3) и (3;3). Для вершины (2;3) имеющаяся оценка 520 не нуждается в корректировке, поскольку с момента ее вычисления не появилось новых занятых вершин, смежных с (2;3). Для вершины (3;2) имеющаяся оценка 380 должна быть откорректирована, поскольку с момента ее вычисления появилась новая смежная с (3;2) занятая вершина (4;2). Проводим корректировку, полагая Ё(3;2) = Е(3;2) = 380:

£(3;2) = min{£(3;2),1910 + L(4;2)} = min {380,430} = 380.

Значение оценки при корректировке не изменилось, так что установленная ранее стрелка у вершины (3;2) остается на прежнем месте. Из трех имеющихся -оценок значение 380 является минимальным; соответствующую вершину (3;2) объявляем занятой, полагаем

L(3;2) = Е(3;2) = 380

и записываем это число на место вершины (3;2).

Начальная вершина (0;0) по-прежнему осталась незанятой, поэтому расчеты продолжаем далее. Действуя по алгоритму, мы последовательно вычислим значения функции L(v) во всех вершинах графа, кроме вершины (0;3), на месте которой оставлена точка. Для этой вершины оценка имеет значение 1230, что больше значения 1220 для начальной вершины А = (0; 0) (вершина (0;3) «не. успела» стать занятой — конечная вершина А стала занятой раньше). Расчет значения L(A) означает завершение этапа условной оптимизации решения задачи. Результаты расчетов полностью приведены на рис. 3.11.

Приступаем к этапу безусловной оптимизации, на котором и строится искомый кратчайший путь. Как видно из расчетов, оптимальное значение задачи, равное минимальной стоимости строительства дороги, составляет

L(A) = L(0;0) = 1220 усл. ден. ед.

Конфигурация дороги минимальной стоимости строится начиная с пункта А с учетом стрелок, расставленных в ходе расчетов. При этом получается следующая цепочка вершин:

(0; 0)(0; 1)(1; 1)(1; 2)(2; 2)(2; 1)(3; 1)(3; 2)(3; 3)(4; 3).

На этом решение задачи завершено. В формулировке ответа полученному результату надлежит дать содержательную трактовку в терминах решаемой задачи.

Ответ: минимальная стоимость строительства дороги из пункта А в пункт Б равна 1220 усл. ден. ед. Дорога минимальной стоимости должна состоять из прямолинейных отрезков, последовательно соединяющих на местности точки с координатами (0;0) (пункт А), (0;10), (10;10), (10;20), (20;20), (20;10), (30;10), (30;20), (30;30), (40;30) км (пункт Б).

К постановке и решению данной задачи необходимо сделать ряд следующих замечаний.

Замечание 1. Задачи, подобные рассмотренной, могут возникать и в несколько ином контексте, например, при проектировании железнодорожных линий, линий электропередачи, газо-, нефте-, водопроводов и других коммуникаций.

Замечание 2. Проанализируем полученное оптимальное решение. Прежде всего отметим, что из вершины (3;0) выходят две стрелки; это означает, что из данной вершины имеется два различных кратчайших пути в конечную вершину Б:

(3;0)-(4;0)-(4;1)-(4;2)-(4;3),

(3;0)-(3;1)-(3;2)-(3;3)-(4;3)

стоимостью 590 усл. ден. ед. Если бы строящийся от вершины А кратчайший путь прошел через вершину (3;0), то существовало бы два различных оптимальных решения задачи. Но кратчайший путь прошел мимо данной вершины, так что неоднозначности оптимального решения в данной задаче не возникло.

Замечание 3. Рассмотрим некоторые числовые характеристики полученного оптимального решения. Спроектированная дорога содержит участок (2; 2) — (2; 1), имеющий «обратное» направление по отношению к общему направлению строительства от А к Б. Вследствие этого общая длина дороги составила 90 км вместо возможных 70 км при проектировании без допущения обратных направлений. Однако стоимость строительства этих более коротких дорог является более высокой (за счет неравномерности распределения стоимостей строительства отдельных участков), что подтверждает известный факт: короткая дорога не всегда является самой оптимальной.

Подчеркнем, что в спроектированной дороге минимальная стоимость строительства отрезка в 1 км равна 4 усл. ден. ед., а средняя стоимость равна

1220 : 90 и 13, 56 усл. ден. ед.,

в то время как в исходных данных задачи имеются участки стоимостью 1, 11, 12 и 13 усл. ден. ед., не вошедшие в проект. Тем самым еще раз подтверждается, что метод ДП оптимизирует не отдельные участки, а всю траекторию в целом.

Далее, средняя по всем ребрам графа стоимость строительства 1 км дороги составляет около 21,16 усл. ден. ед. (это нетрудно установить прямым подсчетом); поэтому оценка средней стоимости дороги длиной 70 км, проложенной без предварительной оптимизации, составит

21,16 • 70 = 1481,2 усл. ден. ед.,

что более чем на 20\% превышает полученную минимальную стоимость дороги длиной 90 км. (Конечно, при построении всевозможных путей ребра, инцидентные вершинам А и Б, встречаются чаще, чем ребра «внутри графа»; соответственно при строгом-вычислении среднего значения стоимости дороги эти ребра необходимо учитывать с большим весом. Точный расчет здесь достаточно сложен и не обязателен, а приведенное значение 1481,2 является допустимым именно как оценка среднего значения.)

Замечание 4. Естественным и логичным обобщением рассматриваемой задачи является допущение строительства дороги не только в направлении сторон света, но и в северо-восточном направлении. Будем считать, что стоимость строительства 1 км дороги на северо-восток равна полусумме стоимостей 1 км на север и на восток в том же месте. Например, в соответствии с приведенными выше данными стоимость строительства 1 км дороги от точки, находящейся в 10 км восточнее и 20 км севернее пункта А, в северо-восточном направлении составляет ,„ . „,

16 + 23 1 „ .

—-— = 19,5 усл. ден. ед.

При этом отрезок дороги между двумя соседними расположенными по диагонали точками имеет длину >/2 • 10 км; будем считать его приближенно равным 14 км (поскольку у/2 « 1,4142). Отметим, что в новой постановке задачи множество допустимых вариантов строительства шире, чем в исходной постановке; в силу этого новая минимальная стоимость дороги должна получиться не выше значения 1220 усл. ден.ед., полученного для исходной задачи.

Задание. Провести решение рассматриваемой задачи в новой постановке методом ДП.

• —>•—> Б

t | I

Tit

І І ї

A -> • -> •

Рис. 3.12

Замечание 5. В более сложных ситуациях могут возникать и более замысловатые конфигурации дорог минимальной стоимости. Например, на рис. 3.12 показан минимальный путь из пункта А в пункт Б длиной 11. Длины ребер, отмеченных стрелками, равны 1, длины остальных ребер равны 8. На практике реализация такого типа оптимальных решений приводит к дорожному «серпантину», часто встречающемуся в гористой местности.