Категория
Информатика
Тип
реферат
Страницы
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
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Решение задачи о кратчайшем маршруте методом Форда 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