Пути в таблице и динамическое программирование
Почему для оптимального маршрута достаточно хранить лучшую сумму до каждой клетки и как учитывать недоступные переходы.
К одной клетке таблицы могут вести разные маршруты. Если каждый шаг разрешён только вправо или вниз, сравнивать все маршруты целиком не обязательно. Достаточно знать лучший результат до каждой из двух предыдущих клеток. Основание этого способа — возможность заменить начало пути, сохранив его продолжение.
Маршрут и его сумма
Маршрут — последовательность посещаемых клеток, в которой каждая следующая получается из предыдущей разрешённым шагом. Число, которое клетка добавляет к результату, называют её весом. Если оплачивается или собирается содержимое всех посещённых клеток, сумма маршрута включает и старт, и финиш.
Например, на маленьком участке путь A1 → B1 → B2 посещает клетки со значениями 22, 21 и 11. Его сумма равна 22+21+11=54. Путь A1 → A2 → B2 при значении A2, равном 28, даёт 22+28+11=61. Оба маршрута заканчиваются в B2, но результаты различаются. Эти числа взяты из фрагмента поля с оплатой каждой клетки ↗.
При движении только вправо и вниз нельзя вернуться в уже посещённую клетку: для возврата потребовался бы шаг влево или вверх. Поэтому каждое число выбранного маршрута добавляется ровно один раз. До клетки, находящейся на несколько строк ниже и несколько столбцов правее старта, число шагов определяется этими двумя смещениями.
Какой результат достаточно сохранить
Для поиска минимума в каждой клетке хранится наименьшая сумма пути от старта до неё включительно. Это состояние вычисления: значение, достаточное для последующих шагов. Для максимума определяется отдельное состояние с наибольшей суммой.
Почему остальные пути можно не хранить? Пусть два пути пришли в одну клетку с суммами 54 и 61. Любое разрешённое продолжение доступно им обоим: дальнейшие переходы зависят от клетки и стен, а не от того, как Робот сюда пришёл. Если продолжение добавляет 30, результаты будут 84 и 91. Для минимума путь с суммой 61 уже не сможет стать лучше пути с суммой 54.
Это рассуждение называют принципом оптимальности. Если бы минимальный путь содержал не самое выгодное начало до некоторой клетки, это начало можно было бы заменить и уменьшить итоговую сумму. Для максимума рассуждение такое же, только начало заменяется на большее.
Основание относится к рассматриваемым маршрутам: правила дальнейших шагов определяются текущей клеткой. Если бы условие дополнительно ограничивало, например, число уже сделанных поворотов, одной суммы в клетке было бы недостаточно. В задаче о сумме клеток без такого ограничения состояние остаётся простым.
От последнего шага к формуле
Номер строки обозначается i, номер столбца — j; оба отсчитываются от единицы. Значение исходной клетки обозначается a_{i,j}, минимальная сумма до неё — L_{i,j}, максимальная — H_{i,j}.
Клетка перед последним шагом называется предшественником. Если оба перехода открыты и до обеих предыдущих клеток есть путь от старта, последний шаг приходит из строки выше, (i-1,j), или из столбца левее, (i,j-1). Выбирается лучшая сумма до предшественника, затем добавляется вес текущей клетки. Знак \min выбирает меньшее число, \max — большее:
L_{i,j}=a_{i,j}+\min(L_{i-1,j},L_{i,j-1}).
H_{i,j}=a_{i,j}+\max(H_{i-1,j},H_{i,j-1}).
Формула выражает новый результат через уже вычисленные. Такую зависимость называют рекуррентным соотношением. Для B2 из приведённого фрагмента a_{2,2}=11, суммы сверху и слева равны 43 и 50. Поэтому L_{2,2}=11+\min(43,50)=54, а H_{2,2}=11+\max(43,50)=61.
Начальное значение и порядок вычислений
У начальной клетки нет предыдущего шага. Если старт — A1 и он учитывается в сумме, начало расчёта задаётся отдельно: L_{1,1}=H_{1,1}=a_{1,1}. Это база, от которой строятся все следующие результаты.
В первой строке можно прийти только слева, а в первом столбце — только сверху. Пока переходы открыты, результат равен сумме предшественника и веса текущей клетки. Во внутренних клетках уже возможен выбор между двумя направлениями.
Таблица заполняется по строкам сверху вниз, внутри строки — слева направо. К моменту вычисления клетки её верхний сосед уже обработан в предыдущей строке, а левый — раньше в текущей. Повторное использование готовых решений меньших задач называется динамическим программированием.
На квадратном поле со стороной N имеется N^2 клеток. Для каждой рассматриваются не более двух предшественников. Поэтому объём работы пропорционален числу клеток и обозначается O(N^2). Число возможных маршрутов может быть гораздо больше, но они не перечисляются по отдельности.
Разрешённый переход и достижимость
Стена лежит между клетками и запрещает пересечь соответствующую границу. Поэтому предшественник участвует в формуле лишь при двух условиях: до него существует путь от старта и переход от него в текущую клетку открыт.
Если сверху стена, но слева есть допустимый путь, выбор между двумя числами исчезает: к левой накопленной сумме добавляется вес клетки. Такое правило применяется в поле с внутренними стенами и заданным финишем ↗. Клетка за стеной не становится запрещённой целиком: она может оставаться доступной с другого направления.
Клетка достижима, если существует хотя бы один разрешённый маршрут от старта до неё. Если нет ни одного доступного предшественника, кроме отдельно заданного случая старта, накопленной суммы нет. Это состояние отличается от суммы, равной нулю. Подстановка нуля в минимум добавила бы вымышленный путь, которого Робот не проходил.
Таким образом, для каждой клетки сначала определяется набор доступных предшественников. При двух выбирается лучший результат; при одном используется он; при отсутствии клетка отмечается как недостижимая. Та же проверка нужна дальше: открытая граница от недостижимой клетки не создаёт пути от старта.
Как определяется окончательный ответ
Если финиш задан, ответ находится в соответствующей клетке расчётной таблицы. Но условие может разрешать завершение в любом тупике — клетке, из которой нет ни одного разрешённого шага вправо или вниз. Тупик определяется выходами из клетки, а её достижимость — возможностью прийти от старта. Эти свойства проверяются отдельно.
При нескольких допустимых финишах минимум выбирается среди минимальных сумм достижимых конечных клеток; максимум — среди их максимальных сумм. В задаче о завершении пути в тупике ↗ минимальный результат 436 относится к F8, а максимальный 2476 — к P20. Один маршрут не обязан обеспечивать оба результата: минимизация и максимизация решаются независимо.
Восстановление пути
Число в конечной клетке показывает оптимальную сумму, но для проверки полезно получить сам маршрут. При вычислении можно сохранять, из какого предшественника пришла лучшая сумма. Затем путь восстанавливается от финиша к старту, проходя выбранные связи в обратном порядке.
Если оба предшественника дают одинаковую лучшую сумму, для восстановления одного оптимального пути достаточно любого. После разворота списка клеток проверяются разрешённые шаги, стены и сумма исходных значений. Эта проверка отличает числовой результат от действительно существующего маршрута с такой суммой.
Как перенести правило накопленных сумм в электронную таблицу, сохранив края и стены? Почему при нескольких тупиках ответ может относиться к разным конечным клеткам? Полный расчёт и применение этих правил приведены в материале «Задание №18. Робот в таблице: минимальная и максимальная сумма».