Алгоритм Дейкстры - Математика контрольная работа

Главная

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

Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

по дисциплине "Математика Часть II"
Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d (z) =l (z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l (y) =l (x) +w (xy). По предположению индукции, в момент посещения вершины x выполнялось d (x) =l (x), следовательно, вершина y тогда получила метку не больше чем d (x) +w (xy) =l (x) +w (xy) =l (y). Следовательно, d (y) =l (y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d (z) =l (z), что и требовалось доказать.
Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин
Сложность работы алгоритма Дейкстры
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v , а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m - количество ребер в графе G .
В простейшем случае, когда для поиска вершины с минимальным d [ v ] просматривается все множество вершин, а для хранения величин d - массив, время работы алгоритма есть O ( n 2 + m ). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
Для разреженных графов (то есть таких, для которых m много меньше n 2 ) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d [ i ], тогда время извлечения вершины из U станет log n , при том, что время модификации d [ i ] возрастет до log n . Так как цикл выполняется порядка n раз, а количество релаксаций не больше m , скорость работы такой реализации O ( n*log n + m*log n ).
Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O ( log n ), а уменьшение значения в среднем за O ( 1 ), то время работы алгоритма составит O ( n*log n + m ).
Условие з адач и : Найти кратчайший путь от вершины 1 к вершине 6 следующего графа (рис.3):
Решение : Каждой вершине графа сопоставим метку - минимальное известное расстояние от этой вершины до вершины 1. Метка самой вершины 1 полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки.
На каждом шаге из ещё не посещённых вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом.
Вершины, в которые ведут рёбра из u , назовем соседями этой вершины. Для каждого непосещённого соседа вершины u рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Шаг 1. (см. рис.4) Минимальную метку имеет вершина 1. Её соседями являются вершины 2 и 3.
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, т. е значение её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 3 = 3. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 3.
Аналогичным образом получаем новую метку 3-й вершины, равную 4.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра).
Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Шаг 2. (см. рис.5) Ближайшей из непосещенных вершин является вершина 2 с меткой 3. Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину.
Соседями вершины 2 являются вершины 1 и 4. Вершина 1 уже посещена. Рассмотрим вершину 4. Если идти в неё через 2, то длина такого пути будет равна 3 + 5 = 8. Присваиваем ей метку 8.

Шаг 3. (см. рис.6) Рассмотрим вершину 3. Ее соседями являются вершины 1, 4 и 5.
Следующий сосед вершины 3 - вершина 4, так имеет минимальную метку из непосещённых вершин. Если идти в неё через 3, то длина такого пути будет равна 4 + 2 = 6. Это значение меньше текущей метки, поэтому меняем метку четвертой вершины на 6.
Рассмотрим вершину 5. Если идти в неё через 3, то длина такого пути будет равна 4 + 3 = 7. Присваиваем ей метку 7. Пометим стрелкой путь от вершины 1 к вершине 4 наименьшей длины.
Шаг 4. (см. рис.7) Рассмотрим вершину 4. Ее соседями являются вершины 2, 3, 5 и 6.
Рассмотрим вершину 5. Если идти в неё через 4, то длина такого пути будет равна 6 + 6 = 12. Но это значение больше текущей метки, поэтому метку вершины 5 не меняем. Пометим стрелкой путь от вершины 1 к вершине 5 наименьшей длины.
Рассмотрим вершину 6. Если идти в неё через 4, то длина такого пути будет равна 6 + 8 = 14. Присваиваем ей метку 14.
Шаг 5. (см. рис.8) Рассмотрим вершину 5. Ее соседями являются вершины 3, 4 и 6.
Рассмотрим вершину 6. Если идти в неё через 5, то длина такого пути будет равна 7 + 9 = 16 < 14, значит, метку вершины 6 не меняем. Пометим стрелкой путь от вершины 1 к вершине 6 наименьшей длины.
У целевой вершины 6 не осталось непосещенных соседей. Алгоритм закончен.
Ответ : Кратчайший путь от вершины 1 к вершине 6: 1-3-4-6, его длина 14.
1. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М.: "Вильямс", 2006. - С.189-195.
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М.: "Вильямс", 2006. - С.1296.
3. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование", Минск, Вышейшая школа, 2001г.
4. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.
5. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.
6. Белов Теория Графов, Москва, "Наука", 1968.
7. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.
8. Оре О. Теория графов. - М.: Наука, 1980.
9. Исмагилов Р.С., Калинкин А.В. Материалы к практическим занятиям по курсу: Дискретная математика по теме: Алгоритмы на графах. - М.: МГТУ, 1995
10. Смольяков Э.Р. Введение в теорию графов. М.: МГТУ, 1992
11. Дейкстра Э. Дисциплина программирования = A discipline of programming. - 1-е изд. - М.: Мир, 1978. - С.275.
12. Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming. - 1-е изд. - М.: Мир, 1975. - С.247.
13. E. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V.1 (1959), P.269-271
Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе. курсовая работа [625,4 K], добавлен 30.09.2014
Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера. презентация [150,3 K], добавлен 16.01.2015
Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности. курсовая работа [228,5 K], добавлен 30.01.2012
История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни. курсовая работа [636,2 K], добавлен 20.12.2015
Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях. дипломная работа [145,5 K], добавлен 19.07.2011
Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов. реферат [220,4 K], добавлен 22.11.2010
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов". курсовая работа [2,4 M], добавлен 08.10.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Алгоритм Дейкстры контрольная работа. Математика.
Технико Экономическое Обоснование Систем
Статья: К вопросу о творческих связях Есенина и Гейне
Курсовая работа: Муниципальные финансы
Реферат: Права женщин в международном праве
Курсовая работа: Государственное управление и его принципы в ситуации социального и политического конфликта
Лабораторные Работы По Объектам Морской Техники
Качество процессов регулирования.
Реферат: Жилье как объект имущественных прав
Курсовая работа: Проблемы реформирования системы оплаты труда в условиях перехода к рыночной экономике. Скачать бесплатно и без регистрации
Английский Контрольная Работа 1 Класс
Контрольная Работа По Обществознанию 11
Курсовая работа: Разработка СУБД Записная книжка руководителя
Курсовая работа по теме Перспективные направления развития услуг санатория-профилактория "Березки"
Классификация признаков смерти
Шпаргалки: История психологии.
Курсовая работа: Аутстаффинг, аутсорсинг в управлении
Измерение Теплоемкости Твердого Тела Лабораторная Работа
Доклад по теме Уретрит
Аргументы К Сочинению Егэ Про Войну
Реферат: Холодное лезвие - технологии охлаждения DLADE-серверов
Особенности расследования взяточничества - Государство и право курсовая работа
Мир исламской культуры - Культура и искусство курсовая работа
Проверочный расчет КБТ при бурении с дополнительной нагрузкой - Геология, гидрология и геодезия контрольная работа