Урок 17
§11.1. Моделирование на графах

САМОЕ ГЛАВНОЕ

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

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

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

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

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

1) присутствие нескольких игроков;
2) неопределённость поведения игроков, связанная с имеющимися у каждого из них несколькими вариантами действий;
3) различие (несовпадение) интересов игроков;
4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);
5) наличие правил поведения, известных всем игрокам.

Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии.

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

Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.

Вопросы и задания

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

2. С помощью алгоритма Дейкстры найдите кратчайший путь между вершинами А и G следующего графа:

Cкачать материалы урока