Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

выделенным двойной рамкой. В результате получаем матрицы D₂ и S₂ (см. рис.10):

Шаг 3. Полагаем k=3. В матрице D₂ и S₂ выделены ведущие строка и столбец.

Треугольный оператор применяется к элементам матриц D₂ и S₂, выделенные двойной рамкой. В результате получаем матрицы D₃ и S₃(см. рис.11):

Шаг 4. Полагаем k=4. Выделены ведущие строка и столбец в матрице D₃ и S₃.

Получаем новые матрицы (см. рис.12):

Шаг 5. Полагаем k=4. Ведущие строка и столбец в матрице D₄ и S₄ выделены_. Никаких

действий на этом этапе не выполняем; вычисления закончены.

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

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

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

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

1. Шаг 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоверный ответ на поставленную задачу - это матрица действительных чисел, определяющая расстояние между любыми двумя узлами сети.

1. Определение критических участков проекта и оценка ограничений проекта.

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

а) число узлов ограничено (от 3 до 50);

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

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

г) Расстояние не может быть равно 0;

1. Определение архитектуры системы.

Windows 98, Turbo C++ IDE.

1. Принятие решений об использовании продуктов других разработчиков, о способах интеграции и механизмов обмена информацией с другими программами.

Продукт не имеет механизмов обмена информацией с другими программами.

Программа может использоваться и копироваться любым пользователем в системе Windows.

1. Проектирование процесса и кода: выбор средств разработки, определение интерфейсов программ, отображение функций системы на ее модуле и определение спецификации модулей.

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

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

Задача разбита на подзадачи (программа на модули):

1-ая часть – ввод начальных расстояний.

2-ой частью является определение ведущей строки и ведущего столбца.

3-ей – возможности применения треугольного оператора и произведение нужной замены в двух матрицах (расстояний и последовательности узлов).

2-ая и 3-я часть выполняются такое число раз, сколько узлов сети.

4-ая часть выводит результат на экран.

При программировании модулей словесный алгоритм переводиться в соответствующие операторы ЯП. 2-ой и 3-ий модули выполняются в цикле.

1. Определение требований к процессу тестирования.

Тестирование (Testing) – это этап разработки программы, в процессе которого проверяется работоспособность программы, не содержащей явных ошибок

Т естирование производиться с помощью тестов, совокупностью входных данных, а также точного описания вех результатов, которые должна выработать программа на этих данных. Тесты могут быть взяты из различных источников или разработаны самим программистом.

Все результаты сравниваются с данными, которые были получены при решении задачи вручную.

1. Определение требований безопасности системы.

Данный продукт не связан с другими программами, кроме его запускаемого кода (файла *.exe)

Обоснование выбора языка программирования

Язык Си (разработал Деннисом Ритчи в 1972 г.) соединяет свойства языка высокого уровня с возможностями эффективного использования ресурсов компьютера, которые обычно достигаются только при программировании на языке Ассемблера.

Си не очень прост в изучении и требует тщательности в программировании, но позволяет создавать сложные и весьма эффективные программы. Потому я и выбрал в качестве языка программирования Си.

7. Руководство пользователю

Данная программа находит кратчайшее расстояние между городами по существующей сети дорог. При запуске программа спрашивает, какое количество вершин сети (от 3 до 50) .После чего последовательно вводится расстояние между вершинами (если между вершинами нет расстояния, то ставиться любое отрицательное число).

После ввода данных на экран выводиться матрица расстояний и матрица последовательности узлов.

Если в матрице последовательности узлов s_ij ≠ j, то города i и j связаны, по крайней

мере, через один промежуточный узел. Рассмотрим этот случай на примере (см. «Численное решение показательного примера»):

Поскольку s₁₅ = 4 и s₄₅ = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1→4→5. Но, т. к. s₁₄ ≠ 4, узлы 1 и 4 в определяемом пути не связаны одним ребром (но в исходной сети они должны быть связаны непосредственно). Далее следует

определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s₁₄=2 и s₂₄=4, поэтому маршрут 1→4 заменяем на 1→2→4. Поскольку s₁₂=2 и s₂₄=4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 к узлу 5: 1→2→4→5. Длина этого пути равна 12 милям.

Заключение

Данная курсовая работа включает в себя два предмета: «Основы алгоритмизации и программирования» и «Математические методы».

В курсовой работе были рассмотрены следующие вопросы:

• Рассмотрен и дан алгоритм решения сетевых задач методом Флойда.

• Рассмотрен выбор языка программирования.

• Даны ограничения модели.

• Написана программа для решения данной модели.

• Даны инструкции пользователю.

Данная программа была протестирована на многих примерах и на разных ПК и при этом выдавала правильные результат.

Список использованной литературы

1. «Введение в исследование операций» Х.А.Таха;

2. «Математика для экономических специальностей» М.С.Красс;

3. «Основы математики и ее приложение в экономическом образовании» М.С. Красс, Б.П.Чупрынов;

4. «Экономико-математические требования» В.А.Абчук.

5. «C/C++ в задачах и примерах» Н.Культин.

6. «Turbo Pascal в задачах и примерах» Н.Культин.

7. «Информатика» Л.З.Шауцукова.

8. «Дискретная математика для программистов» Ф.А.Новиков.

9. «Основы алгоритмизации и программирования» О.Л.Гальцына, И.И.Попов.

10. «C++ Builder 6 справочное пособие» А.Я.Архангельский.

11. «Теория графов» О.И.Леонов.

12. ссылка на алгоритм Флойда http://algolist.manual.ru/maths/graphs/shortpath/floyd.php

13. ссылка “теория графа” http://www.csu.ac.ru/~yan/mvs2002/Mvslab_7.htm

14. ссылка на математические графы http://www.sura.ru/maxwell/scripts/math-graphs.php

15. ссылка “вопросы о графах” http://shade.msu.ru/~mab/summer2002/test/graph.html

16. ссылка алгоритмы на Basic http://www.rsdn.ru/res/book/prog/basic_algorithms.xml

17. ссылка http://olympiads.ru/sis/2003/plans/exam_c.doc

18. ссылка на все алгоритмы http://alglib.dore.ru/all.html

19. ссылка “теорию графов“ http://pco.iis.nsk.su/~dyatlov/alg/graph/index.php

20. ссылка на различные алгоритмы http://www.citforum.ru/book/algoritm/algoritm_c.shtml

21. ссылка “дискретная математика” http://ermak.cs.nstu.ru/site/students/rta/control.phtm

Приложение

Описание алгоритма в виде блок-схемы

Листинг программы

#include

#include

#define MAX_VERT 50

int main ( void )

{

clrscr ( );

int k = 0,

i = 0,

j = 0,

n = 0;

int D [ MAX_VERT ][ MAX_VERT ];

int S [ MAX_VERT ][ MAX_VERT ];

/*-------->8-------------start>>Vvod*dannix----------------->8--------------*/

while ( n MAX_VERT ){

printf ( "\nvvedite kol_vo versin v seti [ 2 >> %d ] : ", MAX_VERT );

scanf ( "%i", &n );

if ( n > MAX_VERT || n < 3 )

printf ( "\nkol_vo versin dolzno bit v diapozone ot [ 2 >> %d ] ! \n", MAX_VERT );

};

printf ( "\n" );

for ( i=0;i

for ( j=0;j

if ( i = = j ) D[i][j] = 0;

else { printf ( "A [ %i , %i ] = ", i+1, j+1 );

scanf ( "%i", &D[i][j] );

};

};

};

for ( i=0;i

for ( j=0;j

if ( i==j ) S[i][j] = 0;

else S[i][j] = j+1;

};

};

/*-------->8---------------end>>Vvod*dannix----------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>resenia*dannix-------------->8---------------*/

for( k=0;k

for( i=0;i

if ( k==i ) continue;

for ( j=0;j

if ( k = = j || i = = j ) continue;

if ( ( ( D[i][j] > ( D[i][k] + D[k][j] ) )

|| D[i][j] 0

&& D[i][k] > 0 ){

D[i][j] = ( D[k][j] + D[i][k] );

S[i][j] = k+1;

};

};

};

};

/*-------->8---------------end>>resenia*dannix-------------->8--------------*/

/*--------------------------------------------------------------------------------------*/

/*-------->8-------------start>>vivoda*dannix--------------->8---------------*/

printf ( "\n\t" );

printf ( "Matrixa Rastoqnij :" );

printf ( "\n\n" );

for ( i=0;i

for ( j=0;j

printf ( "%5i", D[i][j] );

};

printf ( "\n" );

};

printf ( "\n\t" );

printf ( "Matrixa Posledovatelnosti yzlov :" );

printf ( "\n\n" );

for ( i=0;i

for ( j=0;j

printf ( "%5i", S[i][j] );

};

printf ( "\n" );

};

/*-------->8---------------end>>vivoda*dannix--------------->8--------------*/

printf ( "\n < Nazmite lubyu klavisy ! >" );

getch ( );

return 0;

};

Характеристики

Список файлов реферата