КРАТЧАЙШИЕ ПУТИ СЛЕДОВАНИЯ ПОЕЗДОВ

Определение кратчайшего пути имеет как самостоятельное значение, когда между рассматриваемыми станциями или полигонами существует несколько параллельных линий, так и вспомогательное — при решении задач минимизации стоимости перевозок. Критериями решения этой задачи могут быть выбраны расстояние, время, затраты и т.д. Задача нахождения кратчайшего пути имеет многочисленные практические приложения и может быть использована при решении различных задач оптимизации. Математически она относится к задачам линейного программирования, в которых минимизируется стоимость прохождения потока между двумя станциями. Для решения задачи о кратчайшем пути следования целесообразно использовать специальный алгоритм Дийкстры.

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

Полагаем, что вершина as принадлежит искомому дереву. Предположим теперь, что найдено т ребер дерева (т = 0, 1, ..., п — 2). Длину кратчайшего пути из вершины as в вершину ак обозначим lsk. Рассмотрим пути из as в а„ содержащие, кроме ребер дерева, не более одного ребра вне дерева. Длину кратчайшего среди таких путей обозначим 1'к Если все пути из as в ак содержат на некотором шаге алгоритма больше одного ребра вне дерева, то полагаем 1'к = оо. Заметим, что величина 1'к зависит от т: она изменяется по мере увеличения т. Вообще говоря, l'k > lsk.

Предположим, что в ходе алгоритма построена часть искомого дерева, которую будем называть текущим деревом. Вершина ак (не принадлежащая текущему дереву) называется соседней с этим деревом, если в сети имеется ребро bik или ребро bkj, где а1 некоторая вершина текущего дерева. Тогда путь длиной l'si из вершины as в вершину а, содержит только ребра дерева и, следовательно, l'si = lsi. Из определения следует, что l'k = min (lsi + dik), где минимум берется по всем вершинам текущего дерева.

На каждом шаге алгоритма число ребер дерева увеличивается на единицу, при этом величины 1'к должны быть пересчитаны для всех вершин, соседних с вновь построенным деревом. Для этого имеющаяся величина 1'к сравнивается с величиной lsr+ drk. Если hr+ drk < l'k, то параметру l’k присваивается значение lsr + drk, если же hr + d* - Кк-> то Кк остается без изменения. Символически это записывается в следующем виде: l’k: = min (l'sk, lsk + dik), где символ: = обозначает оператор присвоения.

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

Шаг 0. Положить, что вершина as принадлежит дереву; lss = 0; для соседних с as вершин lsk = dsk, для остальных lsk = оо.

Шаг 1. Положить lsr = min l'k = lsi + djr, где ak все вершины, соседние с текущим деревом. Ребро bir включить в число ребер дерева.

Шаг 2. Если число ребер дерева равно л —1, то конец. Если нет, перейти к шагу 3.

Шаг 3. l'k: =min lsr + drk). Перейти к шагу 1.

Этот алгоритм может быть осуществлен при помощи расстановки пометок. Каждая вершина ак получает пометку вида (/, /'). Первая часть пометки — это величина Гл или lsk, а вторая часть указывает соседнюю с ак вершину в кратчайшем пути из as в ак. Пометка называется временной, если она имеет вид (1'к, /), и постоянной, если она имеет вид (lsk, /). Вначале каждая вершина ак, соседняя с вершиной as, получает временную пометку (а, 5) = = (l'k, s). Если lsr = min l'k, то вершина аг получает постоянную пометку (/;r, S) = (lsr, S).

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

Большое практическое значение задачи нахождения кратчайших путей следования грузопотоков, вагонопотоков и поездопотоков связано с тем, что с грузовладельцев взимается плата за перевозку грузов по тарифному расстоянию, т.е. кратчайшим путем. В оперативных условиях вследствие временного возрастания потока или уменьшения пропускной способности участков часто весь заданный поток не может быть пропущен по кратчайшему пути. И тогда возникает задача о нахождении промежуточной величины заданного потока между максимальным потоком и следующим только по кратчайшему пути. На исходной сети (см. рис. 9.2) практическое решение такой задачи приведено в разделе 6.3.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >