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

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

1. Постановка сетевой транспортной задачи.

На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P₁ ,P₂ ,...,P_n , причем некоторые упорядоченные пары (P_i ,P_j ) пунктов назначения соединены дугами заданной длинны r(P_i ,P_j )=l_ij . Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P₁ ,P₂ ,...,P₆ , которые связаны между собой восьмью транспортными путями.

Необходимо определить кратчайший маршрут из пункта P₁ в P₆ . Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.

Например маршрут из пункта P₁ в пункт P₆ : P₁ P₂ P₄ P₆ ; L=l₁₂ +l₂₄ +l₄₆ =10.

Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P₁ в P_n .

2. Описание метода и алгоритма решения.

Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности.

Алгоритм метода Форда содержит четыре этапа (схема 1). На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры l_i и l_j по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р₁ в любой другой пункт назначения Р_j , j=1,2,...,n.

Рассмотрим подробнее каждый из этих четырех этапов.

2.1 Первый этап: Составление исходной таблицы расстояний.

Данная таблица содержит n+1 строк и такое же количество столбцов; P_i - пункты отправления; P_j - пункты назначения. Во второй строке и втором столбце проставляется значения параметров l_i иl_j , определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний l_ij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт P_i не соединен отрезком пути с пунктом P_j , то соответствующая клетка таблицы не заполняется.

2.2 Второй этап: Определение l_i и l_j .

Определяется значение параметров в соответствии с формулой:

l_j =min(l_i +l_ij ); i=1,2,...,n; j=1,2,...,n, (1)

где l₁ =0.

Эти значения заполняются во второй строке и во втором столбце.

2.3 Третий этап: Определение длинны кратчайших путей.

Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты P_j , i=1,2,...,n; j=1,2,...,n.

В первом случае, если выполняются неравенство:

l_j - l_i £ l_ij ; l_ij ¹0; j=1,2,...,n; j=1,2,...,n, (2)

то значения параметров l₁ ,...,l_n удовлетворяют условиям оптимальности. Каждое значение l_j есть не что иное, как кратчайшее расстояние от пункта P_i до пункта P_j , j=2,3,...,n.

Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:

l_j - l_i > l_ij ; i=1,...,n; j=1,...,n, (3)

то значения l_j иl_i могут быть уменьшены.

Если справедливо (3), тогда исправим значение l_j0 , пересчитав его по формуле:

l¢_j0 =l_i0 +l_i0j0 . (4)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--