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

Посмотреть архив целиком

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


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


На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны (Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

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

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

Например маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.

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


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


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

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

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


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


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


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


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


j=min(i+lij); i=1,2,...,n; j=1,2,...,n, (1)

где 1=0.

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


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


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

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


j - i  lij; lij0; j=1,2,...,n; j=1,2,...,n, (2)

то значения параметров 1,...,n удовлетворяют условиям оптимальности. Каждое значение j есть не что иное, как кратчайшее расстояние от пункта Pi до пункта Pj, j=2,3,...,n.

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


j - i > lij; i=1,...,n; j=1,...,n, (3)

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

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

j0=i0+li0j0. (4)


2.4 Четвертый этап: Нахождение кратчайшего пути.


Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:

lr1,j = j - r1, (5)

где lr1,j берется из таблицы, причем r1 выбирается так, чтобы выполнилось равенство (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.

Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.

В программе предусмотрена возможность повторного решения задачи с другими исходными данными.


4. Описание подпрограмм и процедур.


Подпрограммы и функции.



ТИП


НАЗВАНИЕ


НАЗНАЧЕНИЕ

Function

type : real

min;

Вычисляет минимальное значение вектора k[i];

Procedure

set_graph_mode;

Устанавливает графический режим;

Procedure

install_firewall;

Инициализирует огонь;

Procedure

fire;

Процедура рисования огня;

Procedure

ok;

Выводит сообщение о корректности операции;

Procedure

notok;

Выводит сообщение о некорректности операции;

Procedure

check_input_data;

Проверяет корректность ввода данных;

Procedure

keybord_input;

Ввод исходных данных с клавиатуры;

Procedure

ramka;

Выводит рамку по краям экрана;

Procedure

save;

Сохранение результатов в файл;

Procedure

about_program;

Выводит информацию о программе;

Procedure

about_method;

Выводит информацию о методе Форда;

Procedure

output_graph;

Рисует вершины графа;

Procedure

draw_ways;

Рисует дуги графа;

Procedure

draw_short_way;

Рисует кратчайший маршрут;

Procedure

count_point_coord;

Вычисляет экранные координаты вершин графа;

Procedure

set_font;

Инициализирует шрифт пользователя;

Procedure

calculate;

Основное математическое ядро программы;

Procedure

draw_menu;

Открытие меню;

Procedure

redraw_menu;

Закрытие меню;

Procedure

main_menu;

Основной механизм меню;

Procedure

pixel;

Ставит точку;

Procedure

stars;

Инициализирует массив со звездами;

Procedure

welcomescreen;

Заставка;


4.2 Таблица идентификаторов.



ИМЯ



тИП


НАЗНАЧЕНИЕ

Константы

menu

array of string

Описывает меню программы

menuof

array of byte

Описывает меню программы

menugo

array of byte

Описывает меню программы

name1

string

Имя файла входных данных

name2

string

Имя файла выходных данных

xxx

word

Размер огня по х

yyy

word

Размер огня по у

xx1

word

Координата х огня

yy1

word

Координата у огня

messize

byte

Размер заглавия

title

array of string

Заглавие

Переменные

mas

array of real

Основная матрица вычислений

coord_point

array of real

Координаты вершин графа

i

integer

Переменная для организации цикла

j

integer

Переменная для организации цикла

t

integer

Используется при расчете пути

m

integer

Счетчик кол-ва вершин в крат. Пути

n

integer

Кол-во вершин в графе

z

integer

Код ошибки

x1

integer

Исп. в процедуре вывода на экран

y1

integer

Исп. в процедуре вывода на экран

x2

integer

Исп. в процедуре вывода на экран

y2

integer

Исп. в процедуре вывода на экран

kk

integer

Промежуточное значение

iii

integer

Промежуточное значение

x

integer

Координата х конца отрезка

y

integer

Координата у конца отрезка

lenth

integer

Кол-во вершин в кратчайшем маршруте

chrus

integer

Номер шрифта пользователя

z1

integer

Номер графического драйверв

z2

integer

Номер графического режима

k

array of real

Используется для нахождения минимума

result

array of integer

Номера вершин, которые входят в кратчайший маршрут

error_code

array of byte

Коды ошибок при вводе данных

fire1

array of byte

Хранит цвета огня

fire2

array of byte

Матрица промежуточных данных

aa

real

Используется при вычислении координат вершин графа

pi1

real

Используется при вычислении координат вершин графа

s

real

Хранит промежуточное значение

l

boolean

Исп. при определении кратчайшего маршрута

inputdata

boolean

TRUE, если данные вводились

calculatedata

boolean

TRUE, если данные били обработаны

mov

boolean

Используется в процедуре меню

o

string

Используется при вводе с клавиатуры

temp

byte

Хранит временное значение

cursor

byte

Координаты курсора меню

lastcursor

byte

Последние координаты курсора меню

menulevel

byte

Уровень меню

nline

byte

Кол-во строк в текушем уровне меню

pressed

char

Используется при вводе с клавиатуры

f1

text

Файловая переменная

f2

text

Файловая переменная


Случайные файлы

Файл
116389.rtf
96684.rtf
50037.rtf
32144.rtf
70057.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.