OutputError: Find the longest path in a matrix with given constraints
OutputError: Find the longest path in a matrix with given constraints
我的矩阵是：
4 8 7 3
2 5 9 3
6 3 2 5
4 4 1 6
问题（滑雪）：
每个数字代表该山区的海拔。
从网格中的每个区域（即方框），您可以向北、南、东, west - 但前提是您要进入的区域的海拔高度比您所在区域的海拔高度 低。
即你只能滑雪下坡。
您可以从地图上的任何地方开始，并且您正在寻找具有最长可能路径的起点，根据您访问的框数来衡量。
如果有几条相同长度的下行路径，您希望选择垂直落差最陡的那条，即起点海拔与终点海拔之间的最大差异高程。
我的解决方案：
def findSkiPath():
mySolution = [0] * 3
mySolution[0] = 0 # Distance
mySolution[1] = 0 # Drop
cellIndexRow = 0
cellIndexCol = 0
myPath = []
myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
countRows = len(myMatrix)
countCols = len(myMatrix[0])
for i in range(0, countRows - 1):
for j in range(0, countCols - 1):
myValue = myMatrix[i][j]
myPath.append(myValue)
#check east
cellIndexRow = i
cellIndexCol = j + 1
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check west
cellIndexRow = i
cellIndexCol = j - 1
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check north
cellIndexRow = i - 1
cellIndexCol = j
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check south
cellIndexRow = i + 1
cellIndexCol = j
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
print (mySolution)
def checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath ):
#The base case - If we go beyond the limits of the matrix
if (cellIndexRow < 0 or cellIndexRow > (len(myMatrix) - 1) or cellIndexCol < 0 or cellIndexCol > (len(myMatrix[0]) - 1)):
evaluateSolution(mySolution , myPath )
return
#check if the next cell has a lower value than the current cell
tmpValue = myMatrix[cellIndexRow][cellIndexCol]
if tmpValue < myValue:
newPath = myPath
newPath.append(tmpValue)
r = cellIndexRow
c = cellIndexCol
#check east
cellIndexRow = r
cellIndexCol = c + 1
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check west
cellIndexRow = r
cellIndexCol = c - 1
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check north
cellIndexRow = r - 1
cellIndexCol = c
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check south
cellIndexRow = r + 1
cellIndexCol = c
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
evaluateSolution(mySolution , myPath )
def evaluateSolution(mySolution , myPath ):
myDistance = 1
mySolutionDistance = int(mySolution[0])
mySolutionDrop = int(mySolution[1])
if myDistance < mySolutionDistance:
return
myDrop = myPath[0] - myPath[-1]
if myDistance > mySolutionDistance or myDrop > mySolutionDrop:
mySolution[0] = myDistance
mySolution[1] = mySolutionDrop
mySolution[2] = myPath
if __name__ == "__main__":
findSkiPath()
问题：
当前输出（距离、落差、路径）：
[1, 0, [4, 2, 8, 7, 3, 4, 2, 5, 2, 3, 2, 1, 7, 3, 2, 5, 2, 3, 2, 1, 9,
3, 5, 2, 3, 2, 1, 7, 3, 2, 1, 6, 3, 2, 1, 2, 4, 3, 2, 1, 2, 1]]
预期输出：
[5,8,[9,5,3,2,1]]
在这个特定的地图上，最长的下行路径长度为 5，下降为 8 (9-1=8)，路径为：9-5-3-2-1。
这样做的主要问题是您没有进行任何类型的回溯。您正在适当地遍历矩阵，但您没有做任何事情来维护特定路径的概念。相反，对于您访问的每个方块，您只需将所有合法移动附加到一个列表中。
相反，请考虑将当前路径保留为局部变量。对于给定方块的每个合法移动，您进行单独的递归调用以查找更多移动。每一个都会在 local 路径的末尾添加一个合法的移动。
每次调用 return 时，将找到的最佳路径与您保存的路径（迄今为止最好的）进行比较；保留这两者中较好的一个，然后进行下一个合法步骤。当您考虑了四个方向中的每一个时，return 调用实例的最知名路径。
在线和本网站上有很多回溯的例子；找出一些你觉得可以理解的。你可能会看硬币组合递归（找到一组增加到一定数量的硬币） - 它们不是相同的算法，但上面的回溯思路更清楚。
这是否促使您找到解决方案？
可以通过两种不同的方式解决问题中描述的挑战：
使用递归算法，如果满足给定要求，该算法仅遍历有效路径并在遍历矩阵元素时进行检查
分两步进行：
2.1。通过简单调用 itertools 模块可用函数 permutations()
获取所有可能路径的迭代器
2.2。从生成的路径中选择满足要求的路径
第二种方法的代码更容易编写和理解，但是对于 4x4 大小的矩阵来说已经存在大量可能的路径，这使得它实际上不可能 运行 它用于更大的矩阵大小。
第一种方法的代码可以处理更大尺寸的矩阵，但缺点是更难掌握在其他约束的情况下如何调整它。
此处提出的问题 100% 1:1 重复 两年前提出的问题 here on Whosebug，标题为 "Maximum number of elements in the path of a matrix"。无论如何，这里再次给出了对那个老问题的回答的解决方案：
theMatrix = [
[ 4, 8, 7, 3],
[ 2, 5, 9, 3],
[ 6, 3, 2, 5],
[ 4, 4, 1, 6]
]
def longest_path(matrix):
def inner_longest_path(x, y):
best, best_path = 0, []
# for all possible neighbor cells...
for dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)):
# if cell is valid and strictly smaller...
if (0 <= x + dx < len(matrix) and 0 <= y + dy < len(matrix[x])
and matrix[x+dx][y+dy] < matrix[x][y]):
n, path = inner_longest_path(x+dx, y+dy) ### RECURSION
# check if the path starting at that cell is better
if n > best:
best, best_path = n, path
return best + 1, [matrix[x][y]] + best_path
return max(inner_longest_path(x, y) for x, row in enumerate(matrix)
for y, _ in enumerate(row))
print( longest_path(theMatrix) )
上面的代码打印：
(5, [9, 5, 3, 2, 1])
现在让我们也看一下 non-recursive 方法的代码，我自己在这里提供：
# myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
# 4 5 8 7
# 1 1 5 9
# 0 7 5 5
# 7 4 2 9
myMatrix = [[4, 5, 8],[1, 1, 5], [0, 7, 5]]
# 4 5 8
# 1 1 5
# 0 7 5
# myMatrix = [[4, 5],[1, 1]]
# 4 5
# 1 1
def getAllValidSkiingPathsFrom(myMatrix):
# def getDictRepresentationOf(myMatrix):
dctOfMatrix = {}
for row in range(len(myMatrix)):
for column in range(len(myMatrix[0])):
currPoint = (column, row)
dctOfMatrix[currPoint] = myMatrix[row][column]
lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
setAllPossiblePaths = set()
from itertools import permutations
for pathCandidate in permutations(lstIndicesOfAllMatrixPoints):
lstPossiblePath = []
prevIndexTuple = pathCandidate[0]
lstPossiblePath.append(prevIndexTuple)
for currIndexTuple in pathCandidate[1:]:
if abs(currIndexTuple[0]-prevIndexTuple[0]) + abs(currIndexTuple[1]-prevIndexTuple[1]) > 1:
break # current path indices not allowed in path (no diagonals or jumps)
else:
if dctOfMatrix[currIndexTuple] >= dctOfMatrix[prevIndexTuple]:
break # only "down" is allowed for "skiing"
else:
lstPossiblePath.append(currIndexTuple)
prevIndexTuple = currIndexTuple
if len(lstPossiblePath) > 1 and tuple(lstPossiblePath) not in setAllPossiblePaths:
setAllPossiblePaths.add(tuple(lstPossiblePath))
return setAllPossiblePaths, dctOfMatrix
#:def getAllValidSkiingPathsFrom
setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)
for path in setAllPossiblePaths:
for point in path:
print(dctOfMatrix[point], end=',')
这里是 myMatrix 的 2x2 和 3x3 版本的结果：
# 4 5
# 1 1
4,1,
5,1,
5,4,
5,4,1,
# 4 5 8
# 1 1 5
# 0 7 5
5,1,
8,5,1,
7,1,
4,1,
5,1,
5,4,
8,5,1,
1,0,
5,4,1,0,
8,5,4,1,
8,5,4,1,0,
8,5,4,
8,5,
7,0,
7,5,
8,5,
4,1,0,
5,4,1,
我希望代码是self-explanatory，但如果不是这里粗略的想法：
构建一个表示矩阵的字典，其中键是（列，行）"coordinates" 的元组，值是矩阵中的值。
构建矩阵内所有可能完整路径的列表（排列）
过滤所有可能的完整路径列表，根据需要（应用标准）仅提取有效路径。
我没有 运行 计算非常昂贵的 4x4 矩阵结果计算，因为它在我的盒子上肯定需要几分钟以上的时间。
为了完整起见，我想提一下还有另一个问题 HERE on Whosebug，它是这个问题的变体（它对有效路径有一些其他规则，并要求能够工作的算法在不规则矩阵上）。
我的矩阵是：
4 8 7 3
2 5 9 3
6 3 2 5
4 4 1 6
问题（滑雪）：
每个数字代表该山区的海拔。
从网格中的每个区域（即方框），您可以向北、南、东, west - 但前提是您要进入的区域的海拔高度比您所在区域的海拔高度 低。
即你只能滑雪下坡。
您可以从地图上的任何地方开始，并且您正在寻找具有最长可能路径的起点，根据您访问的框数来衡量。
如果有几条相同长度的下行路径，您希望选择垂直落差最陡的那条，即起点海拔与终点海拔之间的最大差异高程。
我的解决方案：
def findSkiPath():
mySolution = [0] * 3
mySolution[0] = 0 # Distance
mySolution[1] = 0 # Drop
cellIndexRow = 0
cellIndexCol = 0
myPath = []
myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
countRows = len(myMatrix)
countCols = len(myMatrix[0])
for i in range(0, countRows - 1):
for j in range(0, countCols - 1):
myValue = myMatrix[i][j]
myPath.append(myValue)
#check east
cellIndexRow = i
cellIndexCol = j + 1
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check west
cellIndexRow = i
cellIndexCol = j - 1
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check north
cellIndexRow = i - 1
cellIndexCol = j
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
#check south
cellIndexRow = i + 1
cellIndexCol = j
checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
print (mySolution)
def checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath ):
#The base case - If we go beyond the limits of the matrix
if (cellIndexRow < 0 or cellIndexRow > (len(myMatrix) - 1) or cellIndexCol < 0 or cellIndexCol > (len(myMatrix[0]) - 1)):
evaluateSolution(mySolution , myPath )
return
#check if the next cell has a lower value than the current cell
tmpValue = myMatrix[cellIndexRow][cellIndexCol]
if tmpValue < myValue:
newPath = myPath
newPath.append(tmpValue)
r = cellIndexRow
c = cellIndexCol
#check east
cellIndexRow = r
cellIndexCol = c + 1
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check west
cellIndexRow = r
cellIndexCol = c - 1
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check north
cellIndexRow = r - 1
cellIndexCol = c
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
#check south
cellIndexRow = r + 1
cellIndexCol = c
checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )
evaluateSolution(mySolution , myPath )
def evaluateSolution(mySolution , myPath ):
myDistance = 1
mySolutionDistance = int(mySolution[0])
mySolutionDrop = int(mySolution[1])
if myDistance < mySolutionDistance:
return
myDrop = myPath[0] - myPath[-1]
if myDistance > mySolutionDistance or myDrop > mySolutionDrop:
mySolution[0] = myDistance
mySolution[1] = mySolutionDrop
mySolution[2] = myPath
if __name__ == "__main__":
findSkiPath()
问题：
当前输出（距离、落差、路径）：
[1, 0, [4, 2, 8, 7, 3, 4, 2, 5, 2, 3, 2, 1, 7, 3, 2, 5, 2, 3, 2, 1, 9, 3, 5, 2, 3, 2, 1, 7, 3, 2, 1, 6, 3, 2, 1, 2, 4, 3, 2, 1, 2, 1]]
预期输出：
[5,8,[9,5,3,2,1]]
在这个特定的地图上，最长的下行路径长度为 5，下降为 8 (9-1=8)，路径为：9-5-3-2-1。
这样做的主要问题是您没有进行任何类型的回溯。您正在适当地遍历矩阵，但您没有做任何事情来维护特定路径的概念。相反，对于您访问的每个方块，您只需将所有合法移动附加到一个列表中。
相反，请考虑将当前路径保留为局部变量。对于给定方块的每个合法移动，您进行单独的递归调用以查找更多移动。每一个都会在 local 路径的末尾添加一个合法的移动。
每次调用 return 时，将找到的最佳路径与您保存的路径（迄今为止最好的）进行比较；保留这两者中较好的一个，然后进行下一个合法步骤。当您考虑了四个方向中的每一个时，return 调用实例的最知名路径。
在线和本网站上有很多回溯的例子；找出一些你觉得可以理解的。你可能会看硬币组合递归（找到一组增加到一定数量的硬币） - 它们不是相同的算法，但上面的回溯思路更清楚。
这是否促使您找到解决方案？
可以通过两种不同的方式解决问题中描述的挑战：
使用递归算法，如果满足给定要求，该算法仅遍历有效路径并在遍历矩阵元素时进行检查
分两步进行：
2.1。通过简单调用
获取所有可能路径的迭代器itertools模块可用函数permutations()2.2。从生成的路径中选择满足要求的路径
第二种方法的代码更容易编写和理解，但是对于 4x4 大小的矩阵来说已经存在大量可能的路径，这使得它实际上不可能 运行 它用于更大的矩阵大小。
第一种方法的代码可以处理更大尺寸的矩阵，但缺点是更难掌握在其他约束的情况下如何调整它。
此处提出的问题 100% 1:1 重复 两年前提出的问题 here on Whosebug，标题为 "Maximum number of elements in the path of a matrix"。无论如何，这里再次给出了对那个老问题的回答的解决方案：
theMatrix = [
[ 4, 8, 7, 3],
[ 2, 5, 9, 3],
[ 6, 3, 2, 5],
[ 4, 4, 1, 6]
]
def longest_path(matrix):
def inner_longest_path(x, y):
best, best_path = 0, []
# for all possible neighbor cells...
for dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)):
# if cell is valid and strictly smaller...
if (0 <= x + dx < len(matrix) and 0 <= y + dy < len(matrix[x])
and matrix[x+dx][y+dy] < matrix[x][y]):
n, path = inner_longest_path(x+dx, y+dy) ### RECURSION
# check if the path starting at that cell is better
if n > best:
best, best_path = n, path
return best + 1, [matrix[x][y]] + best_path
return max(inner_longest_path(x, y) for x, row in enumerate(matrix)
for y, _ in enumerate(row))
print( longest_path(theMatrix) )
上面的代码打印：
(5, [9, 5, 3, 2, 1])
现在让我们也看一下 non-recursive 方法的代码，我自己在这里提供：
# myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
# 4 5 8 7
# 1 1 5 9
# 0 7 5 5
# 7 4 2 9
myMatrix = [[4, 5, 8],[1, 1, 5], [0, 7, 5]]
# 4 5 8
# 1 1 5
# 0 7 5
# myMatrix = [[4, 5],[1, 1]]
# 4 5
# 1 1
def getAllValidSkiingPathsFrom(myMatrix):
# def getDictRepresentationOf(myMatrix):
dctOfMatrix = {}
for row in range(len(myMatrix)):
for column in range(len(myMatrix[0])):
currPoint = (column, row)
dctOfMatrix[currPoint] = myMatrix[row][column]
lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
setAllPossiblePaths = set()
from itertools import permutations
for pathCandidate in permutations(lstIndicesOfAllMatrixPoints):
lstPossiblePath = []
prevIndexTuple = pathCandidate[0]
lstPossiblePath.append(prevIndexTuple)
for currIndexTuple in pathCandidate[1:]:
if abs(currIndexTuple[0]-prevIndexTuple[0]) + abs(currIndexTuple[1]-prevIndexTuple[1]) > 1:
break # current path indices not allowed in path (no diagonals or jumps)
else:
if dctOfMatrix[currIndexTuple] >= dctOfMatrix[prevIndexTuple]:
break # only "down" is allowed for "skiing"
else:
lstPossiblePath.append(currIndexTuple)
prevIndexTuple = currIndexTuple
if len(lstPossiblePath) > 1 and tuple(lstPossiblePath) not in setAllPossiblePaths:
setAllPossiblePaths.add(tuple(lstPossiblePath))
return setAllPossiblePaths, dctOfMatrix
#:def getAllValidSkiingPathsFrom
setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)
for path in setAllPossiblePaths:
for point in path:
print(dctOfMatrix[point], end=',')
这里是 myMatrix 的 2x2 和 3x3 版本的结果：
# 4 5
# 1 1
4,1,
5,1,
5,4,
5,4,1,
# 4 5 8
# 1 1 5
# 0 7 5
5,1,
8,5,1,
7,1,
4,1,
5,1,
5,4,
8,5,1,
1,0,
5,4,1,0,
8,5,4,1,
8,5,4,1,0,
8,5,4,
8,5,
7,0,
7,5,
8,5,
4,1,0,
5,4,1,
我希望代码是self-explanatory，但如果不是这里粗略的想法：
构建一个表示矩阵的字典，其中键是（列，行）"coordinates" 的元组，值是矩阵中的值。
构建矩阵内所有可能完整路径的列表（排列）
过滤所有可能的完整路径列表，根据需要（应用标准）仅提取有效路径。
我没有 运行 计算非常昂贵的 4x4 矩阵结果计算，因为它在我的盒子上肯定需要几分钟以上的时间。
为了完整起见，我想提一下还有另一个问题 HERE on Whosebug，它是这个问题的变体（它对有效路径有一些其他规则，并要求能够工作的算法在不规则矩阵上）。