close

Вход

Забыли?

вход по аккаунту

?

Информационные модели на графах

код для вставки
ИНФОРМАЦИОННЫЕ МОДЕЛИ НА
ГРАФАХ
Демонстрация основных понятий
14.01.2018
Информатика
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
2
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
Граф (неориентированный граф) - это непустое множество
вершин V и ребер E. Граф отображает элементный состав
системы и структуру связей между ними.
1
2
ОБОЗНАЧЕНИЯ:
ребро
– ВЕРШИНА
Связи между вершинами:
3
V={1, 2, 3}
E={(1,2),(2-3),(1,3)}
– РЕБРО, линия
– ДУГА, направленная линия
3
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
Ориентированный граф – граф, рёбрам которого присвоено
направление.
2
1
I
дуга
II
III
IV
3
4 группы крови и возможность переливания
крови одной группы другой
4
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
Взвешенный граф — граф, каждому ребру или вершине
которого поставлено в соответствие некоторое значение (вес).
b
1
М
2
67
a
Л
3
В
80
c
вес
45
62
73
К
Населённые пункты и расстояние между
ними
5
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
Путь в графе — последовательность вершин, имеющая
для каждой вершины ребро, соединяющее её со
следующей вершиной в последовательности.
Путь обозначается A-B-C-F.
Длина пути — сумма весов всех рёбер входящих в него.
6
ОСНОВНЫЕ ПОНЯТИЯ ГРАФОВ
Способы представления графов:
B
A
• перечисление всех ребер графов;
8
1
• таблица смежности.
E
C
4
3
1
10
D
1 способ (перечисление всех
ребер графа):
(AC;8), (AD;10), (BE;1), (BD;4),
(CE;3), (CD;1).
2 способ (таблица смежности):
Вершина
A
B
C
D
E
A
0
0
8
10
0
B
0
0
0
4
1
C
8
0
0
1
3
D
10
4
1
0
0
E
0
1
3
0
0
7
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
8
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
ЗАДАЧА
Имеется
взвешенный
граф
G={V, E}. Каждому ребру (i, j)
назначен вес wij.
Граф представлен
смежности.
таблицей
Заданы начальная вершина А и
конечная вершина Е.
Требуется найти
путь из А в Е.
кратчайший
A
A
B
B
C
E
2 10 8 16
2
9
C 10 9
D
D
8
E 16
1
1
3
3
4
11
4 11
9
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Такую таблицу называют
весовой матрицей.
Части таблицы, разделённые
диагональю – симметричны,
т.е. содержат одни и те же
данные.
Следовательно, можно рассматривать данные любой
половины таблицы
A
A
B
B
C
E
2 10 8 16
2
9
C 10 9
D
D
8
E 16
1
1
3
3
4
11
4 11
10
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Построим по таблице граф. Расставим на рёбрах вес.
A
В
2
1
8
9
10
16
3
C
4
D
11
E
11
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Алгоритмы поиска кратчайшего пути в графе
Алгоритм
Применение
Алгоритм Дейкстры
Находит кратчайший путь от одной вершины до всех
остальных во взвешенном графе, wij > 0
Алгоритм Беллмана-Форда
Находит кратчайшие пути от одной вершины графа до
всех остальных во взвешенном графе
Алгоритм поиска А*
Находит кратчайший путь с наименьшим весом от одной
вершины к другой, используя алгоритм поиска по
первому наилучшему совпадению на графе
Алгоритм Флойда-Уоршелла
Находит кратчайшие пути между всеми
взвешенного ориентированного графа
Алгоритм Джонсона
Находит кратчайшие пути между всеми парами вершин
взвешенного ориентированного графа
Алгоритм Ли
Находит путь между вершинами s и t, содержащий
минимальное количество промежуточных вершин
вершинами
12
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Решим задачу, используя алгоритм Дейкстры.
Суть алгоритма
Каждой вершине из V поставим метку — минимальное
известное расстояние от этой вершины до a.
Алгоритм работает пошагово — на каждом шаге он
«посещает» одну вершину и пытается уменьшать метки.
Работа алгоритма завершается, когда все вершины
посещены.
13
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Ставим
метки:
помечаем
вершину А – 0, как начало
пути, остальным вершинам
присвоим знак бесконечности
.

0
В
2
A
8
9
10
16

4
C
1

3
D
11
 E
14
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Минимальную метку имеет
вершина
А,
её
соседями
являются вершины B, D, C, E.

0
В
2
A
8
9
10
16

4
C
1

3
D
11
 E
15
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Посещаем вершину B, так как
длина до нее минимальна.
Длина пути в вершину В через
вершину А равна сумме метки
вершины А и длины ребра А-В:
0+2=2
2<, поэтому новая
вершины В равна 2.
метка

В
0
2
A
8
9
10
16

4
C
1

3
D
11
 E
16
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Аналогичную
операцию
проделываем с тремя другими
соседями вершины A — D, C,
E.

В
0
2
A
8
9
10
16

4
C
1

3
D
11
 E
17
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Все соседи вершины А проверены. Текущее минимальное
расстояние до вершины А
считается окончательным и
пересмотру не подлежит.
Вычеркнем её из графа, чтобы
отметить, что эта вершина
была посещена.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
8
3
D
11
E
18
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Шаг алгоритма повторяется.
Снова находим «ближайшую»
из непосещённых вершин. Это
вершина B с меткой 2.
Снова пытаемся уменьшить
метки
соседей
выбранной
вершины. Соседями вершины
B являются вершины A, C и D.
Первый (по порядку) сосед
вершины B — вершина A. Но
она уже посещена, поэтому с
вершиной A ничего не делаем.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
8
3
D
11
E
19
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Следующий сосед вершины B
— вершина D, так как имеет
минимальную
метку
из
вершин, отмеченных как не
посещённые.
Если идти в неё через B, то
длина такого пути будет равна
3 (2+1=3).
Текущая метка вершины D
равна 8.
Поскольку 3<8, устанавливаем
метку вершины B равной 3.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
8
3
D
11
E
20
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Ещё один сосед вершины B —
вершина C. Если идти в неё
через B, то длина такого пути
будет равна сумме 2+9=11.
Но текущая метка вершины С
равна 10, а 10<11, поэтому
метка не меняется.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
8
3
D
11
E
21
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Все
соседи
вершины
B
просмотрены, замораживаем
расстояние до неё и помечаем
её как посещённую.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
3
3
D
11
E
22
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Повторяем шаг алгоритма,
выбрав вершину D. После её
«обработки» получим такие
результаты.
2
В
0
2
A
8
9
10
10
16
4
16
C
1
3
3
D
11
E
23
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Помечаем вершину
посещённую.
D
как
2
В
0
2
A
8
9
10
6
16
4
14
C
1
3
3
D
11
E
24
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Выполняем последний шаг
алгоритма, выбрав вершину C.
Соседями
вершины
C
являются вершины A, B, D и
E. Вершины A, B, D уже
отмечены как посещённые,
поэтому обрабатываем только
вершину Е.
После её «обработки» получим
такие результаты.
2
В
0
2
A
8
9
10
6
16
4
14
C
1
3
3
D
11
E
25
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Помечаем вершину
посещённую.
С
как
В
Из вершины Е нет непосещённых вершин.
Помечаем вершину
обработанную.
2
Е
0
2
A
8
как
9
10
6
16
4
10
C
1
3
3
D
11
E
26
АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ
Алгоритм заканчивает работу,
когда
нельзя
больше
обработать
ни
одной
вершины.
В
данном
примере
все
вершины зачёркнуты.
Кратчайший путь от вершины
A до вершины Е:
2
В
0
2
A
8
9
10
6
16
4
A-B-D-C-E = 10
10
C
1
3
3
D
11
E
27
СПАСИБО ЗА ВНИМАНИЕ!
14.01.2018
Информатика
Автор
gosteeva66
Документ
Категория
Образование
Просмотров
8
Размер файла
295 Кб
Теги
информационные
1/--страниц
Пожаловаться на содержимое документа