Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог

Конечные матрицы D₄ и S₄ содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i,j) состоит из ребра (i,j) только в том случае, когда s_ij=j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел.

4. Описание алгоритма автоматизированных расчетов

1. Cоставляется начальная матрица расстояний D₀ и матрица последовательности узлов S₀. В каждой ячейке матрицы D пишется элемент d_ij, который определяет расстояние между узлом i и узлом j, матрица S заполняется автоматически . Элемент, в котором i==j помечается “—“, он в вычислении не участвует.

2. Шаг 1. Пока k<=n-1 выполняются следующие действия.

Определяем k-ую стоку и k-ый столбец как ведущую строку и ведущий столбец.

а) осуществляется переборка всех элементов, если d_ik+d_kjij, то элемент d_ij заменяется на сумму d_ij+d_kj. При условии, что i≠k, j≠k и j≠i.

б) cоставляется матрица расстояний D₁ в соответствии с заменами на шаге 1 и матрица последовательности узлов, в котором элементы s_ij соответствующие элементам d_ij заменяется на k.

3. Полагается, что k=k+1 и повторяется шаг 2.

5. Расчет экономической эффективности расчетной модели

Решение задачи сетевого моделирования при помощи программы курсовой работы по теме “Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог” рассчитывает минимальное расстояние между любыми двумя пунктами с большой точностью, что не происходит при решение таких задач вручную. Результат, получаемый при решении данной задачи отличается от ручного решения тем, что человеку гораздо удобнее использовать ресурсы компьютера, а не заниматься рутинной работой, решая однотипные задачи вручную, что может привести к ошибочным результатам.

Пример некорректных данных с точки зрения данной модели

Некорректными данными с точки зрения выбранной модели являются данные, которые не удовлетворяют условиям ограничения данной модели. Например: при вводе отрицательного расстояния между городами то система выдаст сообщение «Расстояние между городами не может быть отрицательным»

Математический анализ найденного решения

Математический анализ решения задач из темы “Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог” показывает. Что если при вводе входных данных не было допущено ошибки, т. е. входные данные удовлетворяют установленным для системы ограничениям, то полученное решение действительно будет соответствовать поставленной задаче.

Экономический анализ полученного решения

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

6. Постановка задачи на программирование

Ограничения модели

Данный проект имеет следующие ограничения:

1. Количество вершин должно быть в диапазоне (i=3;i<=50);

2. расстояния между одним и тем же узлом быть не может;

3. Если между вершинами нет расстояния - вводится любое отрицательное число.

4. Расстояние не может быть равно 0.

Техническое задание

Программа предназначена для вычисления кратчайшего пути между всеми городами заданной сети дорог.

Задание на проектирование

Результатами проектирования являются:

1. Рассмотрение результатов анализа и проверка их полноты.