Лабораторная работа по «Дискретной математике»

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Факультет дистанционного образования (ФДО)

27.03.04 - Управление в технических системах. Направленность (профиль) программы - «Управление в робототехнических системах»

Отчет

Лабораторная работа №2

по дисциплине: «Дискретная математика»

Вариант №11

Томск 2023

Задание 1. Решить задачу нахождения кратчайшего маршрута на взвешенном графе с помощью алгоритма Дейкстры.
Исходные данные:
вершина  – начальная;
вершина  – конечная.
r[0,1] = 12 r[4,7] = 34 r[6,3] = 13 r[5,7] = 43
r[0,2] = 10 r[4,2] = 18 r[6,7] = 35 r[5,4] = 46
r[0,3] = 29 r[2,5] = 21 r[2,1] = 3 r[6,5] = 11
r[1,4] = 25 r[2,6] = 15 r[3,2] = 32
Построим граф [pic 1][pic 2]

[pic 3]

За текущую рассматриваемую вершину с постоянной пометкой возьмем вершину 0

Присвоим L(0)=0 L(i)=  [pic 4]

[pic 5]

Найдем прямое отображение для текущей выбранной вершины 0 это будут вершины 1, 2, 3
Все вершины, входящие в прямое отображение имеют временные пометки. Посчитаем их значение:
L(1)min(∞ ; 0+12)=12 меняем метку
L(2)min(∞ ; 0+10)=10 меняем метку
L(3)min(∞ ; 0+29)=29 меняем метку
Имеем метки вершин:
L(1)=12 L(5)=∞
L(2)=10 L(6)= ∞
L(3)=29 L(7)= ∞
L(4)=∞
Минимальную метку, равной 10, имеет вершина 2
За следующую метку возьмем вершину 2, а метка 0 становится постоянной

[pic 6]

Найдем прямое отображение для текущей рассматриваемой вершины 2 это будут вершины 0, 1, 6, 3, 4. Все вершины, кроме 0, входящие в прямое отображение имеют временные пометки, поэтому посчитаем их значение:
L(1)min(12; 10+3)=12 оставляем метку
L(4)min(∞; 10+18)=28 меняем метку
L(3)min(29; 10+32)=29 оставляем метку
L(6)min(∞; 10+15)=25 меняем метку
Имеем метки вершин:
L(1)=12
L(3)=29
L(4)=28
L(6)=25
L(5)= ∞
L(7)= ∞

[pic 7]

Помечаем 2 как рассмотренную

Найдем прямое отображение для текущей рассматриваемой вершины 1, это будут вершины 0, 2, 4. Для 0, 2 метки постоянные. Для 4 временные метки поэтому рассчитаем

L(4)min(28; 12+25)=28 оставляем метку. Помечаем 1 как рассмотренную

[pic 8]

Перейдем к вершине 3. Найдем прямое отображение для текущей рассматриваемой вершины 3: 0, 2, 6. Для 0, 2 метки постоянные. Для 6 временные метки поэтому посчитаем L(6)min(25 ; 13+29)=25 оставляем метку.
Имеем следующие временные метки
L(3)=29
L(4)=28
L(6)=25
L(5)= ∞
Помечаем 3 как рассмотренную

[pic 9]

Перейдем к вершине 6 Найдем прямое отображение для выбранной рассматриваемой вершины 6, это будут вершины 2, 3, 5, 7 Для 3, 2 метки постоянные. Для 5, 7 посчитаем их значения.
L(X5)min( ∞; 11+25)=36 меняем метку
L(X7)min(∞ ; 35+25)=60 меняем метку
Имеем следующие временные метки

L(5)= 36
L(7)=60
L(4)=28

Все смежные вершины рассмотрены помечаем вершину 6 как рассмотренную

[pic 10]

Перейдем к вершине 5. Найдем прямое отображение для текущей рассматриваемой вершины 5 это буду вершины 4, 6, 7. Для 6 метка постоянная. Для 4, 7 посчитаем их значения.
L(4)min(28 ; 36+46)=28 оставляем метку
L(7)min(60 ; 36+43)=60 оставляем метку
L(4)=28
L(5)=36
L(7)=60
Все вершины рассмотрены, помечаем оставшиеся вершины: 4, 5, 7 как рассмотренные

[pic 11]

Все вершины имеют постоянные метки, алгоритм окончен.
Находим кратчайший путь от вершины 0 в вершину 7.
Построение кратчайшего маршрута пройдем обратный путь от 7 к 0.

7 последовательно используем соотношение

L(x*i)+c( x*i, xi)=L( xi)

где L(i) - пометка рассматриваемой вершины

 L(x*i) - пометка предшествующей вершины вершине i

с - вес ребра соединяющий вершины x*i и вершину i
L(7)=60
L(5)+c(5, 7)=36+43 L(7)
L(6)+c(6, 7)=35+25= L(7)
В вершину 7 попали из вершины 6.
L(6)=25
L(3)+c(3, 6)=13+29≠ L(6)
L(2)+c(2, 6)=10+15=L(6)
В вершину 6 попали из вершины 2.

Из вершины 2 попали в вершину 0, так как 10 минимальное значение.

[pic 12]
Ответ: кротчайший путь из 0 в 7 имеет длину 60 и проходит по вершинам: 0, 2, 6, 7.