CODEWITHSUNDEEP
pythonmatrixdynamic-programming
dhs4402
dhs4402

Reputation: 143

Find max cost path of N*N matrix, from [0,0] to [N-1,N-1] with perference in one direction

For example, given a cost matrix, I need to know not only the maximum sum cost to travel from [0,0] to [N-1, N-1], but also the movement I made with this optimal path. At the same time, horizonal move has higher priority than vertical move.

| 1 | 2 | 3 |

| 2 |-8 | 4 |

| 3 | 4 | 6 |

which I know could be solved through dynamic programming. However, how to record the movement needed to be made?

In this case, two path: (right, right, down, down) would give exactly same total cost as (down, down, right, right), the optimal path will only be (right, right, down, down).

To make it clear, my question is, how to find out all the movements for the optimal path?

def optimal(mat):
    dim = len(mat)
    cost = [[0]*dim for i in range(dim)]
    path = []
    if mat[0][1]>=mat[1][0]:
        path.append('r')
    else:
        path.append('d')
    cost[0][0] = mat[0][0]
    for i in range(1,dim):
        cost[i][0] = mat[i][0] + cost[i - 1][0]
    for j in range(1,dim):
        cost[0][j] = mat[0][j] + cost[0][j - 1]
    for i in range(1, dim):
        for j in range(1, dim):
            if cost[i-1][j] >=  cost[i][j-1]:
                cost[i][j] = cost[i-1][j] + mat[i][j]
            else:
                cost[i][j] = cost[i][j-1] + mat[i][j]
    print(cost[dim-1][dim-1])
    print(path)

Upvotes: 1

Views: 711

Answers (1)

fafl
fafl

Reputation: 7385

Start by creating a structure in dynamic programming fashion. Solve the bottom and right edges of the matrix first, then reuse these results to solve more and more until you know the max cost and direction for each field.

Then walk through the matrix from the top left corner to collect the total cost and best path.

def optimal(mat):
    # Calculate optimal solution, a 2D list of cost and direction
    solution = []
    for _ in range(len(mat)):
        solution.append([])
        for _ in range(len(mat[0])):
            solution[-1].append((0, None))

    # Start in the bottom right corner and go backwards
    for i in range(len(mat)-1, -1, -1):
        for j in range(len(mat[0])-1, -1, -1):
            if i == len(mat) - 1 and j == len(mat[0]) - 1:
                # Bottom right corner, can not go further
                solution[i][j] = (mat[i][j], None)
            elif i == len(mat) - 1:
                # Bottom row, can only go right
                solution[i][j] = (mat[i][j] + solution[i][j+1][0], 'right')
            elif j == len(mat[0]) - 1:
                # Right column, can only go down
                solution[i][j] = (mat[i][j] + solution[i+1][j][0], 'down')
            else:
                # Any other field
                right_cost = mat[i][j] + solution[i][j+1][0]
                down_cost = mat[i][j] + solution[i+1][j][0]
                if right_cost < down_cost:
                    # Go down
                    solution[i][j] = (down_cost, 'down')
                else:
                    # Go right
                    solution[i][j] = (right_cost, 'right')

    # Walk the path and assemble the result
    i = 0
    j = 0
    path = []
    while i < len(mat) - 1 or j < len(mat[0]) - 1:
        path.append(solution[i][j][1])
        if solution[i][j][1] == 'down':
            i += 1
        else:
            j += 1

    return solution[0][0][0], path

m = [
    [1, 2, 3],
    [2, -8, 4],
    [3, 4, 6]
]

print(*optimal(m))

This prints 16 ['right', 'right', 'down', 'down']

Upvotes: 1

Related Questions