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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Работа № 96067


Наименование:


Курсовик Алгоритм Дейкстры. Поиск кратчайшего пути.

Информация:

Тип работы: Курсовик. Добавлен: 10.4.2016. Сдан: 2015. Страниц: 64. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Введение………………………………………………………………………………….………….…...4
ГЛАВА 1. Нахождение минимального пути в графе (Алгоритм Дейкстры)
1.1- Постановка задачи………………………………………..…………………………..…………...5
1.2- Описание метода решения задач…………………………………………………..…………….8
1.3- Общие сведения о графах……………………….…………...…………….………………………8
1.4- Функциональные тесты…………………..……………………………………………..………10
ГЛАВА 2. Моделирование, алгоритмизация и программирование метода
2.1- Входные- выходные данные задачи……………..……………………………………………....14
2.2-Тестирование……………………………………..………………………………………….……14
ГЛАВА 3. Руководство пользователя
3.1- Диалог с пользователем……………………...……………………………………….………….17
Заключение………..……………………………………………………………………………………21
Список литературы…..………………………………………………………………………………22
Приложение А(Текст программы)………………………………….……………………………… 23
Приложение Б(Схема программы)…………………………………………………………………..64


ВВЕДЕНИЕ

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторика, Алгоритм на графах, изобретён нидерландским ученым Э. Дейкстрой в 1959 год его алгоритм был рассчитан для нахождения минимального пути положительных чисел, и был назван в его честь алгоритм Дейкстры. Графы стали использоваться при построении схем электрических цепей и молекулярных схем.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности, в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п. Именно по тому, что теория графов занимает не малое значение в нашей жизни, автор выбрал именно эту тему курсовой работы.
Целью курсовой работы является разработка программного продукта для решения задач нахождения минимального пути.
Задачи курсовой работы:
· Изучить предметную область
· Определить входные, выходные данные
· Определить метод решения нахождения минимального пути
· Выполнить структурное проектирование задачи в виде блок схемы
· Спроектировать интерфейсные формы ПП «метода Дейкстры»
· Разработать ПП «метода Дейкстры»
· Произвести анализ надежности и качества ПП «метода Дейкстры»
Большое значение в теории графов имеют алгоритмические вопросы. Для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для графов имеет построение эффективных алгоритмов, находящих точное или приближенное.
ГЛАВА 1. НАХОЖДЕНИЯ МИНИМАЛЬНОГО ПУТИ В ГРАФЕ (АЛГОРИТМ ДЕЙКСТРЫ)
1.1 ПОСТАНОВКА ЗАДАЧИ
Постановка задачи на максимум выглядит следующим образом:
Граф G задается множеством вершин х1, х2,…, хn. (которое обозначается через Х) и множеством линий (ребер) а1, а2,…, аm. (которое обозначается символом А), соединяющих между собой все или часть этих вершин в соответствии с рисунком 1. Таким образом, граф G полностью задается (и обозначается) парой (Х, А).
Рисунок 1 - Граф G
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом в соответствии с рисунком 2.
Рисунок 2 - Ориентированный граф
Например, если дорога имеет не двух -, а одностороннее движение то направление этого движения будет показано стрелкой. Если ребра не имеют ориентации, то граф называется неориентированным в соответствии с рисунком 3.

Рисунок 3 - Неориентированный граф
В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин(т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 2 обозначение (х1, х3) относится к дуге а1. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рисунке 2: Г (х1)={х2, х3}, т.е. вершины х2 и х3 являются конечными вершинами дуг, у которых начальной вершиной является вершина х1.
На рисунке 3: Г (х1)={х2, х4, х5}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.) Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Так, на рисунке 4 последовательности дуг являются путями.
а6, а5, а9, а8. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, а10, а6. (3)
Рисунок 4 - Граф H
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т. к. дуга а6 в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) - нет. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер д1, д2,…, дq, в которой каждое ребро аq за исключением первого и последнего ребер, связано с ребрами аi-1 и аi+1 своими концевыми вершинами. Последовательности дуг:
д2, д4, д8, д10 (4)
д2, д7, д8, д4, д3, (5)
д10, д7, д4, д8, д7, д2. (6)
В графе, изображенном на рисунок, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х2, х5, х4, х3, х5, х6. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (д1, д2,…, дq), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.

Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости длины), задаваемые матрицей С = [cij].
Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s?x до заданной конечной вершины t?x, при условии, что такой путь существует t?R(s) (здесь R(s) - множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi - некоторая его вершина, то, двигаясь от s к хi, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым (? ?) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
1.2 ОПИСАНИЕ МЕТОДА РЕШЕНИЯ ЗАДАЧ
Процедура находит путь минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wij неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2 . Процедура использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.
Алгоритм по которому происходит поиск заключается в следующем:
всем вершинам приписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u1 , а d(u1 ) := 0
всем вершинам приписывается метка m(i) := 0
вершина u1 объявляется текущей: t := u1
для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле: d(i) := min{d(i), d(t)+W[t,i]}
среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм
иначе найденную вершину c минимальным весом полагаем т........



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы

* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.