§ 11. Моделирование на графах
Информатика. 11 класса. Босова Л.Л. Оглавление
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. Например, с их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов. Необходимость решения задач, связанных с поиском кратчайшего пути на графе, возникает при проектировании инженерных сетей и линий электропередач, в микроэлектронике и во многих других случаях.
Путь между вершинами А и В графа считается кратчайшим, если:
• эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным);
• сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа).
Есть множество алгоритмов определения кратчайшего пути между вершинами графа, в том числе:
1) алгоритм построения дерева решений;
2) алгоритм Дейкстры;
3) метод динамического программирования.
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Алгоритм построения дерева решений)
Алгоритм построения дерева решений, как правило, используется для нахождения кратчайшего пути в ориентированном графе. Его мы рассмотрели в предыдущем параграфе.
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Алгоритм Дейкстры)
Алгоритм Дейкстры служит для нахождения кратчайшего пути между одной конкретной вершиной (источником) и всеми остальными вершинами графа.
Суть алгоритма состоит в следующем. Каждой вершине графа ставится в соответствие метка — минимальное известное расстояние от источника до этой вершины. Метка самого источника полагается равной 0. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки.
На первом шаге расстояние от источника до всех остальных вершин неизвестно. Метки вершин (кроме источника) считаются равными бесконечности, все вершины считаются непосещёнными.
Далее, из всех непосещённых вершин выбирается вершина, имеющая минимальную метку. Для каждого из соседей этой вершины (кроме отмеченных как посещённые) рассчитывается новая длина пути, как сумма значений текущей метки этой вершины и длины ребра, соединяющего её с соседом. Если полученное значение длины меньше значения метки соседа, то значение метки заменяется полученным значением длины. После рассмотрения всех соседей вершина помечается как посещённая. Этот шаг алгоритма повторяется, пока есть непосещённые вершины. Работа алгоритма завершается, когда все вершины посещены.
Рассмотрим работу алгоритма на примере. На рисунке 3.12 кружками обозначены вершины графа, в кружки вписаны имена вершин. Вершины соединены линиями — рёбрами графа. Около каждого ребра обозначен его «вес» — длина пути. Рядом с каждой вершиной дана метка — длина кратчайшего пути в эту вершину из вершины А: для вершины А — это 0, для всех других вершин она неизвестна и обозначена знаком «бесконечность».
Рис. 3.12. Алгоритм Дейкстры. Начальное состояние
Минимальную метку (0) имеет вершина А. Её соседи — вершины В, С, D. Очерёдность рассмотрения соседей: В, D, С. После изменения их меток получим результат, представленный на рисунке 3.13.
Рис. 3.13. Алгоритм Дейкстры. Шаг 1
После изменения меток всех соседей вершины А она помечается как просмотренная. Теперь минимальная метка из непросмотренных вершин у вершины В. Её соседи — вершины D и Е. Так как 5 + 9 > 10, метка вершины D не изменяется. Вершина Е получает метку 19 (рис. 3.14).
Теперь минимальная метка из непросмотренных вершин у вершины D. Её соседи — вершины С, Е и F. Так как 10 + 3 < 15, метка вершины С изменяется. Вершина F получает метку 18. Метка вершины Е не изменяется (рис. 3.15).
Рис. 3.14. Алгоритм Дейкстры. Шаг 2
Рис. 3.15. Алгоритм Дейкстры. Шаг 3
Далее в качестве вершин с минимальными метками будут поочерёдно рассматриваться вершины С, F и Е. К изменению меток соседних с ними вершин это не приведёт (рис. 3.16).
Полученные в результате работы алгоритма метки вершин графа — это и есть кратчайшие расстояния от вершины А до каждой из этих вершин.
Рис. 3.16. Алгоритм Дейкстры. Результат работы
11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Метод динамического программирования)
Метод динамического программирования основан на том, что процесс решения задачи разбивается на стадии (шаги), на каждой из которых принимаются решения, приводящие к достижению поставленной цели.
Предположим, персонажу некоторой игры необходимо пройти по лабиринту из пункта А в пункт В, набрав при этом как можно меньше штрафных баллов, количество которых указано в клетках лабиринта, причём перемещаться можно только вверх или вправо.
С помощью графа начальные условия могут быть заданы так, как показано на рисунке 3.17.
Рис. 3.17. Лабиринт
Составим таблицу, в которой каждая ячейка будет соответствовать определённой клетке лабиринта. Числа в ячейках будут равны минимальному числу штрафных баллов, которое можно получить, пройдя путь от начала до соответствующей клетки.
Заполнять таблицу будем снизу вверх и слева направо. При этом для заполнения каждой новой ячейки будем рассматривать числа двух соседних с ней заполненных ячеек, находящихся слева от неё и под ней. Будем выбирать наименьшее из этих двух чисел, прибавлять к ним число текущей ячейки и результат записывать в неё.
Ответ равен числу в правом верхнем углу таблицы.
Давайте считать, что числа, обозначающие веса вершин рассмотренного графа, — это призовые баллы, которые можно получить, пройдя по соответствующим клеткам лабиринта. Самостоятельно подсчитайте, какое максимальное число призовых баллов можно набрать, пройдя этот лабиринт.
11.2. Знакомство с теорией игр
Рассмотрим несколько примеров.
Пример 1. Это задачка из учебника информатики для 4 класса 1).
1) Семёнов A.Л. Информатика: Учеб. пособие для 4 кл. нач. шк. В 2 ч. Ч. 2 / A.Л. Семёнов, Т. А. Рудченко. — М.: Просвещение, 2008. — 48 с. : ил.
Алёша Попович и Добрыня Никитич воюют с девятиглавым змеем. По очереди богатыри ходят к его пещере и срубают 1, 2 или 3 головы. Как начавшему бой Алёше обрести славу победителя змея (срубить последнюю голову), если и Добрыня готов приложить все усилия, чтобы стать победителем в этой битве?
Изобразим на числовой линейке текущее число голов змея:
Здесь: 9 — начальное значение; 0 — конечное значение (победа).
Алёша обретёт славу победителя, если после его последнего удара у змея останется 0 голов. Для этого нужно, чтобы после очередного удара Добрыни у змея осталось 3, 2 или 1 голова. Иначе говоря, позиции 3, 2 и 1 являются для Алёши выигрышными (как, впрочем, для любого из богатырей, кому они достаются в качестве исходных при последнем ударе). Выигрышные и проигрышные позиции на числовой линейке будем помечать буквами «В» и «П» соответственно:
Если Добрыня выйдет на бои с черырехголовым змеем (будет находиться в позиции 4), то любым своим ударом он создаст Алёше условия для выигрыша (переведёт Алёшу в выигрышную позицию). Следовательно, задача Алёши на предыдущем шаге состоит в том, чтобы перевести Добрыню в эту заведомо проигрышную для него позицию:
Четырёхголового соперника Алёша сможет обеспечить Добрыне, если сам будет находиться в одной из позиций 7, 6 или 5:
Любой удар Добрыни приведёт к благоприятному для Алёши результату только в том случае, если Добрыня выйдет на бой с восьмиголовым змеем:
Следовательно, первым своим ударом Алёша должен срубить змею одну голову.
Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Выигрышная стратегия может быть только у одного игрока.
Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации при различной игре противника.
На рисунке 3.18 в форме дерева представлена выигрышная стратегия для Алёши. Поэтому для Алёши всегда указывается один ход («Ход А»), обеспечивающий требуемый результат. А вот для Добрыни, фактически выступающего в качестве соперника, рассматриваются все возможные варианты («Ход Д»).
Рис. 3.18. Дерево выигрышной стратегии для Алёши
Пример 2. А эта задача из открытого банка заданий ЕГЭ по информатике (fipi.ru).
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может выполнить одно из следующих действий:
• добавить в кучу один камень (+ 1);
• добавить в кучу два камня (+ 2);
• увеличить количество камней в куче в 3 раза (х 3).
Например, имея кучу из 5 камней, за один ход можно получить кучу из 6, 7 или 15 камней.
У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 46 или больше камней. Будем считать, что в начальный момент в куче S камней, 1 ? S ? 45.
Выясним, при каких значениях числа S Петя может выиграть первым ходом.
Если S = 45, то, добавив в кучу один камень (+ 1), два камня (+ 2) или утроив количество камней в ней (х 3), Петя становится победителем.
Если S = 44, то стать победителем можно, если добавить в кучу два камня (+ 2) или утроить количество камней в ней (х 3).
Если S = 43, то Петя становится победителем, утроив количество камней в куче (х 3). Также можно действовать для любого S ? 16 (16 х 3 = 48, 15 х 3 = 45).
Итак, Петя может выиграть, если S = 16, …, 45 — это его выигрышные позиции. Для выигрыша Пете достаточно увеличить количество камней в 3 раза.
При меньших значениях S за один ход нельзя получить кучу, в которой будет 46 или более камней.
Если же в куче будет 15 камней, то после любого хода Пети своим первым ходом может выиграть Ваня. Действительно, при S = 15 после первого хода Пети («Ход П») в куче будет 16, 17 или 45 камней.
Любой из этих случаев является выигрышным для делающего ход Вани («Ход В»), которому для победы достаточно увеличить количество камней в 3 раза (рис. 3.19).
Рис. 3.19. Позиция 15 — выигрышная для Вани
Теперь попробуем определить значения S, при которых у Пети будет выигрышная стратегия, причём Петя не сможет выиграть первым ходом, но сможет выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Мы выяснили, что S = 15 — проигрышная позиция для любого игрока. Если Петя своим первым ходом сможет перевести в неё Ваню, то что бы ни делал последний, сам он выиграть не сможет, но переведёт в выигрышную позицию своего соперника. 15 камней Петя может получить при S = 14 (+ 1), S = 13 (+ 2) или S = 5 (х 3). Других вариантов для S нет (рис. 3.20).
Рис. 3.20. Позиции 5, 13, 14 — выигрышные для Пети
Представим всю информацию на числовой линейке:
Найдём на ней такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Здесь речь идёт о проигрышной позиции для первого игрока. Следовательно, искать значение S надо среди позиций, не отмеченных как выигрышные.
Пусть S = 12. Каким бы ни был ход Пети, им он переведёт своего соперника в выигрышную позицию: 13(12 + 1), 14 (12+ 2) или 36 (12 х 3). В последнем случае Ваня имеет возможность выиграть своим первым же ходом (36 х 3), а в первых двух случаях он должен перевести соперника в проигрышную позицию S = 15, что обеспечит ему выигрыш вторым ходом. Следовательно, позиция S = 12 — проигрышная для Пети. На дереве решений наши рассуждения могут быть представлены так, как показано на рисунке 3.21.
Рис. 3.21. Позиция 12 — проигрышная для Пети
Если вместо S = 12 взять S = 11, то приведёт ли любой ход Пети Ваню к выигрышу? Подойдёт ли для этой цели S = 10? Обоснуйте свой ответ.
Примеры, которые мы рассмотрели, имеют самое непосредственное отношение к теории игр — разделу современной математики, связанному с решением многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях.
Игра выступает в качестве математической модели некоторой ситуации и понимается как процесс, в котором участвуют две и более стороны, ведущие борьбу за реализацию своих интересов. При этом игра характеризуется такими признаками, как:
1) присутствие нескольких игроков;
2) неопределённость поведения игроков, связанная с имеющимися у каждого из них несколькими вариантами действий;
3) различие (несовпадение) интересов игроков;
4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);
5) наличие правил поведения, известных всем игрокам.
Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии.
Примеры, которые мы рассмотрели, относятся к так называемым играм с полной информацией. В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры.
Тем, кто хочет получить более полное представление о теории игр, рекомендуем познакомиться с книгой Александра Шеня «Игры и стратегии с точки зрения математики». Электронная версия книги является свободно распространяемой и доступна по адресу http://www.mcnmo.ru/free-books/shen/shen-games.pdf.
САМОЕ ГЛАВНОЕ
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. С их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.
Путь между вершинами А и В графа считается кратчайшим, если эти вершины соединены минимальным числом рёбер (в случае, если граф не является взвешенным) или если сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа).
Для определения кратчайшего пути между вершинами графа используются алгоритм построения дерева решений, алгоритм Дейкстры, метод динамического программирования и другие алгоритмы.
Важную роль в решении многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях, играет теория игр.
Игра, выступающая в качестве математической модели некоторой ситуации, характеризуется такими признаками, как:
1) присутствие нескольких игроков;
2) неопределённость поведения игроков, связанная с имеющимися у каждого из них несколькими вариантами действий;
3) различие (несовпадение) интересов игроков;
4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);
5) наличие правил поведения, известных всем игрокам.
Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии.
В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры.
Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.
Вопросы и задания
2. С помощью алгоритма Дейкстры найдите кратчайший путь между вершинами А и G следующего графа:
§ 10. Модели и моделирование
§ 11. Моделирование на графах
§ 12. База данных как модель предметной области