15. Оптимизационные алгоритмы

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

1. Кратчайшие пути.

2. Оптимальные деревья.

3. Паросочетания в графе.

4. Потоки в сетях.

5. Оптимальные ветвления.

15.1. Кратчайшие пути

Пусть G — связный ориентированный граф, в котором каждому ориентированному ребру сопоставлено положительное вещественное число, называемое длиной ребра. Длина ребра, направленного из вершины i в вершину j, обозначается через Если в графе отсутствует ребро, направленное из вершины i в вершину то Длина ориентированного пути в графе G — это сумма длин ребер, входящих в путь. Ориентированный s — -путь, имеющий минимальную длину, называется кратчайшим путем из s в Длина кратчайшего ориентированного s — -пути называется расстоянием из s в t и обозначается через Ясно, что для любого i. В этом разделе мы рассмотрим следующие задачи:

1. Найти кратчайшие пути из данной вершины s ко всем другим вершинам графа

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

Эти две задачи возникают в нескольких проблемах оптимизации. Например, определение потока минимальной стоимости в транспортной сети включает определение кратчайшего пути из источника до стока сети [15.1].

15.1.1. Кратчайшие пути из данной вершины S ко всем другим вершинам графа

Рассмотрим алгоритм Дейкстры [15.2], который определяет кратчайшие пути из данной вершины ко всем другим вершинам связного ориентированного графа на вершинах. Следующее соображение составляет основу алгоритма Дейкстры.

Пусть V — множество вершин графа такое подмножество V, что Обозначим через S дополнение S до V. Таким образом,

Пусть Р — путь минимальной длины среди всех ориентированных путей из s к вершинам в S. Длина пути Р называется расстоянием от s до S. Пусть . Тогда ясно, что Далее, часть пути Р из s в и должна быть наикратчайшим s — -путем, вершины которого принадлежат S. Поэтому Отсюда видно, что расстояние можно вычислить по формуле

Тогда еслиу? S такое, что для некоторого , то

Алгоритм Дейкстры порождает последовательность таких подмножеств V, что выполняются следующие условия:

1. Если — такие вершины из множества V, что для

2. Когда множество определено, известны и кратчайшие пути из s в Для множеств определенных выше соотношением (15.2), справедливо равенство

Таким образом, построение по включает в себя вычисление Подмножества можно построить в соответствии с выражением (15.1) следующим образом:

Следовательно, согласно формуле (15.3), — вершина, для которой выполняется равенство

Если — кратчайший путь из вершины s к вершине то .

Предположим, что подмножества и пути уже определены. Тогда для определения мы вычисляем

используя выражение (15.1). Из равенства (15.3) следует, что вершина в обладающая свойством

Из выражения (15.1) следует, что существует такая вершина что Поэтому мы можем получить присоединяя ребро к пути

Если нам необходимо получить кратчайший путь только до другой данной вершины t, то мы можем завершить вычисления после получения первого множества которое содержит

Ясно, что в этой процедуре необходимо вычислять минимум в выражении (15.1) на каждом этапе. Если этот минимум действительно вычислялся бы на каждом этапе, то определение по потребовало бы сложений и сравнений. Общее число операций для выполнения всего алгоритма составило бы т. е. в общей сложности шагов.

Однако многие из этих сложений и сравнений не обязательно должны каждый раз повторяться.

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

для всех . Ясно, что — вершина, для которой Теперь мы можем определить

Тогда выбирается так, что

Отметим, что метка и, не меняется после определения .

Таким образом, алгоритм Дейкстры начинает работу с меток для всех . По мере выполнения алгоритма

метки модифицируются в соответствии с выражением (15.5). Метки определяют расстояние от s до .

Ясно, что определение включает вычисление для всех и последующее нахождение минимума среди этих меток. Для

1 первое вычисление по формуле (15.5) требует сложений и сравнений, тогда как последние действия по формуле (15.6) требуют сравнений. Таким образом, ясно, что сложность алгоритма Дейкстры равна

Представим описание алгоритма Дейкстры. В этом описании LABEL — это массив, в котором хранятся текущие метки вершин. Вершины становятся постоянно помеченными, когда они оказываются равными для какого-либо i. Мы используем массив PERM, чтобы указать, какие вершины постоянно помечены. Если то v является постоянно помеченной вершиной. Отметим, что в таком случае метка v равна Вначале для всех

PRED — массив указателей на вершины, из которых осуществлен переход в вершины с неизменной меткой. Если вершина v помечена неизменной меткой, то есть вершины, составляющие кратчайший ориентированный путь из s в V.

Алгоритм 15.1. Кратчайшие пути (Дейкстра).

S0. G — данный ориентированный граф с взвешенными ребрами. Требуется найти кратчайшие пути из вершины s во все остальные вершины графа

S1. (Начало.) Положить LABEL Для всех положить LABEL

S2. Пусть — последняя из вершин с неизменной меткой. Теперь — это вершина )

S3. (Вычисление LABEL и изменение элементов массива PRED). Положить Выполнить для каждой вершины, кроме вершин с неизменной меткой, следующие действия: 1) Положить Если то положить LABEL

S4. (Выделение вершины ) Среди всех вершин, которые не помечены неизменной меткой, найти вершину w с наименьшей меткой. (Если таких вершин несколько, то выбор можно сделать произвольно.) Положить и она является последней вершиной с неизменной меткой.)

S5. Если то идти к шагу Иначе HALT. (Все кратчайшие пути найдены). Метки вершин представляют собой длины кратчайших путей. есть вершины кратчайшего ориентированного -пути.

Отметим, что в программе для вычислительной машины представляется достаточно большим числом. Если конечная метка вершины v равна то это означает, что не существует ориентированного пути из s в и.

Чтобы проиллюстрировать работу алгоритма Дейкстры, рассмотрим граф на рис. 15.1, на котором длины ребер указаны рядом. На рис. 15.2 изображены элементы массивов LABEL и PRED.

Рис. 15.1.

Рис. 15.2. Иллюстрация к алгоритму Дейкстры (массив LABEL изображен на рис. а).

Для любого i элементы массива LABEL, обведенные кружком, соответствуют вершинам, помеченным неизменной меткой, а именно вершинам из множества Элементы, помеченные звездочкой, являются метками последних вершин, помеченных неизменной меткой, а именно вершин Кратчайшие пути из s и соответствующие

расстояния получаются из конечных значений элементов массивов PRED и LABEL.

При обсуждении алгоритма мы предполагали, что все длины неотрицательны. Алгоритм Дейкстры неприменим, если какие-либо из длин отрицательны (почему?). Однако некоторая модификация этого алгоритма делает его применимым для более общего случая, когда в графе нет ориентированных циклов с отрицательной длиной. Джонсон [15.3] показал, что в худшем случае этот модифицированный алгоритм имеет сложность а не как было показано в работе [15.4].

Иногда может возникнуть необходимость получить не самые короткие пути. Такая и связанные с ней задачи обсуждаются в работах [15.5-15.10]. Алгоритмы, предназначенные для разреженных графов, приведены в работах [15.11, 15.12].

15.1.2. Кратчайшие пути между всеми парами вершин

Предположим, что необходимо найти кратчайшие пути между всеми упорядоченными парами вершин в ориентированном графе на вершинах. Простым решением этой задачи было бы -кратное применение алгоритма Дейкстры. Однако существуют более эффективные алгоритмы по сравнению с этим решением. Они применимы даже тогда, когда в графе присутствуют ребра отрицательной длины, но не существует ориентированных циклов отрицательной длины. Рассмотрим один из этих алгоритмов. Он предложен Флойдом [15.13] и основан на процедуре Уоршолла (алгоритм 14.1) для вычисления транзитивного замыкания.

Пусть дан ориентированный граф G на вершинах, ребра которого помечены длинами. Пусть вершины графа обозначаются числами . Предположим, что в графе не существует ориентированного цикла с отрицательной длиной. Пусть -матрица длин ребер графа G, т. е. — длина ориентированного ребра в графе G. Полагаем если в графе нет ребра ориентированного из i в Мы полагаем также, что для всех

Начиная с матрицы алгоритм Флойда строит последовательность таких -матриц, что элемент матрицы есть расстояние между и у в графе G. Матрица определяется по матрице в соответствии со следующим правилом:

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

Теорема 15.1.. Для есть длина пути

Доказательство. Аналогично доказательству теоремы 14.1.

Обычно кроме кратчайших длин нам необходимо также получить сами пути с такими длинами. Напомним, что в алгоритме Дейкстры мы использовали массив PRED, чтобы хранить указание на вершины, встречающиеся в кратчайших путях. Это достигается в алгоритме Флойда следующим образом: по мере построения последовательности мы одновременно строим такую другую последовательность матриц что элемент матрицы указывает на вершину, которая непосредственно следует за вершиной t в Ясно, что в этом случае

получается в соответствии со следующим правилом: пусть тогда

Это правило аналогично правилу, применяемому на шаге алгоритма 15.1 для изменения массива PRED. Правомочность этого правила определяется следующим. Если то Длина равна длине . Поэтому совпадает с

С другой стороны, если то — конкатенация Поэтому Очевидно, что кратчайший -путь определяется последовательностью вершин где

    (15.10)

Отметим, что в формуле (15.7) если или равны Это простое замечание используется при дальнейшем описании алгоритма Флойда. Мы добавили также в этот алгоритм действия по проверке на присутствие в графе ориентированного цикла с отрицательной длиной.

Алгоритм 15.2. Кратчайшие пути между всеми парами вершин (Флойд).

S1. -матрица длин ребер вданном ориентированном графе G. Положить для всех — -матрица, в которой

S2. Пусть

S3. Пусть . Для всех таких что и всех таких что выполнить следующие действия:

1) положить

2) если то положить

S4. 1. Если какой-либо элемент матрицы то вершина i принадлежит некоторому ориентированному циклу с отрицательной длиной. HALT.

2. Если все то -длины всех кратчайших путей, а — первая вершина после i в кратчайшем -пути. HALT.

3. Если все , то идти к шагу S3

Алгоритм Флойда является наиболее эффективным из известных алгоритмов выделения всех кратчайших путей. Он применим к графам с отрицательными длинами. Для ознакомления с другим эффективным алгоритмом выделения всех кратчайших путей см. работу [15.14].

В работе [15.15] предлагается алгоритм выделения всех кратчайших путей. Позже в работе [15.16] было указано на наличие в этой работе ошибки и представлен исправленный вариант. В работе [15.17] приводится исчерпывающая библиография по алгоритмам выделения кратчайших путей.