Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Словесное описание алгоритма





Введение

 

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

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

Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики и развитием вычислительной техники.

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

Целью курсовой работы является закрепление знаний по дисциплине «Структуры и алгоритмы обработки данных», практическое овладение математическим аппаратом, характерным для современной теории анализа сложных систем (теории графов).

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

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

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

 

Компьютерные средства и информационные технологии повысили возможности такого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно.

Количество объектов усложнялись, увеличивались, и натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства, формулы и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

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

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

Из всех объектно-ориентированных языков С++ является наиболее широко используемым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстра.

 

 

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

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

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

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

 

Теоретический раздел

Сведения о графах

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.

Граф G задается множеством точек (вершин) х1, х2,..., хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,...,аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Геометрический граф в пространстве jn(Эвклидово пространство) – это множество V={vi} точек пространства jnи множество Е={ek} простых кривых удовлетворяющих следующим условиям:

1) Каждая замкнутая прямая из множества Е содержит только одну точку v множества V;

2) Каждая незамкнутая прямая из множества Е содержит только 2 точки v из множества V, которые являются ее границами.

3) Кривые Е не имеют общих точек за исключением точек из множества V

4) Граф – это совокупность не пустого множества V, изолированного от него множества Е и отображения f: Е~V&V.

5) Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным.

 

 

Описание алгоритма

Алгори́тм Де́йкстра (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э.Дейкстрой в 1959г. Алгоритм Дейкстра строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются). Алгоритм работает только для графов без ребер отрицательного веса.

В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.

Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.

 

Полиномиальная сводимость. NP – полные задачи.

NP – полная задача

Для некоторых задач класса P = NP было обнаружено удивительное свойство. Оказалось, что некоторые из них универсальны в том смысле, что построение полиномиального алгоритма для любой такой задачи влечет за собой возможность построения такого же алгоритма для всех остальных задач класса NP. Такие задачи называют NP-полными. Для понимания этого свойства требуется определить понятие полиномиальной сводимости одной задачи к другой.

Пусть заданы две массовые задачи z1, z2 принадлежащие классу NP. Говорят, что задача z1 полиномиально сводится к задаче z2, если • для любой частной задачи из z1 можно за полиномиальное время построить соответствующую ей частную задачу из z2; • решение построенной частной задачи из z2 за полиномиальное время может быть преобразовано в решение соответствующей частной задачи из z1. Массовую задачу z называют NP-полной, если любая задача из этого класса полиномиально сводится к решению задачи z. Таким образом, теперь ясно, что разработка полиномиального алгоритма любой NP-полной задачи практически означает возможность построения такого алгоритма для любой задачи класса NP, т. е. справедливость равенства P = NP.

Для доказательства NP-полноты некоторой задачи, нет необходимости сводить к ней каждую задачу класса NP. Достаточно установить ее принадлежность к классу NP и показать, что к ней сводится какая-либо известная NP-полная задача. Чтобы воспользоваться этой схемой, надо иметь в распоряжении хотя бы одну NP-полную задачу. Методы, используемые при доказательстве NP-полноты конкретных задач, развиваются очень быстро. В настоящее время часто применяются три основных метода: сужение задачи, локальная замена и построение компоненты. Доказательство методом сужения NP-полноты задачи z1, которая принадлежит классу NP, заключаетсяв установление того, что задача z1 включает в качестве частного случая известную NP-полную задачу z2.Доказательство двумя другими методами достаточно нетривиальны, и поэтому здесь у нас нет возможности их рассмотреть и проиллюстрировать. В заключение следует отметить, что теория NP-полноты, помимо теоретического, представляет и чисто практический интерес. Доказав, что задача NP-полна, разработчик алгоритмов получает достаточное основания, чтобы отказаться от поиска эффективного и точного решения. В настоящее время для решения NP-полных задач используются в основном различного рода приближенные алгоритмы, основанные на эвристиках и вероятностных механизмах.

 

Проектный раздел

Формальная постановка

Входные данные: взвешенный ориентированный граф, номера начальной и конечной вершины.

Выходные данные: кратчайший путь из начальной в конечную вершину, его длина.

 

Экспериментальный раздел

Заключение

 

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

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

 

Введение

 

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

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

Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики и развитием вычислительной техники.

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

Целью курсовой работы является закрепление знаний по дисциплине «Структуры и алгоритмы обработки данных», практическое овладение математическим аппаратом, характерным для современной теории анализа сложных систем (теории графов).

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

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

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

 

Компьютерные средства и информационные технологии повысили возможности такого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно.

Количество объектов усложнялись, увеличивались, и натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства, формулы и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

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

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

Из всех объектно-ориентированных языков С++ является наиболее широко используемым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстра.

 

 

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

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

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

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

 

Теоретический раздел

Сведения о графах

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.

Граф G задается множеством точек (вершин) х1, х2,..., хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,...,аm. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Геометрический граф в пространстве jn(Эвклидово пространство) – это множество V={vi} точек пространства jnи множество Е={ek} простых кривых удовлетворяющих следующим условиям:

1) Каждая замкнутая прямая из множества Е содержит только одну точку v множества V;

2) Каждая незамкнутая прямая из множества Е содержит только 2 точки v из множества V, которые являются ее границами.

3) Кривые Е не имеют общих точек за исключением точек из множества V

4) Граф – это совокупность не пустого множества V, изолированного от него множества Е и отображения f: Е~V&V.

5) Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным.

 

 

Описание алгоритма

Алгори́тм Де́йкстра (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э.Дейкстрой в 1959г. Алгоритм Дейкстра строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются). Алгоритм работает только для графов без ребер отрицательного веса.

В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.

Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.

 

Словесное описание алгоритма

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u,кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

 

Рисунок 1 – Блок-схема алгоритма Дейкстра

 

 







Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.