Алгоритм Дейкстра

  • 21 янв. 2013 г.
  • 2116 Слова
Аннотация
Курсовая работа по дисциплине “Структуры и алгоритмы обработки данных” ставит своей целью самостоятельного исследования студентами различных алгоритмов нахождения кратчайших путей.
Данная курсовая работа посвящена программной реализации алгоритма Дейкстра, позволяющего решить задачу о нахождении кратчайшего пути во взвешенном ориентированном графе.

Содержание

Введение5
1. Постановка задачи 7
2. Теоретический раздел 10
2.1 Сведения о графах 14
2.2 Описание алгоритма 15
2.3 Полиномиальная сводимость, NP – полная задача 20
3. Проектный раздел 18
3.1 Описание алгоритма и структуры программы 18
3.2 Формальная постановка 20
3.3 Описание программных средств21
4. Экспериментальный раздел 24
Заключение 32
Список использованных источников 33

Введение

При взгляде на географическую карту сразу бросается в глаза сеть железных дорог, что является типичным графом. Рассмотрим классическую задачу о коммивояжере. Существует много различных маршрутов поездки. А выбрать из них наикратчайший поможет граф.
Графы используются встроительстве при планировании проведения работ; для решения логических проблем, связанных с перебором вариантов и во многих других вопросах.
Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики и развитием вычислительнойтехники.
В программировании логика незаменима как строгий язык и служит для описания сложных утверждений, значение которых может определить компьютер.
Целью курсовой работы является закрепление знаний по дисциплине «Структуры и алгоритмы обработки данных», практическое овладение математическим аппаратом, характерным для современной теории анализа сложных систем (теории графов) .
Благодаря своемуширокому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутацииинформационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Компьютерные средства и информационные технологии повысили возможности такого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно.
Количествообъектов усложнялись, увеличивались, и натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства, формулы и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.
Реализовать большой потенциалматематического моделирования невозможно без мощных средств автоматизации вычислений, которыми являются компьютеры. Благодаря появлению компьютеров и развитию информационных технологий создаются методы и средства компьютерного моделирования, способные решать сложные практические задачи, такие как управление большими энергетическими системами, создание достоверных прогнозов погоды или урожая,моделирование региональных и общегосударственных систем, проектирование самолетов, кораблей и т. п. Компьютерная модель – это размещенная в компьютере совокупность средств, что реализуют концепцию вычисления.
Для реализации компьютерной модели, большое значение имеет такое научное направление, как программирование. Без него компьютер это просто набор различных устройств,...