Сайт в помощь студенту Грамоте учиться – всегда пригодится


Скачать полностью

ГЛАВА 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алгоритм завершает работу.

ИТЕРАТИВНАЯ ПРОЦЕДУРА

         Пусть для заданного узла j  dj - оценка длины кратчайшей цепи из источника s в узел j. Если эта оценка не может быть улучшена, то соответствующее значение называется “постоянной пометкой” и обозначается  символом dj . В противном случае оно называется “временной пометкой”. Вначале процедуры постоянная пометка приписывается только источнику. Каждая другая пометка является временной и ее величина равна длине дуги, ведущей из источника в соответствующий узел. Для определения ближайшего к источнику узла выбирается временная пометка с минимальным значением и объявляется постоянной пометкой. Затем, до тех пор, пока стоку не будет приписана постоянная пометка, необходимо выполнять следующие две процедуры:
Рассмотреть оставшиеся узлы с временной пометкой. Сравнить величину каждой временной пометки с суммой величины последней из постоянных пометок и длины дуги, ведущей из соответствующего постоянно помеченного узла в рассматриваемый узел. Минимальная из двух сравниваемых величин определяется как новая временная пометка рассматриваемого узла. Если величина старой временной пометки меньше второй из сравниваемых величин, то пометка остается прежней.
Среди временных пометок выбрать ту, значение которой минимально, и объявить ее постоянной пометкой. Если при этом постоянная пометка приписывается узлу t, то алгоритм завершает работу. В противном случае перейти на шаг 1.
Данная процедура может быть выполнена с помощью таблицы решения, в которой столбцы соответствуют узлам сети, строки – шагам итеративного процесса, а ее элементы – постоянным и временным пометкам.

1.1.2. ПРИМЕР, ИЛЛЮСТРИРУЮЩИЙ РАБОТУ АЛГОРИТМА ДЕЙКСТРЫ

Пример, иллюстрирующий работу алгоритма Дейкстры, изображен на рис. 2.11. Узел s здесь является источником, t – стоком, а числа  cij,  приписанные дугам, соответствуют их длинам или стоимости.