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

1. МОДЕЛИРОВАНИЕ НА ГРАФАХ

11
ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ

2. КЛЮЧЕВЫЕ СЛОВА

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

3. КРАТЧАЙШИЙ ПУТЬ МЕЖДУ ВЕРШИНАМИ ГРАФА

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

4. ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЙ

Найдём кратчайший путь от вершины A до вершины F в графе.
A
7
B
6
E
4
1
9
D
13
7
B
F
D
A
E
F
C
E
19
16
3
D
C
20
E
F
F
F
20
22
17
18
Алгоритм построения дерева решений, как правило, используется для
Кратчайший кратчайшего
путь из A в Fпути
имеет
вид A – B – E – F графе
нахождения
в ориентированном
F

5. АЛГОРИТМ ДЕЙКСТРЫ

Алгоритм Дейкстры служит для нахождения кратчайшего пути
между одной конкретной вершины (источником) и всеми
остальными вершинами графа.
Суть алгоритма состоит в следующем. Каждой вершине графа ставится в
соответствие метка — минимальное известное расстояние от источника
до этой вершины.
Метка самого источника полагается равной 0.
Алгоритм работает пошагово — на каждом шаге он «посещает» одну
вершину и пытается уменьшать метки.

6. ПРИМЕР РАБОТЫ АЛГОРИТМА ДЕЙКСТРЫ

∞
Вершины графа
F
7
8
8
∞ С
3
∞
∞ 10
E
9
14
Рёбра графа
D
10
A
0
5
Имена вершин
B ∞
Вес ребра – длинна пути
Метка – длинная кратчайшего пути
Для вершины А – метра равна 0, для всех других вершин она неизвестна и обозначается знаком ∞

7. ПРИМЕР РАБОТЫ АЛГОРИТМА ДЕЙКСТРЫ

∞
18
F
7
15
13
∞
8
19
∞
8
С
3
E
10
∞ 10
D
15
10
A
9
5
14
B ∞
5
0
Результат
Шаг 2
1работы
3
Полученные
Минимальную
Изменим
После
Так
Теперь
Вершина
Далее
какизменения
в5
минимальная
качестве
+метки
F 9получает
результаты
> метку
10,
B, вершин
меток
метка
D, имеет
метку
C.
метка
всех
с 18.
из
вершина
соседей
вершины
непосещённых
Метка
минимальными
работы
вершины
алгоритма
вершины
А.
D не
Её изменяется.
соседи
вершин
метками
Е не
Аметки
она
–у будут
помещается
Вершина
вершины
изменяется
поочерёдно
вершин
графа
Е
B,
D.
B.получает
C,
Её
рассматриваться
как–D.
соседи
посещённая.
это иотметку
есть
–
Очерёдность
19
вершины
кратчайшее
DC,ирасстояние
C,
FEE.
рассмотрения
ииE.
F.КТак как
от 10
соседей:
+
изменению
вершины
3 < 15, метка
B,
А до
меток
D, C.
каждой
вершины
соседних
из С с
изменится.
ними
вершин.
вершин это не приведёт

8. МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВНАИЯ

Метод динамического программирования основан
на том, что процесс решения задач разбивается на
решение более простых (меньшего размера) задачи,
при этом каждый раз применяются решения,
приближающие к достижению поставленной цели.

9. МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВНАИЯ

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

10. МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВНАИЯ

3
3
6
В
5
3
8
4
3
2
8
9
А
9
1
7
3 + 8 = 11
11
17
8 ++ 36 == 11
95
5
3++8
13
2==16
5
10
13
5
8
8
16
13 + 4
9 = 20
22
10 + 7 = 17
11
11
17
17
8
8
16
20
3
5
13
22
А
9
10
17
Ответ: 17

11. ЗНАКОМСТВО С ТЕОРИЕЙ ИГР

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

12. ПРИМЕР 1

Алёша Попович и Добрыня Никитич воюют с девятиглавым змеем.
По очереди богатыри ходят к его пещере и срубают 1, 2 или 3
головы.
Как начавшему Бой Алёше обрести
славу победителя змея (срубить
последнюю голову), если и Добрыня
готов приложить все усилия, чтобы
стать победителем в этой битве?

13. ПРИМЕР 1

Любой
Число
Для
Если
Следовательно,
Четырёхглавого
этого
Добрыня
голов:
удар
нужно,
Добрыни
выйдет
соперника
задача
чтобы
приведёт
на
после
Алёши
бой
Алёши
сочередного
на
четырёхглавым
к благоприятному
предыдущем
сможет удара
обеспечить
змеем,
шаге
Добрыни
длясостоит
Алёши
Добрыне,
то любым
у змея
в
осталось
своим
том,
если
результату
чтобы
сам
ударом,
будет
3,вперевести
2том
или
он
находится
случае,
1
создаст
голова.
Добрыню
если
Алёше
в одной
Добрыня
в условия
эту
из позиций
заведомо
выйдет
для –выигрыша.
проигрышную
на
7, 6бой
илис 5:
для него позицию:
восьмиголовым
змеем:
-3
9
П
8
В
7 -2В
6 -1 В
5
П
4
В
3
В
2
В
1
0
9
8
7
4
3
2
1
0
Начальное
значение
6
5
Конечное
значение
Проигрышная
Следовательно,
Алёша
В
– выигрышные
обретет славу
первым
позиции.
победителя,
своим
ударом
еслиАлёша
после его
должен
последнего
срубить
позиция Добрыни
удара
П
змею
– Проигрышные
одну
останется
голову.0 голов.
позиции.

14. ВЫИГРЫШНАЯ СТРАТЕГИЯ

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

15. ДЕРЕВО ВЫИГРЫШНОЙ СТРАТЕГИИ

В форме дерева представлена выигрышная стратегия для Алёши. Поэтому для Алёши
всегда указывается один ход («Ход А»), обеспечивающий требуемый результат. А вот
для Добрыни, фактически выступающего в качестве соперника, рассматриваются все
возможные варианты («Ход Д»).
Ход А
Ход Д
Ход А
Ход Д
–1
7
–3
4
9
–2
8
3
2
–3
–1
–1
–2
Ход А
6
–3
5
–2
–1
4
4
1
–3
–2
–1
0
0
0

16. ПРИМЕР 2

Два игрока Петя и Ваня, играют в следующую игру. Перед
игроками лежит куча
камней. Игроки ходят по очереди,
первый
+1
6
Один ход
Один ход
ход делает
Петя.
×3
5
15
+2
Доступное действие за один ход
7
У каждого игрока есть неограниченное количество камней. Игра завершится в тот
момент, когда количество камней в куче превышает 45. Победителем
считается
Увеличить
Добавить в кучу
в кучу 2
игрок, сделавший
последний ход,Добавить
т. е. первым
получившим
кучу,камне
в которой
будет 46
количество
в
один камень
камня
куче в 3 раза
или больше камней.
(+ 1)
(+ 2)
В начальный момент в куче S камней: (× 3)
1 ≤ S ≤ 45

17. ПРИМЕР 2

Выигрыш Пети первым ходом
S = 45
+1
S = 44
+2
S = 43
×3
+2
+2
+2
Или
Или
×3
×3
Еслименьшем
Петя
При
может
в куче выиграть,
будет
значениях
15 камней,
если
S за то
один
S = 16,
ход
после
нельзя
любого
… 45
получить
–хода
это выигрышные
Пети
кучу,свои
в которой
позиции.
будет
первым
46ходом
иДля
более
этого
может
камней.
достаточно
выиграть
увеличить количество камней в 3
Ваня.
раза.
Так же можно действовать для любого S ≥ 16 (16 × 3 = 48), (15 × 3 = 45)

18. ПРИМЕР 2

Ход П
Выигрыш Вани
Или
S = 45
16
×3
S = 16, 17
+2
×3
48
+1
+2
8
+1
Ход В
17
×3
51
×3
45
×3
Любой из этих случаев является выигрышным для делающего ход Вани,
которому для победы достаточно увеличить количество камней в 3 раза.
135

19. ПРИМЕР 2

S =Если
Выигрышная
15 – Петя
проигрышная
стратегия
своим первым
позиция
Пети,ходом
при
для
условии,
сможет
любого перевести
что
игрока.
он не сможет
Ваню ввыиграть
S = 15, топервым
чтобы
ходом,
не делал
но сможет
последний,
выиграть
самвторым,
он выиграть
не зависимо
не сможет,
от того,
но переведёт
как будетвходить
Ваня.
выигрышную позицию соперника.
Ход В
Ход П
Ход В
Выигрыш Пети
S = 14
S = 13
S=5
+1
+2
×3
14
13
5
16
+1
+2
×3
×3
48
+1
15
+2
17
×3
51
×3
45
×3
135

20. ПРИМЕР 2

Ход П
Проигрыш
1 для
2 Пети
3 4
5
6
7
+2
Ход В
8
В
Ход ПВ
П
ВХод В
В
В
В
9 10 11 12 13 14 15 16 ×317 … 45 46
14
+1
+1
48
16
+2
+2
+1
Найдём
значение
S, при
котором
у Вани
есть
выигрышная
стратегия,
позволяющая
×3же ходом (36 ×
Речь
идёт
о проигрышной
позиции
первого
игрока:
В последнем
случае
Ваня
имеет
возможность
выиграть
своим
первым
12 или вторым
13
15
17 и при этом 51
ему
при любой
игре вПети,
у Вани
3), авыиграть
в первыхему
двухпервым
случаях
он долженходом
перевести
соперника
проигрышную
позицию
нет
которая позволит
ему гарантированно
выиграть
первым ходом.
S = стратегии
15, чтобы ,обеспечить
ему выигрыш
вторым ходом.
Следовательно,
позиция S =
×3
12 – проигрышная для Пети.
S13
= 12
×3
×3
+1
108
36
45
ход Пети приведёт
в выигрышную
позицию соперника
36
12 +Любой
1
14
12 + 2
46
12 × 3

21. ПРИЗНАКИ ИГРЫ

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

22. ИГРЫ С ПОЛНОЙ ИНФОРМАЦИЕЙ

В играх с полной информацией участники знают все
ходы, сделанные до текущего момента, равно как и
возможные стратегии поражения
противников, что позволяет им
предсказать последующее
развитие игры

23.

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

24.

САМОЕ ГЛАВНОЕ
Игра, выступающая в качестве математической модели некоторой
ситуации, характеризуется такими признаками, как:
1) Присутствие нескольких игроков;
2) Неопределённость поведения игроков, связанная имеющаяся у каждого
из них несколькими вариантами действий;
3) Различие (несовпадение) интересов игроков;
4) Взаимосвязанность поведения игроков (результат, получаемый каждым
из них, зависит от поведения всех игроков);
5) Наличие правил поведения, известных всем игроков.
Игра может быть представлена в виде дерева, каждая вершина которого
соответствует ситуации выбора игрока своей стратегии.
В играх с полной информацией участники знают все ходы, сделанные до
текущего момента, равно как и возможные стратегии противников, что
позволяет им предсказать последующее развитие игры.
Выигрышная стратегия – это правило, следуя которому игрок выигрывает
независимо от того, как играет противник.

25. ВОПРОСЫ И ЗАДАНИЯ

В решении каких прикладных задач используются алгоритмы
нахождения кратчайшего пути между заданными вершинами в
графе?

26. ВОПРОСЫ И ЗАДАНИЯ

С помощью алгоритма Дейкстры найдите кратчайший путь
между вершинами A и G следующего графа:
B
23
A
25
35
22
12
19
D
C
E
23
20
F
H
14
24
16
G

27. ВОПРОСЫ И ЗАДАНИЯ

Бобёр Билли любит жёлуди. Он
хочет поплыть по течению и
собрать все жёлуди на островах,
мимо которых будет проплывать.
Увы, течение реки настолько
сильное, что он может плыть
только вниз по течению. Какое
максимальное количество жёлудей
он сможет собрать?
Решите эту задачу,
воспользовавшись методом
динамического программирования.

28. ВОПРОСЫ И ЗАДАНИЯ

На столе лежат 25 спичек. Играют двое. Игроки по очереди
могут взять от одной до четырёх спичек. Кто не может сделать
ход (так как спичек не осталось), проигрывает. Другими
словами, выигрывает взявший последнюю спичку.
Выясните, у кого из игроков есть выигрышная стратегия.

29. ВОПРОСЫ И ЗАДАНИЯ

Выясните, у кого из двух игроков есть выигрышная стратегия в
такой игре: начальная позиция – на столе лежат 107 спичек, за
один ход можно брать 1 или 2 спички. Выигрывает тот, кто взял
последнюю спичку.

30. ВОПРОСЫ И ЗАДАНИЯ

Два игрока играют в следующую игру. Перед ними лежат две
кучи камней, в первой из которых 2, во второй – 3 камня. У
каждого игрока неограниченное количество камней. Игроки
ходят по очереди. Ход состоит в том, что игрок или увеличивает
число камней в какой-то куче в 3 раза, или добавляет 3 камня в
любую из куч. Выигрывает игрок, после хода которого общее
число камней в двух кучах становится не менее 35. Кто
выигрывает игрок делающий ход первым, или игрок, делающих
ход вторым?

31. ВОПРОСЫ И ЗАДАНИЯ

В начальный
Два
игрока, Петя
момент
и Ваня,
в куче
играют
былов Sследующую
камней, 1 ≤игру.
S ≤ 46.
Перед
игроками лежит
Выполните
следующие
куча камней.
задания,
Игроки
в каждом
ходят случае
по очереди,
обосновывая
первый
ход делает
свой
ответ. Петя. За один ход игрок может добавить в кучу 1
камень или 5 камней. Например, имея кучу из 10 камней, за
1)
2)
3)
4)
Укажите
все такие
такое
два
значение
значения
значение
S,
значения
при
S,
S,
при
котором
при
S,
которых
при
котором
которых
Вани
у15
Пети
Петя
есть
Петя
есть
не
выигрышная
может
может
один
ход может
получить
кучу
из
11 уили
камней
У
каждого
выиграть
выигрышная
стратегия,
за
позволяющая
один
стратегия,
ход.
ход,
Обоснуйте,
но
причём
ему
при
выиграть
любом
Петя
что
ходе
не
найдены
первым
может
Пети
выиграть
или
Ваня
все
нужные
вторым
может
за
игрока, чтобы делать ходы, есть неограниченное количество
значения
выиграть
один
ходом
ход,
при
своим
S,
но
любой
иможет
укажите
первым
игре
выиграть
выигрывающие
Пети,
ходом.
однако
своим
Опишите
вторым
у Вани
позиции.
выигрышную
нет
ходом
стратегии,
независимо
камней.
Игра
завершится
в тот
момент,
когда
количество
стратегию
от
которая
того,
как
позволит
Вани.
будет
ходить
ему
гарантированно
Ваня.
Для
указанных
выиграть
значений
первым
S
ходом.
камней в куче становится не менее 47. Победителем считается
опишите
Для
указанного
выигрышную
значения
стратегию
S опишите
стратегию
игрок,
сделавший
последний
ход,Пети.
т. е.выигрышную
первым получившим
Вани.
Постройте
дерево
всех
партий,
возможных
при
этой
кучу, в которой будет 47 или больше камней.
выигрышной стратегии Вани.

32.

ОПОРНЫЙ КОНСПЕКТ
Путь между вершинами является кратчайшим, если эти вершины
соединены минимальным числом рёбер или если сумма всех
рёбер, соединяющих эти вершины, минимальна.
Алгоритмы поиска кратчайшего пути
Поиск дерева решений
Алгоритм Дейкстры
Метод динамического
программирования
Теория игра – раздел современной математики, связанный с
решением многих задач в различных областях, где необходимо
изучение поведения человека и животных в различных ситуациях.
Выигрышная стратегия – это правило, следуя которому игрок
выигрывает от того, как играет противник.