Лучший маршрут, пересекающий лабиринт

Question

Дана двухмерная целочисленная матрица с размером (m,n), и один человек разрешает перемещаться от (0,0) до (m-1,n-1). Действительные шаги идут вправо или вниз. Меня просят найти путь максимальной суммы, чтобы добраться до места назначения. Это довольно просто, так как

MaxPathSum(i,j) = Math.max(MaxPathSum(i,j-1),MaxPathSum(i-1,j)) + Matrix[i][j] 

Однако, если есть два человека, оба позволили пройти от (0,0) до (m-1,n-1). Значение одной ячейки будет установлено равным нулю, как только эта ячейка будет посещена кем-то. Учитывая это ограничение, какова будет максимальная сумма этих двух путей?

Подсказка приветствуется. Благодарю.

Answer 1

Прежде всего обратите внимание, что каждый шаг всегда увеличивает расстояние Манхэттена от начала координат (x + y) на единицу. Это означает, что если вы перемещаете два маркера сразу по двум путям, поочередно двигая их поочередно, то, если пути пересекают счетчики, они должны быть сверху друг на друга: вы не можете иметь один маркер, достигающий квадрата, другой освобожденный несколько шагов назад ,

Теперь вы можете придумать исходный расчет MaxPathSum (i, j) = ... как динамическую программу в пространстве состояний, где состояние является позицией одного маркера. Для двух путей одна очевидная вещь - запустить динамическую программу в пространстве состояний, где состояние - это положение двух маркеров. Тогда вы могли бы иметь MaxPathSum (i, j, k, l) = ... где более сложное выражение рассматривает четыре возможных движения двух маркеров и гарантирует, что Matrix [i, j] не засчитывается дважды, если i == j & & k == l. Из-за того, что мы разработали выше, нам нужно рассмотреть только столкновения этой формы, поэтому нам не нужно запоминать пути, которые маркеры переместили на их текущие позиции.

Это выглядит как квадрат размера пространства состояний. Это плохо, но не так уж плохо, опять же из-за ограничения расстояния Манхэттена. Вы можете выполнять вычисления рекурсии в несколько этапов, каждый шаг выстраивая все ответы для состояний конкретного Манхэттенского расстояния от начала координат. Вам нужно всего лишь рассмотреть пары состояний, которые имеют одно и то же отличие Манхэттена друг от друга. Если у вас есть массив NxN, исходный расчет стоит O (N^2). Если вы хотите сделать это в тех шагах, где каждый шаг охватывает все ячейки с определенным расстоянием на Манхэттене, тогда у вас есть O (N) шагов, каждый из которых покрывает ячейки O (N). Если вы беспокоитесь о двух путях, у вас все еще есть шаги O (N), но каждый шаг охватывает пары O (N^2), поэтому общая стоимость O (N^3) - но входные данные (матрица) имеет размер O (N^2), так что вы могли бы так же думать об этом как O (N^1.5) или повышать первоначальную стоимость до мощности 1.5.

Answer 2

Если значения неотрицательны (> = 0), то существует пара максимальных путей, которые не пересекаются друг с другом. Его можно проверить по конструкции.

Предположим, что максимальные пути (А и В) пересекаются друг с другом, как:

..B. 
.B.A 
AXA. 
.B.. 

Чем мы можем поменять местами части путей просто прикасаться друг к другу, где сумма та же.

..A. 
.A.B 
AXB. 
.B.. 

Поскольку значения неотрицательны, сумма новых путей является> = что первородного A + B

..A.  ..A. 
AA.B or .A.B 
ABB.  AAB. 
.B..  .BB. 

Мне кажется, что какое-то решение DP должно существовать, но я не могу найти один :-)

Существует жадный подход, который находит неплохое решение.Он использует свойство с двумя верхними операциями. Алгоритм подобен:

find first maximal path 
set 0 to path elements 
find second maximal path 
improve paths with upper operations 

Не оптимальная часть - это нули, установленные на элементах первого пути. Эти нули вынуждают второй путь не пересекать первый. Операции улучшения используют элементы вокруг пересечения, поэтому улучшение добавит к результату соседний элемент. Его можно использовать для установки первых элементов пути для значения некоторого значения соседа. Прямо сейчас, я не уверен, какой сосед использовать, поскольку есть больше комбинаций, особенно если пересечение является более длинным перекрытием. Я думаю, что хорошей стартовой точкой является установление ее минимально возможного значения соседа.