Детерминированные потоки в сетях. Задача о кратчайшей цепи. Алгоритм Дейкстры

ГЛАВА 1. ДЕТЕРМИНИРОВАННЫЕ ПОТОКИ В СЕТЯХ 1.1. ЗАДАЧА О КРАТЧАЙШЕЙ ЦЕПИ. АЛГОРИТМ ДЕЙКСТРЫ Одной из наиболее важных потоковых задач является задача нахождения цепи из источника в сток, минимизирующей стоимость (время) прохождения потока заданной величины по данной цепи. Пусть каждой дуге (i, j) ориентированной сети поставлено в соответствие некоторое число cij , называемое обобщенной стоимостью дуги. Фиктивным, или «бесплатным», дугам приписывается стоимость cij = 0, а каждой паре узлов (i, j), для которых не существует дуги, соединяющей их, приписывается стоимость cij =  . Задача состоит в нахождении в заданной сети такой цепи из источника s в сток t, для которой стоимость прохождения единицы потока по этой цепи минимальна. Математически эта задача может быть записана как следующая задача линейного программирования: минимизировать (1.1) при условии, что (1.2) (1.3) (1.4) Согласно первому равенству, единица потока вытекает из источника. Второе равенство гарантирует сохранение данной единицы потока при протекании по сети. Согласно третьему равенству, единица потока втекает в сток. В качестве кратчайшей цепи может быть взята последовательность смежных дуг (i, j), для которых fij = 1. Сформулированная задача линейного программирования может быть решена специальным методом, известным под названием алгоритма Дейкстры. Пусть, стоимость каждой дуги, или расстояние между двумя узлами, выражается неотрицательным числом cij. Алгоритм основан на приписывании узлам либо временных, либо постоянных пометок. Первоначально каждому узлу, исключая источник, приписывается временная пометка, соответствующая длине кратчайшей дуги, ведущей из источника в данный узел. Источнику приписывается постоянная пометка, значение которой равно нулю. Каждому узлу, в который нельзя попасть непосредственно из источника, приписывается временная пометка , а всем остальным узлам – временные пометки cij, j  s. Если определено, что узел принадлежит кратчайшей цепи, его пометка становится постоянной. Если известна кратчайшая цепь из узла s в узел j и узел k принадлежит этой цепи, то кратчайшая цепь из s в k является частью первоначальной цепи, оканчивающейся в узле k. Алгоритм начинает работать при j = s. Затем величина j последовательно увеличивается на единицу, и при j = t алгоритм завершает работу. 1.1.1. ИТЕРАТИВНАЯ ПРОЦЕДУРА Пусть для заданного узла j j - оценка длины кратчайшей цепи из источника s в узел j. Если эта оценка не может быть улучшена, то соответствующее значение называется “постоянной пометкой” и обозначается символом j . В противном случае оно называется “временной пометкой”. Вначале процедуры постоянная пометка приписывается только источнику. Каждая другая пометка является временной и ее величина равна длине дуги, ведущей из источника в соответствующий узел. Для определения ближайшего к источнику узла выбирается временная пометка с минимальным значением и объявляется постоянной пометкой. Затем, до тех пор, пока стоку не будет приписана постоянная пометка, необходимо выполнять следующие две процедуры: 1. Рассмотреть оставшиеся узлы с временной пометкой. Сравнить величину каждой временной пометки с суммой величины последней из постоянных пометок и длины дуги, ведущей из соответствующего постоянно помеченного узла в рассматриваемый узел. Минимальная из двух сравниваемых величин определяется как новая временная пометка рассматриваемого узла. Если величина старой временной пометки меньше второй из сравниваемых величин, то пометка остается прежней. 2. Среди временных пометок выбрать ту, значение которой минимально, и объявить ее постоянной пометкой. Если при этом постоянная пометка приписывается узлу t, то алгоритм завершает работу. В противном случае перейти на шаг 1. Данная процедура может быть выполнена с помощью таблицы решения, в которой столбцы соответствуют узлам сети, строки – шагам итеративного процесса, а ее элементы – постоянным и временным пометкам. 1.1.2. ПРИМЕР, ИЛЛЮСТРИРУЮЩИЙ РАБОТУ АЛГОРИТМА ДЕЙКСТРЫ Пример, иллюстрирующий работу алгоритма Дейкстры, изображен на рис. 2.11. Узел s здесь является источником, t – стоком, а числа cij, приписанные дугам, соответствуют их длинам или стоимости. Рис. 1.1. Сетевая модель для иллюстрации алгоритма Дейкстры Работа алгоритма начинается с того, что источнику s приписываются постоянная пометка 0, а узлам j=1, 2,…, 6, t – временные пометки j = cij. Таким образом, 1 = 0 и j =  для j= 2,…, t. Поскольку значение 1 = 0 является минимальным среди всех временных пометок, узлу 1 приписывается постоянная пометка 0. Узлы 2 и 3 непосредственно связаны с узлом 1, последним из постоянно помеченных узлов. Кроме того, 1 + c12 = 0 + 3 <  и 1 + c13 = 0 + 7 < . Поэтому узлам 2 и 3 приписываются новые временные пометки 2 = 3 и 3 = 7 соответственно. Поскольку 2 < 3 , узлу 2 приписывается постоянная пометка 2 = 3. Узлы 3 и 6 непосредственно связаны с узлом 2. Кроме того, 2 + c23 = 3 + 2 = 5 < 7 и 2 + c26 = 3 + 1 = 4 < . Поэтому узлам 3 и 6 приписываются новые временные пометки 6 = 4 и 3 = 5 соответственно. Поскольку 6 < 3 , узлу 6 приписывается постоянная пометка 6 = 4. На данном шаге временными являются пометки 4 = 5 = t = . Последним узлом, которому была приписана постоянная пометка, является узел 6. Он непосредственно связан только с узлом 4. 6 + c64 = 4 + 2 = 6 <  , следовательно, узлу 4 приписывается новая временная пометка 4 = 6 . Поскольку 3 = min {3 , 4 , 5 , t }, узлу 3 приписывается постоянная пометка 3 = 5. Алгоритм заканчивает работу, когда узлу t приписывается постоянная пометка. Промежуточные результаты, полученные при решении данной задачи, приводятся в табл. 1.1. Таблица 1.1 Шаг/ Узел s 1 2 3 4 5 6 t 0        1 0 0       2 0 0       3 0 0 3 7     4 0 0 3 7     5 0 0 3 5   4  6 0 0 3 5   4  7 0 0 3 5 6  4  8 0 0 3 5 6  4  9 0 0 3 5 6 9 4  10 0 0 3 5 6 9 4  11 0 0 3 5 6 7 4  12 0 0 3 5 6 7 4  13 0 0 3 5 6 7 4 7 14 0 0 3 5 6 7 4 7 Как видно из табл. 1.1, узлу t приписывается постоянная пометка t = 7. Следовательно, длина кратчайшей цепи из узла s в узел t равна 7. Эта цепь состоит из дуг, для каждой из которых разность между значениями постоянных пометок ее концевых узлов равна длине этой дуги. Иными словами, если i и j - постоянные пометки узлов i и j соответственно, то условие, при выполнении которого эти узлы принадлежат кратчайшей цепи, может быть записано следующим образом: j=i +cij. Это соотношение можно использовать рекурсивно, двигаясь от узла t к узлу s. Определив узел, непосредственно предшествующий t в кратчайшей цепи, данную процедуру нужно повторять до тех пор, пока не будет достигнут узел s. Кратчайшая цепь в рассмотренной сети образуется последовательностью узлов s-1-2-6-4-5-t. 1.2.  ЗАДАЧА О МНОГОПОЛЮСНОЙ КРАТЧАЙШЕЙ ЦЕПИ Рассматривается задача нахождения кратчайших цепей между всеми парами узлов сети G=(N, А). Если длина каждой дуги соответствует расстоянию или стои­мости единицы потока по этой дуге, то кратчайшей цепью между двумя произвольными узлами является цепь, стоимость единицы потока по которой минимальна. Дуги из множества А могут быть ориентированными и неориентированными. Однако, поскольку направление потока в неориентированных дугах нельзя определить заранее, то каждую такую дугу следует за­менить двумя ориентированными дугами с противоположны­ми направлениями и длинами, равными длине неориентирован­ной дуги. Предполагается, что длины дуг могут быть как положитель­ными, так и отрицательными. Однако длина, или стоимость, каждого цикла или контура должна быть неотрицательной. Алгоритм решения такой задачи первоначально был разработан Флойдом, а затем усовершенство­ван Xy. Пусть N={1, 2, …, n } - множество узлов, а сij —длина, или количест­венный параметр, дуги (i, j), направленной от узла i к узлу j. Обозначим через d*ik длину кратчайшей цепи из узла i в узел k. Пусть величина dik представляет наилучшую оценку длины кратчайшей цепи, соединяющей узлы i и k. Тогда либо длина ik=dij+djk каждой кратчайшей цепи, проходящей через промежуточный узел i, превосходит величи­ну dik, либо текущая длина кратчайшей цепи равна ik. Однако если длина dik новой цепи меньше ik, то текущее значение dik следует заменить на ik. Алгоритм Флойда работает сле­дующим образом. Первоначально за длину кратчайшей цепи между двумя произвольными узлами i и k принимается дли­на дуги (i, k), соединяющей эти узлы. 3атем последовательно проверяются всевозможные промежуточные узлы, расположен­ные между i и k. Если длина цепи, проходящей через некото­рый промежуточный узел, меньше текущего значения dik, то переменной dik присваивается новое значение. Данная процеду­ра повторяется для всевозможных пар узлов, пока не будут получены все значения d*ik. Для любых трех различных узлов i, j и k сформулирован­ные выше условия могут быть записаны в виде неравенства dij+djk  dik; i  j  k, (1.5) поскольку в противном случае кратчайшая цепь из узла i в узел r должна содержать узел j и тогда величина dik не была бы равной длине кратчайшей цепи. В алгоритме Флойда началь­ным значением переменной dik является величина cik, а затем данная оценка последовательно улучшается до тех пор, пока не будет найдена кратчайшая цепь между узлами i и k. Рис. 1.2 иллюстрирует выполнение процедуры сравнения для пары узлов i и r. Если dik > dij + djk , то значение dik заменяется значением dij+djk текущая оценка расстояние от расстояние от длины кратчайшей узла i до узла j узла j до узла k цепи между узлами i и k Рис 1.2. Пример процедуры сравнения, выполняемой при работе алгоритма Флойда. 1.2.1. ИТЕРАТИВНАЯ ПРОЦЕДУРА Алгоритм Флойда позволяет решать задачу о многополюс­ной кратчайшей цепи (пути) для сети из n узлов за n итера­ций. Для того чтобы перейти к формальному описанию итеративной процедуры поиска решения, обозначим символом djik оценку длины кратчайшей цепи из узла i в узел k, полученную на j-й итерации. Способ получения на j-и итерации величины djik может быть описан с помощью следующей трехместной операции: dikj = min[dikj-1; dijj-1 + djkj-1], i  j  k. (1.6) Если трехместную операцию, определенную выражением (1.6), выполнять с данной парой узлов i и k и всеми узлами j (i  j  k) в порядке возрастания номеров j, то значение dnik, полученное на последней итерации, будет равно длине кратчайшей цепи из узла i в узел k. На каж­дой итерации алгоритма строятся две матрицы. Первая из них, называемая матрицей длин кратчайших путей, содержит теку­щие оценки длин кратчайших цепей, т. е. на j-й итерации дан­ная матрица определяется как Dj= [djik]. Алгоритм начинает работу при D°=[d°ik], где d°ik=cik. Затем, в результате выполнения трехме­стной операции (1.6) со всеми элементами матрицы D°, по­лучается D1 и т. д. до тех пор, пока для каждой пары узлов не будет выполнен критерий оптимальности (1.5). Вторая матрица, называемая матрицей маршрутов, служит для нахождения промежуточных узлов (если таковые имеются) кратчайших цепей. На j-й итерации она определяется как Rj=[rjik.], где rjik - первый промежуточный узел кратчайшей цепи из i в k, выбираемый среди узлов множества {1,2,...,j} (i  j  k). Алгоритм начинает работу при R°= [r°ik], где r°ik=k. На j-й итерации узел rjik может быть получен из сле­дующего соотношения: (1.7) После построения матриц D° и R° нужно для каждого j=1, 2,..., n, используя для вычислений элементы матрицы Dj-1, полученной на (j—1)-й итерации, выполнить следующую процедуру: Шаг 1. Вычеркнуть элементы j-й строки и j-го столбца, которые называются базовой строкой и базовым столбцом соответственно. Шаг 2. Каждый элемент dikj-1 (k  1) матрицы расстояний (начиная с первого элемента, т. е. расположенного в левом верхнем углу матрицы), который не принадлежит ни базовой строке, ни базовому столбцу, сравнить с суммой элементов djkj-1 и dijj-1 базовой строки и базового столбца соответст­венно. Если выполняется неравенство dijj-1 + djkj-1  dikj-1, то вы­брать новые значения для i и k, перейти к следующему элементу dikj-1 и снова выполнить шаг 2. Если dikj-1 > dijj-1 + djkj-1, то элементу dikj-1 матрицы длин кратчайших путей присвоить значение dikj = dijj-1 + djkj-1, а соответствующему элементу матрицы маршрутов - значение, равное j. После просмотра всех элементов вновь перейти к выполнению шага 1 при j = j + 1. При j = n будут построены матрица расстояний и матрица маршрутов, представляющие решение задачи. Согласно (1.6), при получении Dj из Dj-1 трехместную операцию, позволяющую установить факт принадлежности ба­зового узла кратчайшей цепи, следует выполнять только с эле­ментами матрицы Dj-1, не принадлежащими ни базовой стро­ке, ни базовому столбцу. При исследовании каждого элемента dikj-1 (i, j  k) может быть использована процедура, похожая на симплекс-метод. После того как выбран элемент dikj-1, замену производить не следует, если dikj-1 = ∞ и одно из двух значе­ний dijj-1 или djkj-1 равно ∞. Если dikj-1  ∞ и одно из двух зна­чений dijj-1 или djkj-1 превосходит dikj-1, то замену также производить не следует. Поэтому необходимо рассмотреть лишь случаи, когда dikj-1  ∞ и оба значения dijj-1 и djkj-1  ∞ меньше dikj-1. Таким образом, для выполнения каждой итерации необходимо руководствоваться следующими правилами, позволяющими упростить вычисления: 1. dijj-1 = ∞, т. е. i-й элемент базового столбца равен ∞. Из (1.6) следует, что в данном случае значение dikj должно оста­ваться равным dikj-1 . Поэтому трехместную операцию выпол­нять не нужно. 2. djkj-1 = ∞, т. е. j-й элемент базовой строки равен ∞. Из (1.6) следует, что в данном случае значение dikj должно оста­ваться равным dikj-1. Поэтому трехместную операцию выпол­нять не нужно. Рассматриваемый алгоритм может быть описан в виде по­следовательности двух шагов вычислений. Начальные значе­ния D° и R° для итеративного выполнения этик шагов определя­ются по формулам D°=[сik], R°=[k], а параметру j присваивается начальное значение, равное нулю. Данный параметр используется для обозначения базового узла на каждой итерации. Шаг 1. j=j+1, определить узел j как базовый узел и вычерк­нуть базовую строку и базовый столбец матрицы Dj-1. Вычерк­нуть также строки и столбцы матрицы Dj-1, содержащие те элементы, равные ∞, которые принадлежат базовой строке или базовому столбцу. Шаг 2. Сравнить каждый невычеркнутый элемент dikj-1 с сум­мой следующих двух элементов: а) элемент dijj-1, расположенный на пересечении базового столбца и строки, содержащей dikj-1, б) элемент djkj-1, расположенный на пересечении базовой строки и столбца, содержащего dikj-1. Если сумма этих двух элементов меньше dikj-1, то положить dikj = dijj-1 + djkj-1, rikj = j. В противном случае положить dikj = dikj-1, rikj = rikj-1. После того как будут рассмотрены все невычеркнутые элементы матрицы Dj-1, проверить выполнение условия j = n. Если оно выполнено, то работа алгоритма завер­шается, в противном случае перейти к шагу 1. 1.2.2. ПРИМЕР ЗАДАЧИ О МНОГОПОЛЮСНОЙ КРАТЧАЙШЕЙ ЦЕПИ Для иллюстрации работы алгоритма Флойда найдем крат­чайшую цепь между всеми парами узлов сети, изображенной на рис. 1.3. Начальные значения элементов матрицы длин кратчайших путей и матрицы маршрутов могут быть выбра­ны так, как это показано ниже. Поскольку n = 8, число ите­раций в алгоритме также равно 8. Рис. 1.3. Сеть в задаче о многополюсной кратчайшей цепи , Итерация 1. Узел j=1 определяется как базовый, поэтому в матрице D° вычеркивается первая строка и первый столбец. Кроме того, столбцы 3, 5, 6, 7 и 8 содержат элемен­ты, равные ∞ и принадлежащие базовой строке, а строки 3, 5, 6, 7 и 8 содержат элементы, равные ∞ и принадлежащие ба­зовому столбцу. Поэтому, для того чтобы определить, приве­дет ли использование узла 1 к более коротким цепям, следу­ет исследовать (с помощью трехместной операции) лишь эле­менты матрицы D°, изображенные на рис. 1.4. 1 2 3 4 5 6 7 8 1 9 3 - базовая строка 2 9 ∞ 3 4 3 ∞ 5 6 7 8 Базовый столбец Рис. 1.4. Элементы, исследуемые (с помощью трехместной операции) на первой итерации. Поскольку диагональные элементы матрицы D° можно не рассматривать, необходимо исследовать лишь оценки d°24 и d°42. Применение трехместной операции дает следующие ре­зультаты: d124=min[d°24;d°21+d°14]=min[∞;9+3]=12, d142=min[d°42;d°41+d°12]=min[∞;3+9]=12. Оценки d124=12 и d142=12 лучше оценок d°24 =∞ и d°42=∞ соответственно. Поскольку использование ба­зового узла приводит к более коротким цепям из узла 2 в узел 4 и из узла 4 в узел 2, то r124=1 и r142=1. Все остальные элементы матриц D° и R° остаются без изменения. Теперь матрицы D1 и R1 имеют вид: , Итерация 2. Узел j=2 - базовый, в матрице D1 вычеркивается вторая строка и второй столбец. Кроме того, столбцы 6, 7 и 8 содержат элементы, равные ∞ и принадле­жащие базовой строке, а строки 6, 7 и 8 содержат элементы, равные ∞ и принадлежащие базовому столбцу. Поэтому, для того чтобы определить, приведет ли использование узла 2 к более коротким цепям, следует исследовать (с помощью трех­местной операции) лишь элементы матрицы D1, изображенные на рис. 1.5. Поскольку диагональные элементы матрицы D1 можно не рассматривать, то необходимо исследовать элементы d113, d114, d115, d131, d134, d135, d141, d143, d145, d153 и d154. Улучшены могут быть только оценки d113, d115, d131, d145, d151 и d154. Новые оценки получаются следующим обра­зом: 1 2 3 4 5 6 7 8 1 9 ∞ 3 ∞ - базовая строка 2 9 2 12 7 3 ∞ 2 2 4 4 3 12 2 ∞ 5 ∞ 7 4 ∞ 6 7 8 Базовый столбец Рис. 1.5. Элементы, исследуемые (с помощью трехместной операции) на второй итерации. d213=min[d113;d112+d123]=min[∞;9+2]=11, d215=min[d115;d112+d125]=min[∞;9+7]=16, d231=min[d131;d132+d121]=min[∞;2+9]=11, d245=min[d145;d142+d125]=min[∞;12+7]=19, d251=min[d151;d152+d121]=min[∞;7+9]=16, d254=min[d154;d152+d124]=min[∞;7+12]=19. Таким образом, r213 = r215 = r231 = r245 = r251 = r254 = 2 и r2ik = r1ik для всех элементов, таких, что d2ik = d1ik. Новые матри­цы D2 и R2 имеют вид: , Результаты аналогичных вычислений на итерациях 3, 4, 5, 6, 7, 8 приведены в табл. 1.2. Оценки, полученные на итерациях 6, 7 и 8, не могут быть улучшены. Следовательно, оптимальное решение соответствует матрицам D5 и R5. Таблица 1.2. Итерация j Dj Rj 3 4 5 6 Остается неизменной Остается неизменной 7 Остается неизменной Остается неизменной 8 Остается неизменной Остается неизменной Для иллюстрации ре­зультатов, приведенных в табл. 1.2, рассмотрим кратчайшую цепь из узла 1 в узел 5. Длина этой цепи равна d515=9. Для того чтобы найти соответствующую последовательность узлов, обратимся к матрице R5. Поскольку значение r515 равно 4, то узел 4 является первым промежуточным узлом в кратчайшей цепи из узла 1 в узел 5. Затем, для того чтобы найти узел, следующий за узлом 4 в цепи, ведущей к узлу 5, мы опреде­ляем значение r545. Данное значение равно 3. Точно так же, поскольку r535=б, узел 5 следует за узлом 3. Следовательно, кратчайшая цепь из узла 1 в узел 5 определяется последова­тельностью узлов 1, 4, 3, 5. 1.3. АНАЛИЗ АЛГОРИТМОВ КРАТЧАЙШИХ ПУТЕЙ Проведение анализа вычислительных алгоритмов имеет практическое и теоретическое значение. Для практических целей нужно знать оценки объема требуемой машинной памяти и времени прохождения программы. Теоретическую ценность имеют количественные критерии, позволяющие проводить сравнения нескольких алгоритмов решения одной задачи. В алгоритмах Дейкстры и Флойда выполняется только два типа элементарных операций – сложение и сравнение. Обычно предполагается, что время выполнения этих двух операций приблизительно одинаковое и что в наихудшем случае при работе алгоритма выполняется максимально возможное число элементарных операций. Это число называется вычислительной сложностью алгоритма и является функцией размера сети и количества искомых путей. 1.3.1. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ МЕТОДА ДЕЙКСТРЫ Пусть сеть G = (N, А), содержит n узлов, образу­ющих множество N. В наихудшем случае конечный узел сети будет n-м по счету узлом, которому приписывается постоянная пометка. В некоторый заданный момент ра­боты алгоритма m узлам приписаны постоянные пометки, а n - m узлам - временные пометки. Для определения (m+1)-го узла, которому должна быть приписана постоянная пометка, необходимо вычислить новые величины n – m временных поме­ток, выполняя при этом для каждой из них операцию сложения и операцию сравнения. После вычисления новых значений временных пометок необходимо также найти минимальное сре­ди них, чтобы определить пометку, которая должна стать по­стоянной. Данная процедура минимизации состоит из n – m – 1 операций сравнения. Таким образом, если имеется m узлов с постоянными пометками, то число элементарных операций, ко­торое необходимо выполнить для того, чтобы еще одному узлу приписать постоянную пометку, равно 3(n - m) – 1  3 (n – m). Общее число элементарных операций, выполнение которых необходимо для завершения работы алгоритма, в наихудшем случае равно (1.8) 1.3.2. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ АЛГОРИТМА ФЛОЙДА Для сети G = (N, А), где N = {1, 2, ..., n} на каж­дой итерации алгоритма суммарное число элементов, значение которых должно быть оценено с помощью трехместной опера­ции (1.6), вычисляется, исходя из следующих соображе­ний: 1. Общее число элементов матрицы равно n2. 2. Суммарное число элементов в базовой строке и базовом столбце равно 2n - 1. 3. Число нулевых элементов на главной диагонали равно n и для каждого из них не надо получать новую оценку. 4. Один элемент базовой строки и один элемент базового столбца расположены на главной диагонали. 5. Анализ каждого элемента требует выполнения одной операции сложения и одной операции сравнения, соответствую­щих трехместной операции. 6. Таким образом, максимальное число операций, выполняе­мых на одной итерации алгоритма, приблизительно равно 2n(n – 3). Поскольку число итераций равно n, то общее число элементарных операций равно 2n2(n – 3). 1.4. ЗАДАЧА О КРАТЧАЙШЕМ ОСТОВНОМ ДЕРЕВЕ Задача о кратчайшем остовном дереве имеет широкое практическое применение. Она возникает при про­ектировании распределительных систем, транспортных сетей, когда требуется найти реше­ния, минимизирующие затраты. Построение кратчайшего остова часто встречается в зада­чах субоптимизации, или декомпозиции, сложных сетевых алго­ритмов. Помимо того, что данная задача имеет большое прак­тическое значение, метод ее решения является уникальным в исследовании операций. 1.4.1. АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ОСТОВНОГО ДЕРЕВА В рассмотренных выше потоковых алгоритмах были исполь­зованы рекуррентные схемы вычислений, позволяющие строить последовательность решений, сходящуюся к оптимальному ре­шению. Задача о кратчайшем остове является од­ной из немногих задач исследования операций, которые могут быть решены с помощью «поглощающих» алгоритмов, являю­щихся весьма экономичными. Задача о кратчайшем остове заклю­чается в выборе таких дуг заданной сети, что их суммарная стоимость минимальна и для любой пары узлов найдется путь (или маршрут), соединяющий их. Этого можно достигнуть, вы­бирая дуги таким образом, что образованное ими дерево покроет, или соединит, все узлы заданной сети. Алгоритм начинает работу с выбора произвольного узла сети и кратчайшей дуги из множества дуг, соединяющих этот узел с другими узлами. Два узла соединяются выбранной дугой. Вы­бирается ближайший к этим узлам третий узел. Этот узел и соответствующая дуга добавляется к сети. Данный процесс продолжается до тех пор, пока все узлы не будут соединены между собой. Алгоритм, основанный на «поглощении» кратчайших дуг, может быть описан следующим образом. Алгоритм построения кратчайшего остова Шаг 1. Используя узлы исходной сети, определить следующие два множества: S-множество соединенных узлов; —мно­жество несоединенных узлов. Вначале все узлы принад­лежат множеству . Шаг 2. Выбрать произвольный узел из и соединить его с ближайшим соседним узлом. (После выполнения данного шага множество S будет содержать два узла.) Шаг 3. Среди всех дуг, соединяющих узлы из множества S с узлами из множества , выбрать кратчайшую дугу. Концевой узел этой дуги, лежащий в , обозначить через . Удалить узел из множества и поместить его в множество S. Шаг 4. Выполнять шаг 3 до тех пор, пока все узлы не будут принадлежать множеству S. 1.4.2. ПРИМЕР ПОИСКА РЕШЕНИЯ С ПОМОЩЬЮ «ПОЕДАЮЩЕГО» АЛГОРИТМА Рис. 1.6. Пример сети в задаче о кратчайшем остове Шаг 1. = (1, 2, 3, 4, 5, 6, 7), S=0. Шаг 2. Выбрать узел 6. S=(6, 5), =(0,2.3,4,7). Стоимость = 1 ед. Шаг 3. а. Выбрать узел 3. S=(6,5,3), = (1,2,4,7). Шаг 3а Стоимость = 4 ед. б. Выбрать узел 4. S=(6,5,3,4), =(1,2,7). Шаг 3б Стоимость = 5 ед. в. Выбрать узел 2. S=(6,5,3,4,2), =(1,7). Шаг 3в Стоимость = 7 ед. г. Выбрать узел 1. S=(6,5,3,4,2,1), =(7). Шаг 3г Стоимость = 9 ед. д. Выбрать узел 7. S=(6,5,3,4,2,1,7), =0. Шаг 3д Стоимость = 14 ед. Алгоритм заканчивает работу, поскольку =0. Стоимость кратчайшего остова равна 14. Задача о кратчайшем остовном дереве находит широкое практическое применение. Многие задачи, на первый взгляд не похожие на задачц о кратчайшем остове, после некоторых преобразований сводятся к ней. Нпример, посроение кратчайшего остова позволяет оценить надежность сетей – вес кратчайшего остова соответствует минимальной вероятности того, что дерево будет повреждено в одной или нескольких дугах. Гомори и Ху использовали алгоритм построения кратчайшего остова при решении задач о многополюсных потоках. Хелд и Карп нашли аналогичное применение этой задачи для решения задачи коммивояжера. Но наиболее интересное и важное применение задача о кратчайшем остове находит в кластерном анализе, где ряд задач наиболее эффективно решается с помощью построения кратчайшего остова. Контрольные вопросы к главе 1 1. Почему методы сетевого анализа являются более предпочтительными по сравнению с другими методами исследования операций? Указать четыре причины. 2. Дать определение следующих понятий: дуга, узел, ориентированная дуга, биориентированная дуга, неориентированная дуга, источник, сток, главный источник, главный сток. 3. Дать определение цепи и пути. В чем различие между ними? 4. Дать определение цикла и контура. В чем различие между ними? 5. Дать определение дерева и остовного дерева. 6. Может ли минимальное остовное дерево содержать циклы? 7. Может ли кратчайший путь между двумя узлами в сети с циклами содержать циклы? 8. Следует ли заново начать решение задачи методом Дейкстры, если на одной из промежуточных итераций при определении постоянной пометки была допущена ошибка, которая не была обнаружена до завершения решения задачи? 9. Привести несколько примеров практического использования задач о пути максимальной длины. Указать условия, при выполнении которых задача о пути максимальной длины может быть сведена к эквивалентной задаче о кратчайшем пути? 10. При работе каких алгоритмов о кратчайшем пути вначале определяются длины путей, а затем используются процедуры трассировки для нахождения самих путей? В чем преимущество таких алгоритмов по сравнению с алгоритмами, в которых длины путей и сами пути определяются одновременно? 11. В настоящей главе был описан вариант метода Дейкстры, в котором предполагается, что все параметры дуг неотрицательные. Модифицировать данный алгоритм таким образом, чтобы он был применим к сетям, содержащим дуги с отрицательными параметрами. Какое условие в данном случае имеет решающее значение? 12. Объяснить, почему число итераций в алгоритме Флойда равно числу узлов в сети. 13. Могут ли в алгоритме Флойда параметры дуг принимать отрицательные значения? 14. Объяснить, почему эффективность алгоритма Флойда может зависеть от порядка нумерации узлов. 15. При каких условиях неориентированная дуга, соединяющая узлы i, j, может быть заменена двумя ориентированными дугами с той же пропускной способностью, что и у исходной дуги? В каких случаях такая замена невозможна? Привести соответствующие примеры. Упражнения к главе 1 1.1. На изображенной ниже сети параметр каждой дуги соответствует стоимости единицы потока по этой дуге. Найти: а) путь минимальной стоимости из узла 1 в узел 13; б) пути минимальной стоимости между всеми парами узлов. Рис. к упр. 1.1. 1.2. Предположим, что в упражнении 1 стоимость единицы потока по дуге (12, 13) уменьшена вдвое. Можно ли найти путь минимальной стоимости, используя полученные ранее результаты? 1.3. Предположим, что в упражнении 1 дуга (4, 5) должна быть включена в путь минимальной стоимости. Найти решение данной задачи. Как изменится процедура решения, если знать о данном ограничении заранее? 1.4. На изображенной ниже сети параметр каждой дуги соответствует стоимости единицы потока по этой дуге. Найти: а) путь минимальной стоимости из узла 1 в узел 10; б) пути минимальной стоимости из узлов 1 и 2 в узлы 10, 11, 12. Рис. к упр. 1.4. 1.5. Построить минимальные остовные деревья изображенных ниже сетей. Рис. к упр. 1.5. 1.6. Решить задачи 3.1 – 3.7, 3.23 из «Сборника задач по курсам «Математическое моделирование», «Методы оптимизации».