Решение задачи о кратчайшем маршруте

1. Постановка сетевой транспортной задачи.
На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1 ,P2 ,...,Pn , причем некоторые упорядоченные пары (Pi ,Pj ) пунктов назначения соединены дугами заданной длинны r(Pi ,Pj )=lij . Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.
На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1 ,P2 ,...,P6 , которые связаны между собой восьмью транспортными путями.
Необходимо определить кратчайший маршрут из пункта P1 в P6 . Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.
Например маршрут из пункта P1 в пункт P6 : P1 P2 P4 P6 ; L=l12 +l24 +l46 =10.
Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P1 в Pn .
2. Описание метода и алгоритма решения.
Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.
Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры li и lj по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj , j=1,2,...,n.
Рассмотрим подробнее каждый из этих четырех этапов.
2.1 Первый этап: Составление исходной таблицы расстояний.
Данная таблица содержит n+1 строк и такое же количество столбцов; Pi - пункты отправления; Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров li иlj , определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj , то соответствующая клетка таблицы не заполняется.
2.2 Второй этап: Определение li и lj .
Определяется значение параметров в соответствии с формулой:
lj =min(li +lij ); i=1,2,...,n; j=1,2,...,n, (1)
где l1 =0.
Эти значения заполняются во второй строке и во втором столбце.
2.3 Третий этап: Определение длинны кратчайших путей.
Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj , i=1,2,...,n; j=1,2,...,n.
В первом случае, если выполняются неравенство:
lj - li £ lij ; lij ¹0; j=1,2,...,n; j=1,2,...,n, (2)
то значения параметров l1 ,...,ln удовлетворяют условиям оптимальности. Каждое значение lj есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj , j=2,3,...,n.
Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
lj - li > lij ; i=1,...,n; j=1,...,n, (3)
то значения lj иli могут быть уменьшены.
Если справедливо (3), тогда исправим значение lj0 , пересчитав его по формуле:
l¢j0 =li0 +li0j0 . (4)
2.4 Четвертый этап: Нахождение кратчайшего пути.
Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:
lr1,j = lj - lr1 , (5)
где lr1,j берется из таблицы, причем lr1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn , а Pr1 . Будем продолжать до тех пор, пока rn =1.
Таким образом кратчайший маршрут проходит через Pr1 ,Pr2 ,...,Prn , а длинна маршрута Lmin=lr2,r1 +lr3,r2 +...+lrn-1,rn .
3. Описание программы.
Программа “FORD” написана на языке высокого уровня - Pascal, в интегрированной среде разработки “Turbo Pascal 7.0” фирмы Borland Inc.
Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.
В программе предусмотрена возможность повторного решения задачи с другими исходными данными.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию