Практическая работа№4 по МДК 01.02: Математический аппарат для построения компьютерных сетей наименование работы: Решение задач по теории графов. Нахождение кратчайшего пути.

Смоленский колледж телекоммуникаций
(филиал) федерального государственного
бюджетного образовательного учреждения высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
















Практическая работа№4
по МДК 01.02: Математический аппарат для построения компьютерных сетей
наименование работы: Решение задач по теории графов. Нахождение кратчайшего пути.
для специальности: 09.02.02
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.



Смоленск, 2016

1. Цель работы: научиться находить кратчайшие пути в графе при помощи алгоритма Дейкстры.
2. Литература:
2.1. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд. / М.О. Асанов , В.А.Баранский , В.В. Расин - СПб. : Издательство «Лань» 2012 г. 368с. - ISBN 978-5-8114-1068-2
2.2. Мельников, О.И. Теория графов в занимательных задачах. Изд.4, испр. и доп./О.И. Мельников 2012. 240 с. М.: Книжный дом "Либриком" ISBN978-5-9775-0232-0
2. 3. Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения: учебник / Ф.А. Новиков. - СПб. : Питер 2012, 400с.- ISBN 978-5-496-00015-4

3. Подготовка к работе:
3.1. Повторить тему «Основные понятия графа».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулируйте определение графа?
3.3.2. Сформулируйте определение матрицы смежности?
3.3.3. Сформулируйте определение кратчайшего пути?

4. Основное оборудование:
4.1. не используется.

5. Задание:
Выполните задания согласно варианту.
Найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке.
Вариант 1 Вариант 2








Вариант 3 Вариант 4







Вариант 5 Вариант 6







Вариант 7 Вариант 8








Вариант 9 Вариант 10









6. Порядок выполнения работы:
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задания в соответствии с вариантом.
6.4. Ответьте на контрольные вопросы.

7. Содержание отчёта:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия заданий своего варианта.
7.3. Представить результат выполнения заданий.
7.4. Ответы на контрольные вопросы.
7.5. Вывод о проделанной работе.

8. Контрольные вопросы:
8.1.Чем отличается путь от маршрута?
8.2. Дайте определение понятию поиск кратчайшего пути?
8.3. Перечислите, какие алгоритмы по поиску кратчайшего пути вы знаете?
8.4. Сформулируйте определение взвешенного графа?
8.5. Сформулируйте определение ребра?



Составил преподаватель __________________________Скряго О.С.






9. Приложение:
Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.
Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 при положительных длинах дуг. Этот алгоритм предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны 13 EMBED Equation.3 1415 вершин, ближайших к вершине 13 EMBED Equation.3 1415 (близость любой вершины x к вершине 13 EMBED Equation.3 1415 определяется длиной кратчайшего пути, ведущего из 13 EMBED Equation.3 1415 в 13 EMBED Equation.3 1415). Пусть также известны сами кратчайшие пути, соединяющие вершину 13 EMBED Equation.3 1415 с выделенными m вершинами). Покажем теперь, как может быть определена 13 EMBED Equation.3 1415-я ближайшая к 13 EMBED Equation.3 1415 вершина.
Окрасим вершину 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 ближайших к ней вершин. Построим для каждой неокрашенной вершины 13 EMBED Equation.3 1415 пути, непосредственно соединяющие с помощью дуг 13 EMBED Equation.3 1415 каждую окрашенную вершину 13 EMBED Equation.3 1415 с 13 EMBED Equation.3 1415. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины 13 EMBED Equation.3 1415 в вершину 13 EMBED Equation.3 1415.
Какая же из неокрашенных вершин является 13 EMBED Equation.3 1415-й ближайшей к 13 EMBED Equation.3 1415 вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины 13 EMBED Equation.3 1415 в 13 EMBED Equation.3 1415-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число 13 EMBED Equation.3 1415 вершин, ближайших к вершине 13 EMBED Equation.3 1415.
Итак, если известны 13 EMBED Equation.3 1415 ближайших к 13 EMBED Equation.3 1415 вершин, то 13 EMBED Equation.3 1415-я ближайшая к 13 EMBED Equation.3 1415 вершина может быть найдена так, как это описано выше. Начиная с 13 EMBED Equation.3 1415, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины 13 EMBED Equation.3 1415 к вершине 13 EMBED Equation.3 1415.

Алгоритм работает только для графов без рёбер отрицательного веса.

Любая задача,требующая нахождения оптимальных маршрутов может быть выполнена с помощью алгоритма Дейкстры. Это касается и сетей, и транспортных потоков, и обработка графов. Очень часто используется не сам алгоритм в чистом виде, а его модификация.
Примеры:
1. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица,школа и т.д) в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.
2. Компьютерная игра. Указываете точку назначения для персонажа и он движется туда по кратчайшему маршруту. Это тоже алгоритм Дейкстры.
3. Дана сеть автомобильных дорог, соединяющих города Гомельской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Гомеля до каждого города области (если двигаться можно только по дорогам).
4. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Милана до Минска.
Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
OSPF разбивает процесс построения таблицы маршрутизации на 2 этапа.
Второй этап состоит в нахождении оптимальных маршрутов с помощью полученного графа. Задача нахождения оптимального пути на графе является достаточно сложной и ёмкой. В протоколе OSPF для её решения используется итеративный алгоритм Дейкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг - до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов".
Алгоритм
1. Каждой вершине 13 EMBED Equation.3 1415 в ходе алгоритма присваивается число 13 EMBED Equation.3 1415, равное длине кратчайшего пути из вершины 13 EMBED Equation.3 1415 в вершину 13 EMBED Equation.3 1415 и включающем только окрашенные вершины. Положить 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415 для всех остальных вершин графа. Окрашиваем вершину 13 EMBED Equation.3 1415 и полагаем 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415 – последняя окрашенная вершина.
2. Для каждой неокрашенной вершины 13 EMBED Equation.3 1415 пересчитывается величина 13 EMBED Equation.3 1415 по следующей формуле:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
3. Если 13 EMBED Equation.3 1415 для всех неокрашенных вершин, то алгоритм заканчивается т. к. отсутствуют пути из вершины 13 EMBED Equation.3 1415 в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина 13 EMBED Equation.3 1415 является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением 13 EMBED Equation.3 1415 и полагаем 13 EMBED Equation.3 1415.
4. Если 13 EMBED Equation.3 1415, кратчайший путь из 13 EMBED Equation.3 1415 в 13 EMBED Equation.3 1415 найден. Иначе переходим к шагу 2.
Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине 13 EMBED Equation.3 1415. Это дерево называют ориентированным деревом кратчайших путей. Путь из 13 EMBED Equation.3 1415 в 13 EMBED Equation.3 1415 принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.
Отметим, что главным условием успешного применения алгоритма Дейкстры к задаче на графе является неотрицательность длин дуг этого графа
Для графа с отрицательными весами применяется более общий алгоритм Алгоритм Дейкстры с потенциалами.
Пример выполнения задания.
Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:


Алгоритм
Конкретные действия

1.
Инициализация.
Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.
Задаем стартовые условия: d(1)=0, d(x)=
·.
Окрашиваем вершину № 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: 13 EMBED Equation.3 1415.
Составим матрицу длин кратчайших дуг для данного графа.
№/№
1
2
3
4
5
6

1
13 EMBED Equation.3 1415
7
9
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
14

2
7
13 EMBED Equation.3 1415
10
15
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

3
9
10
13 EMBED Equation.3 1415
11
13 EMBED Equation.3 1415
2

4
13 EMBED Equation.3 1415
15
11
13 EMBED Equation.3 1415
6
13 EMBED Equation.3 1415

5
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
6
13 EMBED Equation.3 1415
9

6
14
13 EMBED Equation.3 1415
2
13 EMBED Equation.3 1415
9
13 EMBED Equation.3 1415

или
13 EMBED Equation.3 1415


2.
Первый шаг.
Рассмотрим шаг алгоритма Дейкстры.
d(2)=min{d(2) ; d(1)+a(1,2)}=min{
·; 0+7}=7
d(3)=min{d(3) ; d(1)+a(1,3)}=min{
·; 0+9}=9
d(4)=min{d(4) ; d(1)+a(1,4)}=min{
·; 0+
·}=
·
d(5)=min{d(5) ; d(1)+a(1,5)}=min{
·; 0+
·}=
·
d(6)=min{d(6) ; d(1)+a(1,6)}=min{
·; 0+14}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=7.
Включаем вершину № 2 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,2).

3.
Второй шаг.
d(3)=min{d(3) ; d(2)+a(2,3)}=min{9; 7+10}=9
d(4)=min{d(4) ; d(2)+a(2,4)}=min{
·; 7+15}=22
d(5)=min{d(5) ; d(2)+a(2,5)}=min{
·; 7+
·}=
·
d(6)=min{d(6) ; d(2)+a(2,6)}=min{14; 7+
·}=14
Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=9.
Включаем вершину № 3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,3)

4.
Третий шаг.
d(4)=min{d(4) ; d(3)+a(3,4)}=min{22; 9+11}=20
d(5)=min{d(5) ; d(3)+a(3,5)}=min{
·; 9+
·}=
·
d(6)=min{d(6) ; d(3)+a(3,6)}=min{14; 9+2}=11
Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=11.
Включаем вершину № 6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,6)=(1,3)+(3,6)

5.
Четвертый шаг.
d(4)=min{d(4) ; d(6)+a(6,4)}=min{20; 11+
·}=20
d(5)=min{d(5) ; d(6)+a(6,5)}=min{
·; 11+9}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 4 и № 5 d(4)=d(6)=20.
Включаем вершину № 4 и № 5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,4)=(1,3)+(3,4) и (1,5)=(1,3)+(3,6)+(6,5).

6.
Заключение.
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=7
d(3)=1-3 Длина маршрута L=9
d(4)=1-3-4 Длина маршрута L=20
d(5)=1-3-6-5 Длина маршрута L=20
d(6)=1-3-6 Длина маршрута L=11


Пример выполнения задание № 2
Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:
Решение:

Алгоритм
Конкретные действия

1.
Инициализация.
Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1.
Задаем стартовые условия: d(1)=0, d(x)=
·.
Окрашиваем вершину № 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу: 13 EMBED Equation.3 1415.
Составим матрицу длин кратчайших дуг для данного графа.
№/№
1
2
3
4
5
6

1
13 EMBED Equation.3 1415
10
18
8
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

2
10
13 EMBED Equation.3 1415
16
9
21
13 EMBED Equation.3 1415

3
13 EMBED Equation.3 1415
16
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
15

4
7
9
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
12

5
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
23

6
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
15
13 EMBED Equation.3 1415
23
13 EMBED Equation.3 1415


или13 EMBED Equation.3 1415

2.
Первый шаг.
Рассмотрим шаг алгоритма Дейкстры.
d(2)=min{d(2) ; d(1)+a(1,2)}=min{
·; 0+10}=10
d(3)=min{d(3) ; d(1)+a(1,3)}=min{
·; 0+18}=18
d(4)=min{d(4) ; d(1)+a(1,4)}=min{
·; 0+8}=8
d(5)=min{d(5) ; d(1)+a(1,5)}=min{
·; 0+
·}=
·
d(6)=min{d(6) ; d(1)+a(1,6)}=min{
·; 0+
·}=
·
Минимальную длину имеет путь от вершины № 1 до вершины № 4 d(4)=8.
Включаем вершину № 4 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,4)

3.
Второй шаг.
d(2)=min{d(2) ; d(4)+a(4,2)}=min{10; 8+9}=10
d(3)=min{d(3) ; d(4)+a(4,3)}=min{18; 8+
·}=18
d(5)=min{d(5) ; d(4)+a(4,5)}=min{
·; 8+
·}=
·
d(6)=min{d(6) ; d(4)+a(4,6)}=min{
·; 8+12}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=10.
Включаем вершину № 2 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,2)

4.
Третий шаг.
d(3)=min{d(3) ; d(2)+a(2,3)}=min{18; 10+16}=18
d(5)=min{d(5) ; d(2)+a(2,5)}=min{
·; 10+21}=31
d(6)=min{d(6) ; d(2)+a(2,6)}=min{20; 10+
·}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=18.
Включаем вершину № 3 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (1,3)

5.
Четвертый шаг.
d(5)=min{d(5) ; d(3)+a(3,5)}=min{31; 18+
·}=31
d(6)=min{d(6) ; d(3)+a(3,6)}=min{20; 18+15}=20
Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=20.
Включаем вершину № 6 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (4,6)

6.
Пятый шаг.
d(5)=min{d(5) ; d(6)+a(6,5)}=min{31; 20+23}=31
Минимальную длину имеет путь от вершины № 1 до вершины № 5 d(5)=31.
Включаем вершину № 5 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину.
Согласно выражению это дуга (2,5)

7.
Заключение.
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(1)=1 Длина маршрута L=0
d(2)=1-2 Длина маршрута L=10
d(3)=1-3 Длина маршрута L=18
d(4)=1-4 Длина маршрута L=8
d(5)=1-2-5 Длина маршрута L=31
d(6)=1-4-6 Длина маршрута L=20

Ориентированное дерево с корнем в вершине №1:















Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 109
    Скряго о.С.
    Размер файла: 373 kB Загрузок: 17

Добавить комментарий