Если у меня есть матрица, каждый элемент матрицы является неотрицательным числом. Я хочу пройти через матрицу из левого нижнего угла в правый верхний угол. На каждом шаге я могу двигаться только вверх или вправо, и каждый посетивший элемент будет установлен в 0; после этого я возвращаюсь из правого верхнего угла в левый нижний угол, каждый шаг я могу двигаться только вниз или влево.
Мой вопрос - как эффективно найти путь с максимальной суммой.
Пусть имеется матрица с столбцами N и M и предположим, что N>=2 и M>=2, в противном случае решение тривиально. У меня есть алгоритм, работающий в O(max(M,N) * min(N,M)^4) с использованием динамического программирования.
Сначала докажем, что оптимальное решение, где пути не пересекаются (кроме начала и конца), всегда существует. Мы будем принимать любое решение и преобразовывать его в непересекающийся, не снижая оптимизационную функцию.
Доказательство:
Начните с проверки того, что второй путь (сверху вниз справа налево) всегда выше или в той же строке, что и первый путь. Сделайте это, взяв одну секцию обоих путей, где это не так, и замените их. Иллюстрация:
Затем удалите одно столкновение за раз. Вы всегда можете найти столкновение таким образом, чтобы по крайней мере один маршрут поворачивался туда, и вы можете изменить этот путь, чтобы избежать столкновения. Повторяйте это до удаления всех столкновений. Иллюстрация одного шага:
Мы видим, что не только элементы, которые мы удалили из обоих путей, а добавили больше элементов, и все элементы неотрицательны, поэтому сумма может увеличиться.
Алгоритм:
Мы рассмотрим только пути, которые не пересекаются, также я предполагаю, что N<=M (ширина матрицы не меньше высоты). Часто мы добавим номер из одного столбца, который можно сделать быстро, используя Префиксная сумма.
Мы начнем с первого столбца. Для каждой пары (i, j) такой, что 1<=i<j<=N мы вычислим оценку этой пары, то есть сумму того, насколько оба пути покрывают, начиная с (1,1) и заканчивая на (1, i) и ( 1, j) соответственно. Пример:
Matrix:
1 2 3
4 5 6
7 8 9
score(1,1) = 7
score(1,3) = 12
score(2,3) = -inf (paths cannot cross)
Затем мы вычислим оценку каждой пары в следующем столбце из пар пар в текущем столбце. Для каждой пары в следующем столбце просто посмотрите на все пары в предыдущем столбце, путь которого может быть расширен, чтобы соответствовать пути текущего столбца.
Наконец, ваш ответ - оценка пары (N-1, N) в последнем столбце. Я прошу прощения за то, что я ужасно объясняю алгоритмы над письменными СМИ, надеюсь, что это не совсем неуловимо.