- Понятие «модель»
- Этапы компьютерного моделирования
- Графические модели: графы, деревья
- Алгоритмы нахождения кратчайшего пути между вершинами графа
- знать, что такое модель, виды информационных моделей
- знать алгоритмы поиска кратчайшего пути между вершинами графа
- уметь описывать объект (процесс) с помощью графических моделей
- уметь работать с готовыми моделями на графах
- Какие ассоциации у вас возникают со словом «модель»?
Понятие модель
В процессе познания окружающего мира человек стремится изучать различные объекты и процессы, их структуру, свойства, взаимосвязи. Часто в обучающих целях предлагается исследовать не реальный объект, а его модель. Делается это по разным причинам: оригинал может быть слишком большим (планета) или маленьким (атом), исследовать его может быть дорого (космический корабль), опасно для жизни (ядерный взрыв) или вообще невозможно (например, Солнечная система или Древний Рим). И тогда на помощь нам приходят модели. Моделирование используется во многих областях знаний.
Модель — это новый объект, который обладает существенными для исследования признаками другого объекта или процесса (оригинала) и может быть использован вместо него.
Моделирование — это создание и исследование моделей для изучения оригинала.
Этапы компьютерного моделирования
В информатике особое внимание уделяется компьютерному моделированию информационных моделей. Компьютерное моделирование включает в себя процесс реализации и исследования модели с помощью компьютера.
Выделим этапы создания информационной модели:
- Постановка цели моделирования;
- Выделение свойств объекта-оригинала, существенных с точки зрения цели моделирования;
- Проработка взаимосвязей между значениями выбранных свойств (формы: словесная, табличная, графическая, математическая и т. д.).
Средствами создания компьютерной модели могут быть языки программирования, электронные таблицы, специальные математические приложения и т. д.
В настоящее время компьютер является самым эффективным инструментом для моделирования различных процессов, таких как, например, прогноз погоды, климатические изменения в природе, прогнозирование цен на финансовых рынках и т. д.
Рассмотрим этапы компьютерного моделирования:
- Постановка задачи и её анализ,
- Построение информационной модели,
- Разработка компьютерной модели,
- Компьютерный эксперимент,
- Анализ результатов эксперимента,
- Принятие решений.
Графические модели: графы, деревья
Существует множество видов моделей. Рассмотрим более подробно самые наглядные модели — графические.
Граф — это множество элементов (вершин графа) и связей между ними (рёбер).
С помощью графа можно описать любую сложную структуру объекта. Например, транспортная система, схема железнодорожного транспорта или метро, организм человека, компьютерная сеть и т. д.
Свойства графа:
- К каждой вершине может вести множество рёбер;
- Каждая вершина может быть связана с любым количеством других вершин;
- Каждая связка может иметь направление и вес.
Дуга — это ребро, которое имеет направление (стрелку).
Вершина, из которой выходит дуга, называется начальной, а куда
входит — конечной.
Граф называется неориентированным, если все его вершины соединены ребрами.
Граф называется ориентированным, если его вершины соединены дугами.
Граф называется взвешенным, если его вершины или рёбра имеют вес.
Граф называется связным, если между любыми его вершинами есть путь (последовательность вершин, где каждая следующая вершина связана с предыдущей). Замкнутый путь называется циклом.
Частным случаем графа является дерево. Дерево является многоуровневой структурой (иерархией). Поэтому его удобно использовать для представления, например, родственных связей.
Дерево — это граф, в котором нет циклов.
Поддерево — это часть дерева, которая тоже является деревом.
Так же как и граф, дерево состоит из вершин и рёбер. Самая первая вершина дерева называется корнем. Конечные вершины называются листьями.
Для хранения информации о вершинах графа и связях между ними используют таблицу, которая называется матрица смежности. В ней указываются наличие связи в виде 1 или отсутствие в виде 0. Для взвешенного графа такая матрица называется весовой матрицей. В ней указывается не наличие связи, а вес.
Алгоритмы нахождения кратчайшего пути между вершинами графа
Огромное количество жизненных задач требует умения определять оптимальный маршрут. В информатике такие задачи называются задачами поиска кратчайшего пути.
Путь между вершинами А и В является кратчайшим, если:
- эти вершины соединены минимальным числом рёбер (если граф не взвешенный);
- сумма весов рёбер, соединяющих эти вершины, минимальна (если граф взвешенный).
Существует следующие алгоритмы поиска кратчайшего пути:
- дерево решений;
- алгоритм Дейкстры;
- метод динамического программирования.
Рассмотрим их на следующих примерах.
Пример 1
Рис. 1. Пример 1
Решение
Рис. 2. Пример 1 (решение)
Построим полное дерево перебора решений для графа на рис. 2.
Ответ: 11.
Упражнение 1
Постройте дерево решений по матрице смежности.
Таблица 1. Упражнение 1
|
|
А
|
В
|
C
|
D
|
E
|
F
|
|
А
|
|
7
|
5
|
|
|
|
|
В
|
7
|
|
|
7
|
8
|
|
|
С
|
5
|
|
|
4
|
|
|
|
D
|
|
7
|
4
|
|
|
3
|
|
E
|
|
8
|
|
|
|
1
|
|
F
|
|
|
|
3
|
1
|
|
И найдите длину кратчайшего пути между пунктами А и F.
Пример 2
Рис. 3. Пример 2
Найдём кратчайший путь между пунктами А и F (рис. 3), воспользовавшись алгоритмом Дейкстры.
Решение
Каждой вершине графа поставим в соответствие метку — минимальное известное расстояние от источника до этой вершины. Начальная вершина А имеет метку 0. Из вершины А мы можем попасть в вершины С, B, D и получить в них следующие метки: С (11), D(21), B(12). Далее будем двигаться последовательно из каждой вершины, прибавляя к данным меткам вес той вершины, в которую мы идём. Из вершины С двигаться больше некуда. Из вершины В можно попасть в вершину D, E, F. Суммируем метку B = 12 c новыми значениями меток вершин: D(12 + 14 = 26), E(12 + 13 = 25), F(12 + 5 = 17). Заметим, что значение D(21) < D(26), поэтому дальше будем двигаться из него. При этом мы уже достигли нужной вершины F(17). Проверим оставшиеся траектории из D в F (26 + 14 = 40) и из Е в F (25 + 7 = 32). Таким образом, получаем ответ — 17.
Ответ: 17.
Упражнение 2
Рис. 4. Упражнение 2
Пример 3
Исполнитель Собиратель двигается по клеткам квадрата 4 на 4 и собирает монеты достоинством от 1 до 50, которые лежат в клетках. При этом Собиратель может двигаться только на одну клетку вправо или вниз за одно перемещение. При попытке выйти за границу квадрата исполнитель разрушается. Посещая клетку, Собиратель забирает монету, которая в ней лежит. Определите максимальную сумму монет, которую может собрать Собиратель, перемещаясь из верхней левой в нижнюю правую клетку.
Таблица 2. Пример 3
|
12
|
3
|
1
|
10
|
|
2
|
4
|
6
|
7
|
|
9
|
8
|
6
|
21
|
Решение
Для решения данной задачи удобно применить метод динамического программирования. Этот метод основан на том, что процесс решения задачи разбивается на шаги, на каждом из которых принимаются решения, приводящие к нужному результату.
Т. к. Собиратель двигается сверху вниз, начнём движение с самой нижней клетки и будет двигаться наверх. В клетку 21 мы можем попасть из клетки 15 или 6. Найдём сумму монет по обеим траекториям.
Таблица 3. Решение примера 3 (1)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36
|
|
|
|
27
|
21
|
Далее рассчитаем сумму монет по строке и столбцу.
Таблица 4. Решение примера 3 (2)
|
|
|
|
53
|
|
|
|
|
43
|
|
|
|
|
36
|
|
44
|
35
|
27
|
21
|
Между клетками 27 и 36 робот выбирает ту, которая больше, и складывает с текущей.
Таблица 5. Решение примера 3 (3)
|
|
|
|
53
|
|
|
|
|
43
|
|
|
|
38
|
36
|
|
44
|
35
|
27
|
21
|
Аналогично посчитаем значения всех остальных клеток.
Таблица 6. Решение примера 3 (4)
|
69
|
57
|
54
|
53
|
|
56
|
53
|
49
|
43
|
|
54
|
43
|
38
|
36
|
|
44
|
35
|
27
|
21
|
Ответ: 69.
Упражнение 3
Исполнитель Собиратель двигается по клеткам квадрата 5 на 5 и собирает монеты достоинством от 1 до 50, которые лежат в клетках. При этом Собиратель может двигаться только на одну клетку вправо или вниз за одно перемещение. При попытке выйти за границу квадрата исполнитель разрушается. Посещая клетку, Собиратель забирает монету, которая в ней лежит. Определите минимальную сумму монет, которую может собрать Собиратель, перемещаясь из верхней левой в нижнюю правую клетку.
Таблица 7. Упражнение 3
|
12
|
3
|
1
|
10
|
2
|
|
2
|
4
|
6
|
7
|
3
|
|
10
|
5
|
2
|
15
|
2
|
|
9
|
8
|
6
|
21
|
5
|
|
3
|
2
|
1
|
5
|
6
|
Итоги
- Граф — это нелинейная структура данных. Граф можно представить как множество вершин и рёбер (дуг) между ними.
- Дерево — это частный случай графа.
- Графы как информационные модели широко применяются во многих жизненных задачах.
- Путь между двумя вершинами считается кратчайшим, если эти вершины соединены минимальным числом рёбер (не взвешенный граф) или сумма весов рёбер, соединяющих эти вершины, минимальна (граф взвешенный).
- Для определения кратчайшего пути между вершинами графа используют дерево решений, алгоритм Дейкстры, метод динамического программирования и др.
Контрольные вопросы
- Приведите примеры моделей из различных областей знаний.
- Какие из этих моделей можно представить в виде графа?
- Какие этапы создания информационной модели можно выделить?
- В чём состоит алгоритм Дейкстры?
- В чём принцип динамического программирования?
- Как можно применять алгоритм «Дерево решений»?
Упражнение 1
12
Упражнение 2
6
Упражнение 3
42
