Моделирование на графах

Ключевые слова
алгоритм Дейкстры
динамическое программирование
теория игр
стратегия игры
дерево игры
выигрышная стратегия
выигрышная позиция игрока
проигрышная позиция игрока

Кратчайший путь между вершинами графа
Путь между вершинами А и В графа считается кратчайшим, если:
эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным)
сумма весов ребер, соединяющих эти вершины, минимальна (для взвешенного графа)
Поиск оптимального транспортного маршрута, проектирование инженерных сетей и линий электропередач приводят к задаче поиска кратчайшего пути.

Построение дерева решений
9
13
4
2
6
5
10
A
B
D
C
E
С
C
5
10
6
16
9
14
4
2
11
Задание 1. На рисунке представлена схема дорог, связывающих населённые пункты A, B, C, D, E, F. Вес ребра означает стоимость проезда между двумя населенными пунктами. Определить минимальную стоимость проезда из пункта E в пункт C.
A
B
D
C
E
Алгоритм построения дерева решений, как правило, используется для нахождения кратчайшего пути в ориентированном графе.
Ответ: 11

Алгоритм Дейкстры
9
13
4
2
6
5
10
2
Задание 2. Определить минимальное расстояние от вершины A до F.
B
A
E
D
C
E
A
B
C
D
0
Ответ: 15
?
Можно ли, используя алгоритм Дейкстры, найти наибольшее расстояние от вершины-источника до остальных вершин?
Какие следует внести изменения?
Можно ли этот алгоритм применить к орграфу (ориентированному графу)?
Алгоритм Дейкстры служит для нахождения кратчай-шего пути между вершиной (источником) и всеми остальными вершинами графа.

Метод динамического программирования
Задание 3. Все улицы одного из кварталов города N прямые с односторонним движением и пересекаются под прямым углом. Если не поворачивать, то можно проехать с южной окраины на северную или с западной на восточную. Длины переулков равны, но каждый участок характеризуется количеством ям на дороге. Необходимо выбрать лучший маршрут проезда от пункта A в пункт B.
0
4
2
7
16
13
8
Как определить маршрут движения?
Попасть в вершину B можно только из двух вершин. Значение лучшего варианта зависит не только от веса ребер, но и от того, с каким «результатом» можно добраться до этих двух вершин.
Существует рекурсивное решение этой задачи.
Рекурсивное решение этой задачи
не оптимально по скорости выполнения.
Решение методом динамического программирования опирается на те же утверждения.
При заполнении будем двигаться от левого нижнего угла к правому верхнему.
11
9
13
15
15
14
2+7<4+8
Вариант проезда от начала движения сначала на север, потом на восток лучше.
25
17
14

Формулы закрашенных ячеек электронной таблицы (стиль ссылок R1C1)
Метод динамического программирования
7
=0
=МИН(R[2]C+R[1]C;RC[-2]+RC[-1])
=R[2]C+R[1]C
=RC[-2]+RC[-1]
Показать значения формул

Метод динамического программирования
A
7
const n=7;
var A: array [1..n, 1..n] of integer;
i,j,k: integer;
begin // порядок: 4, 3, 9, 2, 8, ..., 15
for i:=1 to n do
for j:=1 to n do
if (i+j) mod 2 <>0 then
read(A[i,j]);
for i:=3 to n do
for j:=3 to n do
if (i+j)mod 2 =0 then
if A[i,j-1]+A[i,j-2]
then A[i,j]:=A[i,j-1]+A[i,j-2]
else A[i,j]:=A[i-1,j]+A[i-2,j];
write(A[n,n]);
end.
A
k:=3;
for j:=1 to n div 2 do
begin
k:=k+2;
end;
A[1,1]:=0;
A[k,1]:=A[k-1,1]+A[k-2,1];
A[1,k]:=A[1,k-1]+A[1,k-2];

Знакомство с теорией игр
Теория игр — раздел современной математики, связанный с решением многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях.
Игра выступает в качестве математической модели некоторой ситуации и понимается как процесс, в котором участвуют две и более стороны, ведущие борьбу за реализацию своих интересов.

Знакомство с теорией игр
X0
В1
В1
В1
X1
X1
В2
В2
Задание 4. Чеширский кот предложил сыграть в игру с одной фигурой на части шахматной доски. Вы и кот ходите по очереди. За один ход фигуру можно пере-местить на одну клетку в направлении, указанном стрелками. Выигрывает тот, кто сделал последний ход.
Найдем такую клетку, ход в которую означает выигрыш для игрока, занявшего эту позицию, и проигрыш для соперника.
Отметим эту клетку как проигрышную – X0 (для того, кто должен сейчас выполнять ход).
Индекс означает коли-чество ходов из этой позиции до развязки игры.
Найдем клетки, из ко-торых можно поставить фигуру в позицию X0. Отметим их знаком В1.
Для четырех позиций определено возможное развитие игры, при условии грамотной игры обоих игроков.
Из отмеченных клеток существует только один вариант хода игрока.
Клетки являются про-игрышными в один ход (ходящего игрока) – X1. Из каждой существует единственный вариант развития событий.
Из клеток можно пойти в три различные клетки. Какие варианты следует выбрать?
Метки клеток В2.
Хотите я дам вам возможность пойти первым?
В2
X2
В2
В3
В3
В3
В2
В2

В таблице представлена вся информация об игре. Обозначены все клетки являющиеся выигрышными и все клетки, которые не-обходимо избегать. Игрок, который делает первый ход, обладает выигрышной стратегией.
Кто из игроков обладает выигрышной стратегией для игры на том же поле если фигуру можно передвигать на любое количество кле-ток строго вверх или строго вправо. Началь-ное положение фигуры – левый нижний угол. Проигрывает тот, кто делает последний ход.
Знакомство с теорией игр
Ответ

2-ой игрок
1-ый игрок
2-ой игрок
1-ый игрок
Знакомство с теорией игр
B1
Назовите позицию, из которой игрок, выполняющий первый ход, выигрывает своим первым или вторым ходом при любой игре соперника. При этом он не может гарантированно выиграть своим первым ходом. Ответ обосновать.
A
B
C
D
1
2
3
4
B2
C2
D2
B4
B3
C4
D3
D3
Для обладающего выигрышной стратегией указывается только один ход, который приведет к победе. Для игрока, у которого нет стратегии, рассматриваются все варианты.

Знакомство с теорией игр
Признаки игры
присутствие нескольких игроков
неопределённость поведения игроков, связанная с имеющимися у каждого из них несколькими вариантами действий
различие (несовпадение) инте-ресов игроков
взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков)
наличие правил поведения, известных всем игрокам

Самое главное
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. С их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.
Путь между вершинами А и В графа считается кратчайшим, если эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным), или если сумма весов ребер, соединяющих эти вершины, минимальна (для взвешенного графа).
Для определения кратчайшего пути между вершинами графа используются алгоритм построения дерева решений, алгоритм Дейкстры, метод динамического программирования и другие алгоритмы.
Важную роль в решении многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях, играет теория игр.

Самое главное
Игра, выступающая в качестве математической модели, характеризуется:
присутствием нескольких игроков;
неопределённостью, связанной с поведением игроков, у каждого из которых есть несколько вариантов действий;
различием (несовпадением) интересов игроков;
взаимосвязанностью поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);
наличие правил поведения, известных всем игрокам.
Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии. В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им предсказать варианты развития игры. Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.