Материал: 4442

16

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

Алгоритм Дейкстры поиска кратчайшего пути

Каждой дуге (х, у) исходного графа G поставим в соответствие число а(х, у). Если в графе G отсутствует некоторая дуга (х, у), то а(х, у) = ∞. Будем называть число а(х, у) длиной дуги (x, у), хотя а(х, у) можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь. Для любых двух вершин s и t графа G могут существовать несколько путей, соединяющих вершину s с вершиной t. В данном разделе будет рассмотрен алгоритм, который определяет такой путь, ведущий из вершины s в вершину t, который имеет минимально возможную длину. Этот путь называется кратчайшим путем между вершинами с и t.

Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины х к вершине s определяется длиной кратчайшего пути, ведущего из s в х). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.

Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины у пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший и будем считать его условно кратчайшим путем из вершины s в вершину у.

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

17

Итак, если известны m ближайших к s вершин, то (m + 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может до тех пор, пока не будет получен кратчайший путь, ведущий на вершины s к вершине t.

Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.

Шаг 1. Перед началом выполнения алгоритма все вершины и дуги не окрашены. Каждой вершине в ходе выполнения алгоритма присваивается

число d(x), равное длине кратчайшего пути из s в x, включающего только окрашенные вершины.

Приравнять d(s) = 0 и d(x) = ∞ для всех x, отличных от s. Окрасить вершину s и приравнять y = s (y – последняя из окрашенных вершин).

Шаг 2. Для каждой неокрашенной вершины x следующим образом пересчитать величину d(x) [3]

Если d(x) = ∞ для всех неокрашенных вершин x, закончить процедуру алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина d(x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину x (для этой дуги достигается минимум в соответствии с выражением (2.5)). Приравнять y = x.

Шаг 3. Если y = t, закончить процедуру: кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

Отметим, что каждый раз, когда окрашивается некоторая вершина (не считая вершины s), окрашивается и некоторая дуга, заходящая в данную

вершину. Таким образом, на любом этапе алгоритма в каждую вершину заходит не более чем одна окрашенная дуга. Кроме того, окрашенные дуги не могут образовать в исходном графе цикл, так как в алгоритме не может окрашиваться дуга, концевые вершины которой уже окрашены. Следовательно, можно сделать вывод о том, что окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине s. Это дерево называется ориентированным деревом кратчайших путей. Единственный путь от вершины s до любой верши-

18

ны x, принадлежащей дереву кратчайших путей, является кратчайшим путем между указанными вершинами.

Если кратчайшему пути из вершины s в вершину x в дереве кратчайших путей принадлежит вершине y, то часть этого пути, заключенная между x и y, является кратчайшим путем между этими вершинами. Действительно, если бы между x и y существовал более короткий путь, то упомянутый выше путь между вершинами s и x не могут быть кратчайшим.

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

Когда в этой процедуре наращивания достигается вершина t, процедура может быть остановлена.

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

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

19

Расчетная часть Задание для практической работы состоит из транспортной сети (рису-

нок 1) и таблицы 5 и 6, в которых содержатся исходные данные для выполнения работы согласно индивидуальному варианту, выданному преподавателем.

Варианты заданий В данной таблице приведены сформированные варианты заданий. Данные

варианты являются рекомендуемыми и выбираются согласно таблице 1.

Таблица 4