Практическая работа № 28. Алгоритмы моделирования кратчайших путей между вершинами (построение дерева решений, алгоритм Дейкстры, метод динамического программирования). Элементы теории игр (выигрышная стратегия)

1. Цель работы:

Освоить алгоритмы моделирования кратчайших путей между вершинами (построение дерева решений, алгоритм Дейкстры, метод динамического программирования). Ознакомиться с элементами теории игр (выигрышной стратегией).

2. Оборудование, приборы, аппаратура, материалы:

Компьютер с выходом в интернет, инструкционная карта.

3. Краткие теоретические сведения:

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

Путь между вершинами A и B графа считается кратчайшим, если:

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

4. Задания

Задача 1.

На рисунке представлена схема дорог, связывающих населённые пункты A, B, C, D, E, F. Вес рёбер означает стоимость проезда между двумя населёнными пунктами. Определить минимальную стоимость проезда из пункта E в пункт C.

Решение:

1. Строим дерево решений, начиная с пункта E. В него можно попасть из пунктов B и D, проставляем вес каждого ребра.
2. Определяем, из каких вершин можно попасть в B, строим далее дерево решений, проставляем веса рёбер.
3. Следим, чтобы каждая ветка заканчивалась вершиной C.
4. Выбираем ветку с минимальной суммой весов – это и есть ответ.

Задача 2.

Определить минимальное расстояние от вершины A до F с помощью алгоритма Дейкстры.

Решение:

1. Обозначаем расстояние до исходной вершины A как 0, а до остальных – как ∞.
2. Находим вершину с минимальной меткой, определяем минимальное расстояние до смежных вершин, отмечаем вершину как рассмотренную.
3. Проверяем наличие непосещённых вершин.
4. Повторяем шаги, пока все вершины не будут обработаны.
5. В конце получаем минимальное расстояние до F.

Задача 3 (самостоятельная работа).

Рассчитать количество путей из пункта A в пункт Ж с помощью метода динамического программирования.

Задача 4.

Малыш и Фрекен Бок играют в игру. На столе лежат конфеты. Первым ходом Малыш делит конфеты на три непустых кучки, затем Фрекен Бок отдаёт две кучки Карлсону, а третью снова делит на три. Затем ходит Малыш, и процесс продолжается. Кто не может сделать ход, проигрывает.

Кто победит при верной игре, если на столе:
а) 9 конфет?
б) 7 конфет?
в) 12 конфет?
г) 14 конфет?

Решение:

1. Определяем проигрышные позиции (когда игрок не может сделать ход).
2. Если число конфет = 1 или 2, игрок проигрывает.
3. Если конфет 3, игрок может их разделить на три кучки по одной и выиграть.
4. Используем стратегию расчёта выигрышных и проигрышных позиций, строя дерево игры.

Задача 5.

В коробке 60 спичек. За один ход можно взять от 1 до 5 спичек. Проигрывает тот, кто не может сделать ход. Кто из игроков выиграет при правильной игре?

Заполните пробелы в тексте:
Если количество спичек меньше или равно 5, то тот игрок, чья очередь ходить, заканчивает игру и выигрывает.
Если же количество спичек равно 6, то игрок, чей ход был до появления этой позиции, своим следующим ходом заканчивает игру. Значит, эта позиция проигрышная для того, кто ходит.
Аналогично проигрышными являются позиции, когда количество спичек кратно 6. Значит, и позиция «60 спичек» является проигрышной для того, кто будет ходить, то есть для первого игрока.

---

5. Содержание отчёта:

1. Название работы.
2. Цель работы.
3. Задания и их решения.
4. Ответы на контрольные вопросы.
5. Вывод по работе.

---

6. Контрольные вопросы:

1. Граф – это …
2. Перечислите алгоритмы нахождения кратчайшего пути.
3. В чем заключается суть алгоритма Дейкстры?
4. Динамическое программирование – это …
5. Что значит выигрышная стратегия?

Вывод:

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

0 0 Пожаловаться