Пятница, 2024-03-29, 1:57 PM
Коллекция материаловГлавная

Регистрация

Вход
Приветствую Вас Гость | RSS
Меню сайта
Главная » 2014 » Август » 4 » Скачать Изучение и реализация на практике алгоритма Флойда для нахождения кратчайших путей в графе бесплатно
10:47 PM
Скачать Изучение и реализация на практике алгоритма Флойда для нахождения кратчайших путей в графе бесплатно
Тип: Курсовая работа
Предмет: Математика
Тема: Изучение и реализация на практике алгоритма Флойда для нахождения кратчайших путей в графе
Страниц: 31  
Формат: doc  

Содержание

Введение 3

1. Раздел 1. Общая часть 4

1.1. Постановка задачи 4

В среде Borland Delphi 7 необходимо разработать приложение, которое реализует метод Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Постановка задачи: пусть дан непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа

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

1.2. Цели разработки 5

1.3. Построение математической модели 6

1.4. Описание математических формул 9

2. Раздел 2: Специальная часть 10

2.1. Расчет математической модели 10

2.2. Описание программы 16

2.2.1.О программе 17

2.2.2.Алгоритм работы программы 18

2.2.3.Входные данные 21

2.2.4.Выходные данные 21

2.4.Тестирование программы 25

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

Заключение 29

Литература 30

Приложение А

Введение

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

Наиболее распространенные методы поиска кратчайших расстояний – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе).

Целью курсовой работы было изучить и реализовать на практике алгоритм Флойда для нахождения кратчайших путей в графе. Объектом работы является алгоритм Флойда.

Задачи работы:

1. Изучение теории графов.

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

3. Создание приложения, которое реализует алгоритм Флойда.

4. Отладка приложения.

Список литературы

1. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. М. Иза-во МГТУ им. Н.Э.Баумана, 2003. – 325 с.

2. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 2002. – 165 с.

3. Гофман В.Э., Хомоненко А.Д. Delphi 5. – СПб.:БХВ – Санкт Петербург, 2002. – 800с.

4. Королев Н.А. Введение в Delphi 7. М. ЮНИТИ, 2005. – 322 с.

5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 2002. – 222с.

6. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 2000. – 302 с.

7. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992. – 332 с.

8. Оре О. Теория графов. – М.: Наука, 1980. – 345 с.

Примечания

Скачивание файла!Для скачивания файла вам нужно ввести
E-Mail: 1662
Пароль: 1662
Скачать файл.
Просмотров: 179 | Добавил: Диана33 | Рейтинг: 0.0/0
Форма входа
Поиск
Календарь
«  Август 2014  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031
Архив записей
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Copyright MyCorp © 2024 Создать бесплатный сайт с uCoz