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

11.1. Алгоритмы нахождения кратчайших путей между вершинами графа (Метод динамического программирования)

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

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

С помощью графа начальные условия могут быть заданы так, как показано на рисунке 3.17.

Рис. 3.17. Лабиринт

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

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

Ответ равен числу в правом верхнем углу таблицы.

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

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