如何加速/修复这个最短路径网格遍历? [英] How can I speed up/fix this shortest path grid traversal?
问题描述
我正在编写一个程序，从左下角到右上角遍历一个网格，其中有效的移动是向右移动 1、向上移动 1 或向上或向右跳跃指定的数量跳阵.输入是二维数组格式的网格、网格的维度:X 和 Y，以及必须按顺序完成跳转的跳转数组.输出是最短路径，其中路径的长度是触摸的所有数字的总和，包括左下角和右上角.
示例输入:
I'm working on writing a program to traverse a grid from the bottom left to the top right where valid moves are moving to the right by 1, moving up by 1, or jumping up or right by an amount designated in the jump array. The inputs are the grid in a 2D array format, dimensions of the grid: X and Y, and an array of jumps where the jumps have to be completed in order. The output is the shortest path where the length of the path is the sum of all numbers touched including bottom left and top right.
Example input:
Grid:
[9 9 1]
[9 9 1]
[3 9 1]
Jumps: [1 1] X:3, Y:3
此输出将是 5，因为我们从 (0,0) 开始，即 3，然后使用第一个 1 块跳转到 (2, 0)，即 1，然后第二个块跳转到 (2,2) 这是 1 所以 3+1+1 = 5. 如果 jumps 数组只有 [1] 那么输出将是 6 因为我们必须从 (2,0) 移动到 (2,1) 到 (2),2).
The output for this would be 5 because we start at (0,0) which is 3 and then use the first 1 block jump to (2, 0) which is 1 and then the second one block jump to (2, 2) which is 1 so 3+1+1 = 5. If the jumps array was only [1] then the output would be 6 since we would have to move from (2,0) to (2,1) to (2,2).
这是我的第一个解决方案，它似乎适用于较小的输入，但在较大的输入上永远运行:
This is my first solution, which seems to work for smaller inputs but just runs forever on larger inputs:
def get(grid, x, y, endX, endY):
if (x > endX or y > endY):
return False
return grid[y][x]
def fly(x, y, grid, jumps, endX, endY):
if x > endX or y > endY:
return float('inf')
if (x == endX and y == endY):
return get(grid, endX, endY, endX, endY)
flyup = fly(x, y+1, grid, jumps, endX, endY)
flyright = fly(x+1, y, grid, jumps, endX, endY)
if (len(jumps) > 0):
jumpup = fly(x, y+jumps[0]+1, grid, jumps[1:], endX, endY)
jumpright = fly(x+jumps[0]+1, y, grid, jumps[1:], endX, endY)
temp = min(flyup, flyright, jumpup, jumpright)
return get(grid, x, y, endX, endY) + temp
else:
temp = min(flyup, flyright)
return get(grid, x, y, endX, endY) + temp
fly(0, 0, grid, jumps, X-1, Y-1)
这是我使用 DP 编写的另一个解决方案(或者我对 DP 的任何理解，因为我刚刚学会了它)，但这个解决方案似乎只适用于某些输入，我无法识别模式.
This is another solution I wrote using DP (or whatever my understanding of DP is since I just learned it) but this one seems to only work on certain inputs and I can't identify a pattern.
def fly2(x, y, grid, jumps):
dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
for row in range(len(grid)):
for col in range(len(grid[0])):
if row == 0 and col == 0:
dp[row][col] += get2(grid, col, row)
else:
flyup = float('inf') if row==0 else dp[row-1][col]
flyright = float('inf') if col==0 else dp[row][col-1]
jumpup = float('inf') if row < jumps[0]+1 else dp[row-jumps[0]-1][col]
jumpright = float('inf') if col < jumps[0]+1 else dp[row][col-jumps[0]-1]
shortest = min(flyup, flyright, jumpup, jumpright)
if min == jumpup or min == jumpright:
jumps = jumps[1:]
dp[row][col] += get2(grid, col, row) + shortest
return dp[len(grid)-1][len(grid[0])-1]
我需要一些帮助来加速第一个或找出第二个有什么问题，或者获得一些关于如何有效地编写它的其他想法.谢谢
I need some help speeding up the first one or figuring out what's wrong with the second one or maybe get some other ideas on how I can write this efficiently. Thanks
推荐答案
在我看来，dp 应该有另一个维度用于当前跳转索引.一般来说，
It seems to me that the dp should have another dimension for the current jump index. Generally,
dp[y][x][j] = Grid[y][x] + min(
dp[y + 1][x][j],
dp[y][x - 1][j],
dp[y + jump[j-1] + 1][x][j-1],
dp[y][x - jump[j-1] - 1][j-1]
)
其中 j 是跳转数组中的当前索引.
where j is the current index in the jump array.
(我认为问题描述在示例中使用了 (x, y) 坐标表示法.我使用了 [y][x] 作为 [row][column]，用于编程二维数组访问.)
(I think the question description uses (x, y) coordinate notation in the example. I used [y][x] as [row][column], common for programming two dimension array access.)
这篇关于如何加速/修复这个最短路径网格遍历?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
