OutputError：在给定约束的矩阵中查找最长路径

Question

我的矩阵是：

4 8 7 3 
2 5 9 3 
6 3 2 5 
4 4 1 6

问题（滑雪）：

每一个数字代表该山区域的海拔。在

从网格中的每个区域（即方框），您可以进入北，南，东，西——但前提是您要进入的区域的标高小于等于您所在区域的标高。在

你只能滑雪下山。在

你可以从地图上的任何地方开始，你正在寻找一个起点，这个起点是由你访问的盒子数量来衡量的，这个起点有一条最长的向下路径。在

如果有几条相同长度的路径，你要选择垂直落差最陡的那条，也就是起始高程和终点高程之间最大的差异。在

我的解决方案：

^{pr2}$

问题：

电流输出（距离、压降、路径）：

[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。在

Answer 1

主要的问题是你不做任何回溯。你不必做任何事情，只是要适当地保持矩阵的概念。相反，对于您访问的每个方块，您只需将所有合法移动附加到一个列表中。在

相反，考虑将当前路径保持为局部变量。对于给定方块中的每一个合法移动，都要进行单独的递归调用以查找更多的移动。每一个都将添加一个合法的移动到本地路径的末尾。在

每次通话结束后，请将找到的最佳路径与保存的路径（目前为止最好的路径）进行比较；保留这两条路径中最好的一条，然后转到下一个合法的移动路径。当您考虑了四个方向中的每一个之后，请返回调用实例的最著名路径。在

在网上和这个网站上有很多回溯的例子；找出一些你觉得可以理解的例子。你可能会在硬币组合递归（找到一组硬币，增加到一定数量）下看，它们不是相同的算法，但上面的回溯思想显示得更清楚。在

这能让你找到解决办法吗？在

Answer 2

我们可以用两种不同的方式来处理问题中所述的挑战：

1. 如果满足给定的要求，则使用递归算法在遍历矩阵元素时只进行有效路径检查

2. 分两步进行：

   1.2.1条。通过对itertools模块可用函数permutations()中的简单调用，获得所有可能路径上的迭代器

   2.2条。从生成的路径中选择满足要求的路径

第二种方法的代码更易于编写和理解，但是对于4x4大小的矩阵来说，已经存在大量可能的路径，因此实际上不可能在更大的矩阵大小下运行它。在

第一种方法的代码可以处理更大尺寸的矩阵，但缺点是很难掌握如何在其他约束的情况下调整矩阵。在

这里所问的问题是一个100%1:1的重复两年前提出的题为“矩阵路径中元素的最大数目”的问题。不管怎样，在回答这个老问题时给出的答案是：

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) )

上面的代码打印：

^{pr2}$

现在，我们也来看看这里提供的非递归方法的代码，我自己：

# 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,

我希望代码是不言自明的，但如果不是这里的粗略想法：

1. 构建一个表示矩阵的字典，其中的键是（列、行）“坐标”的元组和矩阵中的值的元组。

2. 建立矩阵（排列）中所有可能的完整路径的列表。

3. 筛选所有可能的完整路径的列表，以便根据需要仅提取有效路径（应用条件）。

我没有运行4x4矩阵计算结果的计算非常昂贵，因为在我的盒子上肯定要花费几分钟以上。在

为了完整起见，我想指出还有另一个问题HERE on stackoverflow，它是这个问题的变体（它对有效路径有一些其他的规则，并要求一个算法能够处理不规则矩阵）。在