2015-06-28
1346
Динамическое программирование: поиск пути в матрице с накоплением минимальной (максимальной) суммы.
Довольно часто встречаются задачи, провоцирующие к применению алгоритмов перебора. Но простой подсчет числа вариантов убеждает в неэффективности такого подхода. Для решения подобных задач используется метод динамического программирования. Суть его заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая подзадача. Данный метод сродни методу математической дедукции, в которой для решения сложной задачи прибегают сначала к решению более простой. С точки зрения программирования динамический метод напоминает рекурсию.
Постановка задачи
Дана матрица, заполненная целыми положительными числами размерности n´m. По ней разрешается перемещаться только в двух направлениях – вправо и вниз. Требуется найти путь из верхнего левого угла матрицы в правый нижний, на котором набирается наибольшая сумма.
| Описание алгоритма Для решения задачи потребуется дополнительная матрица того же размера, что и исходная, которую мы будем формировать следующим образом: I. Заполнение матрицы происходит построчно справа налево сверху вниз. 1. В начальную точку (стартовый узел) новой матрицы записывается значение начального элемента исходной матрицы. | Исходная матрица
|
2. Начиная со стартового узла, анализируются значения узлов, из которых был возможен переход (т.е. сверху и слева) дополнительной матрицы. Выбирается максимальное значение из двух возможных, суммируется со значением текущего узла исходной матрицы и записывается в текущий узел вспомогательной матрицы.
| II. Просмотр заполненной матрицы в обратном направлении. Будем просматривать полученную матрицу с конечной вершины. 1. Встать в конечный узел. 2. Пока не достигнем начального узла: 1) Занести текущие координаты в какую-либо структуру данных (например, двумерный массив P, содержащий 2 строки и n*m столбцов). 2) Из двух узлов (верхнего и левого) выбрать тот, в котором значение больше. Перейти в него. 3. Вывести координаты начального узла. 4. Вывести заполненный путь в обратном порядке (т.к. просмотр шел с конечной вершины в начальную). 5. Вывести значение суммы. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Для реализации алгоритма без выделения обработки первого столбца и первой строки как при заполнении, так и при выводе пути, удобно воспользоваться барьерным способом: окружением матрицы дополнительными строками и столбцами. Т.е. к вспомогательной матрице допишем сверху строку и слева столбец, значения элементов которых не влияют на вычисление суммы и вывод пути. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
