Оптимальный путь через матрицу с учетом множества затрат

Question

Например, приведенная ниже матрица:

[[[0, 8], [0, 3], [0, 8]],
 [[8, 0], [3, 0], [0, 5]],
 [[0, 1], [0, 6], [0, 0]]]

где для каждого кортежа первое число - это еда, а второе число - вода. Мне нужно попасть из нижнего правого угла в верхний левый, и я могу двигаться только вверх или влево.

Мне нужно собрать как можно больше еды и воды, чтобы выжить как можно дольше. На каждый день, когда я хочу выжить, мне нужна 1 еда и 1 вода, поэтому, если бы я мог выбирать между путем, который привел бы к (7,4), и тем, который привел бы к (6,6), правильный выбор был бы (6,6 ), поскольку это позволит мне прожить 6 дней.

Как можно go найти лучший путь через указанную матрицу?

Мой текущий код ниже, но он не работает ( он находит путь очень высокой стоимости, но не самый высокий), и я не знаю, как go об этом. Я понятия не имею, как начать его реализацию, хотя мне сказали избегать рекурсии.

def maxSuppliesPath(matrix):
n = len(matrix) - 1
bestPath = matrix

# Initialize first column of bestPath array
for i in range(1, n + 1):
    if bestPath[i][0] == 0:
        bestPath[i][0] = bestPath[i - 1][0]
    else:
        bestPath[i][0] = (bestPath[i][0][0] + bestPath[i - 1][0][0], bestPath[i][0][1] + bestPath[i - 1][0][1])

# Initialize first row of bestPath array
for j in range(1, n + 1):
    if bestPath[0][j] == 0:
        bestPath[0][j] = bestPath[0][j - 1]
    else:
        bestPath[0][j] = (bestPath[0][j - 1][0] + bestPath[0][j][0], bestPath[0][j - 1][1] + bestPath[0][j][1])



# Construct rest of the bestPath array
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if min(bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1]) > min(
                bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1]):
            bestPath[i][j] = (bestPath[i][j - 1][0] + bestPath[i][j][0], bestPath[i][j - 1][1] + bestPath[i][j][1])
        else:
            bestPath[i][j] = (bestPath[i - 1][j][0] + bestPath[i][j][0], bestPath[i - 1][j][1] + bestPath[i][j][1])

return min(bestPath[n][n][0], bestPath[n][n][1])

Answer 1

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

Обратите внимание, что равноудаленные точки расположены по диагонали. Учитывая set (назовите его A ), который представляет одну диагональ, точки на следующей диагонали (назовите его B ) находятся следующим образом:

for each point in set A
    if the x coordinate is greater than zero
        add (x-1, y) to set B
    if the y coordinate is greater than zero
        add (x, y-1) to set B

В этом примере наборы, представляющие диагонали, должны выглядеть следующим образом:

[(2, 2)]                  // starting position
[(1, 2), (2, 1)]          // after 1 move
[(2, 0), (1, 1), (0, 2)]  // after 2 moves
[(0, 1), (1, 0)]          // after 3 moves
[(0, 0)]                  // after 4 moves

На изображении ниже показано, сколько разных путей можно использовать для достижения каждой точки в матрице. Количество путей совпадает с числами в треугольнике Pascal . Для целей этого вопроса единственное, что имеет значение, - это то, что числа быстро растут, поэтому нам нужно уменьшить количество.

Чтобы уменьшить количество путей, нам нужно отсеивать непродуктивные пути при обходе матрицы. Это достигается путем сравнения кортежей, каждый из которых состоит из еды и воды. Кортеж (F,W) доминирует над кортежем (f,w) iff F >= f AND W >= w.

Например, рассмотрим центральную позицию в матрице. Мы можем достичь этой точки либо перемещаясь вверх, затем влево, либо перемещаясь влево, затем вверх. Переход вверх, затем влево для урожайности (еда, вода) из (3,5), тогда как перемещение влево, затем вверх, для урожайности (3,6). (3,6) доминирует (3,5), поэтому нам нужно только рассмотреть (3,6). Итак, после двух ходов мы имеем ситуацию, показанную ниже. Обратите внимание, что у нас есть только 1 кортеж в центральной позиции, а не два, которые предсказал бы треугольник Pascal.

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

После четырех ходов мы имеем четыре возможных ответа, и выбор лучшего - это простой вопрос сравнения min(food, water) для каждого из кортежей.