寻路Python算法回溯
给定一个矩阵，board我想找到允许我找到更多数字的路径1's，知道我只能向上(n+1)和向右(m+1)。我正在尝试使用回溯解决方案，并且我设法知道1's在最佳路径上可以找到多少个，但是我无法弄清楚如何打印最佳路径的坐标。
board=[[0,0,0,0,1,0],
[0,1,0,1,0,0],
[0,0,0,1,0,1],
[0,0,1,0,0,1],
[1,0,0,0,1,0]]
def findPath(board,n,m):
noo=0
if board[n][m]>0:
noo+=1
if n==len(board)-1 and m==len(board[0])-1:
return noo
if n==len(board)-1:
noo+=findPath(board,n,m+1)
elif m==len(board[0])-1:
noo+=findPath(board,n+1,m)
else:
noo+=max(findPath(board,n,m+1),findPath(board,n+1,m))
return noo
print(findPath(board,0,0))
我应该如何或在哪里实现print(n,m)打印最佳路径的每个网格的坐标
已编辑
提出了这个解决方案
def path(board,x,y,xl,yl,sol,index,paths):
sol.append([x,y])
solaux=sol
if x==0 and y==0:
pass
if board[x][y]>0:
sol[0]+=1
if x==xl-1 and y==yl-1:
paths.append(sol)
print(sol)
return paths
if x==xl-1:
path(board,x,y+1,len(board),len(board[0]),sol,index,paths)
elif y==yl-1:
path(board,x+1,y,len(board),len(board[0]),sol,index,paths)
else:
index= len(sol)
auxnoo= sol[0]
path(board,x,y+1,len(board),len(board[0]),sol,index,paths)
sol = sol[0:index]
sol[0]=auxnoo
path(board,x+1,y,len(board),len(board[0]),sol,index,paths)
return paths
回答
起初，您的实现效率非常低，因为您findPath多次为单个单元格执行此操作。例如，如果您有 2x2 网格，单元格(1, 1)将被访问两次：
(1, 0) -- path 2 --> (1, 1)
^ ^
| path 2 | path 1
| |
(0, 0) -- path 1 --> (0, 1)
(1, 0) -- path 2 --> (1, 1)
^ ^
| path 2 | path 1
| |
(0, 0) -- path 1 --> (0, 1)
所以让我们记住noo每个单元格的值：
我应该如何或在哪里实现打印（n，m）来打印最佳路径的每个网格的坐标
其次，没有简单的方法可以放入print(n,m)给定的代码，因为对于给定的单元格，我们不知道它是否属于任何最佳路径。只有当我们回到单元格(0, 0)时，我们才会确定。
但是现在我们有二维数组noo：如果noo[i][j]包含 value x，那么最佳将是相对于单元格(i, j)位于下一个右侧或上单元格(i1, j1) 的方向，其中noo[i1][j1] >= x - 1(noo[i1][j1]可以等于xifboard[i][j] == 0或x - 1if board[i][j] == 1)。让我们实现最优路径打印机：
# noo[i][j] == None value means value for cell wasn't calculated before.
# Otherwise noo[i][j] it means calculated answer for cell.
noo=[[None for i in range W] for j in range H]
def findPath(board,n,m):
if noo[n][m] is not None:
return noo[n][m]
noo[n][m] = board[n][m]
if n==len(board)-1 and m==len(board[0])-1:
return noo[n][m]
if n==len(board)-1:
noo[n][m]+=findPath(board,n,m+1)
elif m==len(board[0])-1:
noo[n][m]+=findPath(board,n+1,m)
else:
noo[n][m]+=max(findPath(board,n,m+1),findPath(board,n+1,m))
return noo[n][m]
print(findPath(board,0,0))
请注意，如果noo[n+1][m]和 都noo[n][m+1]满足上述条件，则意味着存在多个最佳路径，您可以选择任何方向。