Категория
Информатика
Тип
реферат
Страницы
8 стр.
Дата
02.01.2010
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21105.zip — 11.15 kb
  • reshenie-zadachi-o-kratchajshem-marshrute_21105_1.rtf — 54.04 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо



Текст работы

Решение задачи о кратчайшем маршруте методом Форда SDL SDL
Решение задачи о кратчайшем маршруте методом Форда
1. Постановка сетевой транспортной задачи.
На практике часто встречается задача определения кратчайшего маршрута
по
заданной сети из начального пункта до конечного пункта маршрута. Транспортная
сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные
магистрали, а узлы - пункты отправления и назначения. Графически транспортная
сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые
упорядоченные пары (Pi,Pj) пунктов назначения соединены дугами заданной длинны
r(Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним
возможно движение только в одном направлении, указанном стрелками.
На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов
P1,P2,...,P6, которые связаны между собой восьмью транспортными путями.
Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение
кратчайшего маршрута состоит в указании последовательности прохождения маршрута
через промежуточные пункты и суммарной длинны маршрута.
Например маршрут из пункта P1 в пункт P6: P1P2P4P6; L=l12+l24+l46=10.
Постановка задачи приобретает смысл в том случае, если имеется несколько
вариантов маршрута из начального пункта в конечный. В этом случае физический
смысл функции цели задачи состоит в минимизации общей длинны маршрута, т
.е. в
определении кратчайшего пути из P1 в Pn.
2. Описание метода и алгоритма решения.
Метод Форда бал разработан специально для решения сетевых транспортных задач и
основан, по существу, на принципе оптимальности.



Ваше мнение



CAPTCHA