Двумерное динамическое программирование — это применение методов динамического программирования для задач с двумя измерениями.
Введение
Под динамическим программированием понимается методика решения обширного набора задач, которая подразумевает использование решений вычлененных из общей задачи подзадач, для нахождения решения исходной задачи.
Значение термина «программирование» в формулировке «динамическое программирование» раньше имело несколько другую смысловую окраску, нежели сегодня. В то время, когда Ричард Беллман ввёл в обиход это сочетание слов, написание программ ещё не являлось широко известной профессией и даже названия такие специалисты ещё не имели. В то время под термином программирование понималось «планирование», а термин «динамическое программирование» означал составление оптимального плана многоэтапных процессов.
В обобщённом виде способ заключается в том, что одна исходная задача разбивается на некоторое количество подзадач таким образом, что все подзадачи решаются за счёт решения предыдущих подзадач. А финалом является решение исходной общей задачи. То есть на формальном языке, вначале формируется набор подзадач, которые располагаются в вершинах графа. Далее строятся ориентированные рёбра между подзадачами, в случае, если разрешение одной подзадачи способно оказать помощь в решении другой. И если в итоге построен не очень громоздкий ациклический граф (то есть, не имеющий циклов), то такую задачу возможно решить при помощи метода динамического программирования. Но, чтобы добиться решения задачи методом динамического программирования, необходимо выполнить следующие шаги:
- Выполнить разделение исходной задачи на ряд подзадач. Подзадачи должны выводиться одна из другой.
- Указать параметры, которые чётко и ясно задают подзадачу.
- Указать исходные данные и изначальное состояние.
- Определить параметры перехода между состояниями. Определение формулы, позволяющей получить решение текущей подзадачи на базе предыдущих.
- Определить условия перерасчёта.
- Сформировать общее решение задачи. Это может быть суммарный итог или максимальный результат из множества, другие варианты.
Двумерное динамическое программирование
Наиболее типичной задачей двумерного динамического программирования считается задача об определении маршрутов в двумерном прямоугольном поле. В различных постановках задачи требуется или найти общее количество возможных маршрутов или определить оптимальный по заданным параметрам маршрут. Рассмотрим в качестве примера первую версию задачи, то есть необходимо определить количество маршрутов.
Задана прямоугольная таблица, размером N на M, а исходная точка располагается в левой верхней клетке. Из этой точки позволено одним ходом перейти в соседнюю клетку только вправо или вниз. И есть ограничение, а именно запрещается находиться в заранее указанных точках таблицы. Требуется вычислить общее количество допустимых маршрутов, то есть проходящих только по допустимым клеткам, которые приводят в правую нижнюю клетку. Известно, также, что левая верхняя и правая нижняя клетки находятся в числе разрешённых.
Задана пара чисел N и M, которые определяют размеры таблицы (1
Рассмотрим второй вариант задачи с некоторыми уточнениями. Исходным является прямоугольное поле, имеющее размеры N на M клеток. Возможно делать шаги размером в одну клетку вправо, вниз или вправо-вниз по диагонали. Во все клетки вписаны некоторые натуральные числа. Требуется пройти из верхней левой клетки в правую нижнюю. Каждый маршрут имеет свой вес, который определяется суммой чисел, записанных во всех клетках по ходу маршрута.
Задано прямоугольное поле, имеющее размеры n на m клеток. Возможно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. Во все клетки вписано определённое натуральное число. Требуется попасть из верхней левой клетки в правую нижнюю. Весовая маршрутная характеристика определяется как сумма чисел во всех клетках, через которые проходит путь. Требуется также, определить маршрут, который имеет самый маленький вес. В этой задаче в клетку, имеющую координаты (i, j) возможно перейти из клеток, которые имеют координаты (i – 1, j), (i, j – 1) и (i – 1, j – 1). Предположим, что для всех этих трёх клеток уже найден маршрут, имеющий минимальный вес, а числовые значения весов хранятся в W[i – 1][j], W[i][j – 1], W[i – 1][j – 1]. Для определения самого маленького веса для клетки (i, j), нужно подобрать самый маленький вес из набора W[i– 1][j], W[i][j – 1], W[i – 1][j – 1] и добавить к нему число, которое записано в текущей клетке:
W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j].
Сложность данной задачи заключается в том, что помимо самого маленького веса, требуется проложить ещё и сам маршрут. По этой причине нужно сформировать ещё один массив, где для каждой клетки запоминается направление, то есть с какой стороны в неё нужно прийти. В каждую из оставленных позади клеток будет вести только одна стрелка. Она покажет с какого направления требуется попасть в данную клетку, чтобы обеспечить самый маленький вес, указанный в клетке. Когда будет завершён проход всего массива, требуется ещё отследить сам маршрут из финальной клетки, идя по стрелкам в обратном направлении, а затем зафиксировать его и записать как итоговый результат.
