Задачи выбора маршрута или сетевые задачи

Рассмотрим задачу: имеется конечный граф (I, D, G), каждой вершине i которого сопоставлено некоторое число bi, называемое интенсивностью вершины. Граф (I, D, G), вершинам которого сопоставлены значения интенсивностей bi, будем называть сетью. Если bi > 0, то вершина i называется источником, если bi < 0, то – стоком, а если bi = 0, то  –нейтральной вершиной. Множество источников, стоков и нейтральных вершин обозначим соответственно I+, I-, I0.

Для определенной выше сети потоком  называется такая совокупность величин, заданных на множестве дуг, Х={хd}d D, что 

где Di+ - множество дуг, исходящих из вершины i, a Di- - множество дуг, входящих в нее. Величина хd называется значением потока по дуге d и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.

Соотношение (3.11) означает, что для  любой вершины сети разность выходящего и входящего потоков равна  ее интенсивности.

На базе введенной терминологии может быть сформулировано много различных задач. Рассмотрим наиболее известные из них. Для каждой дуги d D определим значения cd ≥ 0, называемые стоимостью перемещения единицы продукта по дуге, тогда суммарная стоимость потока Х примет вид

Задачу минимизации  функции (3.13) при ограничениях (3.11)-(3.12) обычно называют линейной сетевой задачей. Очевидно, что она является задачей  линейного программирования. Если дополнительно для каждой дуги сети d D определить величины rd ≥ 0, называемые пропускными способностями, то, добавив ограничения 

мы получаем задачу о потоке в  сети с ограниченными пропускными способностями.

Приведенные формулировки задач специально даны в столь  абстрактном виде, что позволяет  подчеркнуть их универсальность. К очевидной сфере их приложения относится организация грузоперевозок в транспортной сети. В таких моделях вершины i трактуются как пункты, соединенные сетью дорог, и характеризуются потребностями в некотором продукте (bi<0) или его запасами (bi>0). Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки зрения полностью идентичны (3.11)-(3.13), (3.14), также называют транспортными задачами в сетевой постановке.

Классическим примером сетевых задач является определение кратчайшего пути между вершинами сети. Пусть задан граф (I, D, G), каждой дуге которого поставлено в соответствие число cd, называемое длиной. Также пусть выделены две вершины графа s и t, и требуется найти путь наименьшей длины, ведущий из вершины s в вершину t.

Если в графе имеются  «кратные» дуги, соединяющие одинаковые начало и конец, то достаточно оставить одну – с наименьшей длиной, а остальные отбросить. Таким образом, достаточно рассматривать задачу о кратчайшем пути для простого графа (I, D), в котором дуги определяются упорядоченными парами вершин d = (i, j). Тогда естественно путь L, идущий из вершины s в вершину t, задавать в виде упорядоченного набора вершин, через которые проходит данный путь:

 

а длины дуг обозначать как cd  = c_i,j.

Длина описанного выше произвольного  пути L определяется по формуле

Легко заметить, что задача о кратчайшем пути является частным случаем транспортной задачи в сетевой постановке (или, что то же самое, задачи об оптимальном потоке). Для этого достаточно присвоить вершине s единичный запас, вершине t единичную потребность, все остальные вершины положить нейтральными, а дугам присвоить неограниченные пропускные способности. Однако, как правило, более рациональным оказывается использование конкретных свойств данной задачи и решение ее специальными (частными) методами. К их числу относится, например, метод Минти, основные идеи которого мы изложим ниже.

Метод Минти решения  задачи о кратчайшем пути в сети представляет собой итеративный  процесс, в ходе которого строится путь L=(s=i0, i1, ..., ip-1, ip=t).

Стандартная итерация включает этапы:

1. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как  (на первой итерации  ={i0}). Для каждой вершины ищутся дуги, соединяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых i,j = 0. Найденные таким способом вершины j помечаются числом m_j = i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих i,j  = 0, заканчиваются в одной и той же вершине j, значение для ее пометки выбирается произвольно.

Если среди вновь  помеченных вершин окажется вершина t, то, значит, найден искомый путь (i0, i1,..., i(p-1), ip), где

 

на чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

2. Преобразование значений модифицированных длин дуг. Для каждой вершины ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятся

 

Далее модифицированные длины всех дуг, которые соединяют отмеченные вершины с неотмеченными ( , ), уменьшаются на величину

 

в результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.

Затем происходит переход  к следующей итерации.

Путь, построенный по методу Минти, будет кратчайшим. Это  можно доказать с помощью индукции по номеру итерации, на которой была помечена вершина t, или, что то же самое, по количеству дуг, составляющих кратчайший путь. Если это произошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение очевидно. Предположим,

 

 

что оно верно для  всех пунктов, помеченных за первые r итераций, т. е. тех, которые достигаются переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный путь также будет кратчайшим, так как данная вершина помечается в результате минимально возможного продолжения одного из путей, полученного за предыдущие r итераций и являющегося по предположению кратчайшим.

Отметим, что описанный  алгоритм пригоден для построения кратчайших путей на неориентированных графах.

Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.

На предварительном  этапе вершина 1 отмечается числом m1 = 0, а модифицированные длины совпадают  с заданными длинами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ∆ = min{1,2, 1,3}=2 и вычитаем ее из 1,2, 1,3. После преобразования имеем 1,2 = 0, 1,3 = 1.

Итерация 2. Помечаем вершину 2 m2 = 1 (см. рис. 3.6). Дальнейшая пометка  невозможна, поэтому переходим к  этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего определяем ∆ = min{1,3, 2,3, 2,4, 2,5}=1 и после соответствующего преобразования имеем

 

Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m3 = 1 (рис. 3.7). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ∆ = min{2,4, 2,5, 3,4, 3,5}=1 и после преобразования имеем 2,4 = 8, 2,5 = 0, 3,4 = 3, 3,5 = 5.

Итерация 4. Помечаем вершину 4 m4 =2 (см. рис. 3.8). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Из чего определяем ∆ = min{2,5, 3,5, 4,5, 4,6}=3 и после преобразования имеем 2,5 = 5, 3,5 = 0, 4,5 = 0, 4,6 = 5.

 

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же соображениями, что и на итерации 3, пометим вершину 5 числом m5=3 (рис. 3.9). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Из чего определяем ∆ = min{4,6, 5,6}=2 и после преобразования имеем 4,6 = 3, 5,6 = 0.

Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m6=5 (см. рис. 3.10). Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен, и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6) 

 

 

 

 

 

 

 

 

Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет несколько решений.

 

 

Алгоритм решения сетевых  задач.

 

 

Нахождение минимального остова в графе.

 

Алгоритм решения 

1. Упорядочить ребра графа по возрастанию весов;

2. Выбрать ребро с минимальным весом, не образующее цикл с ранее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;

3. Проверить, все ли вершины графа вошли в построенный остов. Если нет, то выполнить пункт 2.

 

Пример решения задач.

 

Требуется спроектировать радиотрансляционную сеть, которая должна обслуживать семь населённых пунктов. Расстояния между пунктами приведены в таблице.  

 

 

 

 

 

 

 

Решение

Для решения данной задачи достаточно рассмотреть или только левую или только правую часть  от главной диагонали матрицы. Воспользуемся левой частью таблицы.

Из элементов матрицы  выбираем минимальный - (D,С) = 4. Обводим  выбранный элемент кружком.  

 

 

 

 

 

 

Из оставшихся элементов  выбираем минимальный - (D,E) = 8. Элемент  обводим кружком. Чтобы выполнялось условие 2 пункты С и D не должны соединяться, поэтому элемент (Е,С) зачёркивается. 

 

 

 

 

 

 

 

 

Из невыделенных и  незачеркнутых элементов минимальным  является (D,B). Этот элемент обводится  кружком. Элементы (С,В) и (Е,В) зачёркиваются. 

 

 

 

 

 

 

 

Минимальным элементом является (С,А) = 13. Элементы (В,А), (D,А) и (Е,А) зачеркиваются. 

 

 

 

 

Из невыделенных и  незачеркнутых элементов минимальным  является (F,E) = 15. Элементы (F,A), (F,B), (F,C) и (F,D) зачёркиваются. 

 

 

 

 

 

 

 

 

В последней строке минимальным элементом является (G,E) = 18. Обводим этот элемент, и получаем остов, связывающий все семь пунктов. Все остальные элементы вычеркиваются. 

 

 

 

 

 

 

 

 

Длина минимального остова равна (С,А)+(D,B)+(D,С)+(Е,D)+(F,E)+(G,E) = 13+10+4+8+15+18 = 68.

 

 

Нахождение кратчайшего пути в графе.

 

Пусть дан граф, дугам  которого приписаны веса. Задача о  нахождении кратчайшего пути состоит  в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что  такой путь существует.

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый).

Данная задача может  быть разбита на две:

1. Для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;

2. Найти кратчайшие пути между всеми парами вершин.

 

Рассмотрим алгоритм решения для задачи:

Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).

1. I(s) = 0, I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s.

2. Для всех Хi, пренадлежащих Г(р) и пометки которых временны, изменить пометки по следующему правилу:

I(Xi) = min[I(Xi), I(p) + c(p, Xi)]

3. Среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]

4. Считать пометку вешины Хi* постоянной и положить р = Хi*.

5. Если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2.

Как только все пометки  расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) = I(Xi) (1).

 

Пример решения задачи.

 

Рассмотрим граф, изображенный на рисунке. Требуется найти все  кратчайшие пути от вершины Х1 ко всем остальным вершинам. Матрица весов  приведена ниже.

 

 

 

Решение:

 

I(X1)=0*, I(Xi)=∞, Xi≠X1, p=X1

1. Г{X1}=Г(X1)={X2,X7,X9}

I(X2)=min[∞, 0*+10]=10

I(X7)=min[∞, 0*+3]=3

I(X8)=min[∞, 0*+6]=6

I(X9)=min[∞, 0*+12]=12

min[I(X2), I(X3), I(X4), I(X5), I(X6), I(X7), I(X8), I(X9)]=3

X7:I(X7)=3*, p=3

2. Г{X7}=Г(X7)={X2,X4,X6,X9}

I(X2)=min[10, 3*+2]=5

I(X4)=min[∞, 3*+4]=7

I(X6)=min[∞, 3*+14]=17

I(X9)=min[12, 3*+24]=12

min[I(X2),I(X3),I(X4),I(X5),I(X6),I(X8),I(X9)]=5

X2:I(X2)=5*, p=5

3. Г{X2}=Г(X2)={X3,X9}