Графовые модели. Основные понятия. Принцип планирования многошаговых процессов

Основные понятия
Графовые модели изучает специальная теория называемая теорией графов.
Граф – это схема состоящая из вершин соединённых между собой системой линий, которая носит название рёбер графа

Основные понятия
Рёбра могут быть ориентированными и не ориентированными.
Ориентированным называется ребро имеющие направление. Ориентированное ребро также называется дугой.
Неориентированным – не имеющие направление.

Основные понятия
Основоположником теории графов, принято считать Леонарда Эйлера, который в 1736г. Решил задачу о Кёнигсбергских мостах.
Задача состоит в том что нужно составить маршрут проходящий через все части суши. Начинающийся в любой из них, проходящий по каждому мосту 1 раз и заканчивающийся в пункте выхода.
Эйлер изобразил в качестве вершин участки суши, а в качестве рёбер моты и доказал, что задача не имеет решения.

Основные понятия
Сама теория графов стала развиваться в 30-х годах XX в.
Основу теории графов составляет сеть. Сеть – это граф, каждой дуге которого ставиться в соответствии число или несколько чисел.
Любая сеть характеризуется:
Структурой, которая показывает какие вершины и как соединены между собой.
Параметрами дуг, которые могут отражать либо время переезда, либо расстояние.
Каждая дуга обозначается(i-j), где i– это вершина из которой берёт своё начало дуга, j- это вершина, которой заканчивается соответствующая дуга.

Принцип планирования многошаговых процессов
Данный принцип (метод) был изобретен в 1947 году американским ученым Беллманом.
Он позволяет находить оптимальное решение не на одном отдельно взятом шаге, а искать выгоду для всего процесса в целом.
Ричард Эрнст Беллман

Постановка задачи
Дана сеть дорог. Нужно составить маршрут, который проходит через пункты, начинающийся в пункте выезда и заканчивающийся в конечном пункте. Такой чтобы минимизировать некоторые параметры, например, суммарное расстояние.
4
1
2
3
6
5
2
3
3
1
6
7
8
5
4
8
1
4
9
5
9
2
6
7
7

Решение
Задача является многошаговой, на каждом шаге происходит выбор пункта въезда . Выделим все шаги :
1
2
3
2
1
4
2
3
6
5
3
6
5
8
4
7
4
3
6
7
8
5
4
1
5
9
2
7
8
9
6
7
1 шаг
2 шаг
3 шаг
4 шаг

Решение
На 4 шаге
На 3 шаге
j
На 2 шаге
На 1 шаге
i
i
i