求具有降序项的矩阵中最长的直线路径

Question

问题(滑雪)：每个数字代表该地区的海拔。从栅格中的每个区域(即方框)，你可以向北、南、东、西--但只有当你要进入的区域的海拔小于你所处的海拔(即你只能滑雪下坡)。您可以从地图上的任何地方开始，并且您正在寻找一个起点，根据您访问的框数来衡量，该起点有尽可能长的下行路径。如果有几条相同长度的路径，你想要选择最陡的垂直下降的路径，也就是你的起始高度和结束高度之间的最大差异。目标：

• 找到遵循这些规则的最长路径。最长路径是指我们总是下降的节点的最大数目。
  • 如果我们有多条相同距离(节点数)的最长路径，那么我们应该得到一个有最大降的路径(最后一个节点的第一个节点的值)。

其目的是为1000×1000矩阵运行此代码。现在，只要跑4x4，就需要几分钟。对如何降低时间和空间的复杂性有什么想法吗？

myMatrix = [[4, 5, 2],[1, 1, 6],[8, 7, 5]]
def getAllValidSkiingPathsFrom(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

setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)

printedPath = []
bestPath = []
for path in setAllPossiblePaths:
    for point in path:
        printedPath.append(dctOfMatrix[point])
    if len(printedPath) > len(bestPath): # Looking for the path with a maximum distance
        bestPath = printedPath
    if len(printedPath) == len(bestPath): # If we have more than one path with a maximum distance we look for the drop
        if (printedPath[0]-printedPath[-1]) > (bestPath[0]-bestPath[-1]):
            bestPath = printedPath
    printedPath = []

print("Path -->", bestPath)
print("Distance -->", len(bestPath))
print("Drop -->", bestPath[0]-bestPath[-1])

样本输入矩阵：

4 5 2
1 1 6
8 7 5

输出：

Path --> [8, 7, 1]
Distance --> 3
Drop --> 7

Explanation:

最长的路径是8-7-1，因为它的最大距离= 3.

还有其他路径的最大距离是8-7-5和5-4-1.然而，8-7-1的最大下降率为7 (8-1).

Answer 1

正如我在评论中所说，获得局部极小值并检查从这些点开始的路径可能更快。然后，您可以获得具有最大长度的路径，并在需要下行路径的情况下反转这些点。

我还没有对这个做过很多测试，但是在我的电脑上用4x4矩阵只需要不到一秒钟。

下面是代码(同样，我只用几个输入测试过这个代码，并有一些代码重复，请将其作为一般指导原则)：

def get_next_ascending_value(row, column, matrix, size):
    current_value = matrix[row][column]
    max_steepness = -1
    coords = []
    if (column > 0) and (matrix[row][column-1] > current_value):
        if max_steepness < matrix[row][column-1]:
            max_steepness = matrix[row][column-1]
            coords = [row, column-1]
    if (row > 0) and (matrix[row-1][column] > current_value):
        if max_steepness < matrix[row-1][column]:
            max_steepness = matrix[row-1][column]
            coords = [row-1, column]
    if (column < size - 1) and (matrix[row][column+1] > current_value):
        if max_steepness < matrix[row][column+1]:
            max_steepness = matrix[row][column+1]
            coords = [row, column+1]
    if (row < size - 1) and (matrix[row+1][column] > current_value):
        if max_steepness < matrix[row+1][column]:
            max_steepness = matrix[row+1][column]
            coords = [row+1, column]

    return coords


def is_local_minimum(row, column, matrix, size):
    current_value = matrix[row][column]
    if (column > 0) and (matrix[row][column-1] < current_value):
        return False
    if (row > 0) and (matrix[row-1][column] < current_value):
        return False
    if (column < size - 1) and (matrix[row][column+1] < current_value):
        return False
    if (row < size - 1) and (matrix[row+1][column] < current_value):
        return False

    return True

def get_local_minimum(matrix, size):
    for row in range(len(matrix)):
        for column in range(size):
            if is_local_minimum(row, column, matrix, size):
                yield [row, column]

# [4, 5, 6]
# [1, 1, 6]
# [4, 5, 6]

# starting_matrix = [[4, 5, 6],[1, 1, 6],[4, 5, 6]]
# size = 3

# [4, 5]
# [1, 1]

# starting_matrix = [[4, 5],[1, 1]]
# size = 2


# [4, 5, 7, 9]
# [1, 1, 2, 5]
# [4, 5, 7, 9]
# [1, 1, 2, 5]

starting_matrix = [[4, 5, 7, 9],[1, 1, 2, 5],[4, 5, 7, 9],[1, 1, 2, 5]]
size = 4

for coords in get_local_minimum(starting_matrix, size):
    print(coords, starting_matrix[coords[0]][coords[1]])
    next_coords = get_next_ascending_value(coords[0], coords[1], starting_matrix, size)
    while (len(next_coords) > 0):
        print(next_coords, starting_matrix[next_coords[0]][next_coords[1]])
        next_coords = get_next_ascending_value(next_coords[0], next_coords[1], starting_matrix, size)
    print('---')

Answer 2

如果您不介意使用外部模块，我认为您可以通过将您的景观看作有向图来简化问题。如果我没有遗漏一些东西，你可以把它看作是解决最长路径问题。然而，正如你所说的，如果有选择的话，必须走最陡峭的道路，这包括在手之前去除不需要的边缘。

np.random.seed(1)
a = np.random.randint(0, 100, 100)
a = a.reshape((10, 10))


def find_path(a):

    # Use a 2d grid graph for convenience to set up the edges
    diG = nx.DiGraph()
    for (n0, n1, data) in nx.grid_2d_graph(*a.shape).edges(data=True):
        v0 = a[n0]
        v1 = a[n1]

        # Add a differential to each edge to calculate the drop
        if v0 > v1:
            diG.add_edge(n0, n1, diff=v0-v1)
            diG.add_node(n0, {"val": v0})
            diG.add_node(n1, {"val": v1})
        elif v1 > v0:
            diG.add_edge(n1, n0, diff=v1-v0)
            diG.add_node(n0, {"val": v0})
            diG.add_node(n1, {"val": v1})

    # Need to remove paths which are not possible, i.e. if there is a steeper slop, this must be chosen

    nodes = sorted(diG.nodes(data=True), key=lambda x: x[1]["val"], reverse=True)
    edges = {(n0, n1): data["diff"] for (n0, n1, data) in diG.edges(data=True)}

    for n, data in nodes:
        neigh = [(n, i) for i in nx.neighbors(diG, n)]
        slopes = [edges[e] for e in neigh]
        [diG.remove_edge(*e) for e, s in zip(neigh, slopes) if s != max(slopes)]

    # Longest drop is the longest path problem
    path = nx.dag_longest_path(diG)

    # Find the drop using a list of allowed edges
    edge_names = set(zip(path, path[1:]))
    drop = sum(edges[e] for e in edge_names)

    return path, drop


t0 = time.time()
path, drop = find_path(a)

print time.time() - t0
print len(path)
print drop

>>> 0.00356292724609
[(5, 6), (5, 7), (4, 7), (3, 7)]
4
76

所走的路径在这里用一个点表示：

[[37 12 72  9 75  5 79 64 16  1]
 [76 71  6 25 50 20 18 84 11 28]
 [29 14 50 68 87 87 94 96 86 13]
 [ 9  7 63 61 22 57  1  0. 60 81]
 [ 8 88 13 47 72 30 71  3. 70 21]
 [49 57  3 68 24 43 76. 26. 52 80]
 [41 82 15 64 68 25 98 87  7 26]
 [25 22  9 67 23 27 37 57 83 38]
 [ 8 32 34 10 23 15 87 25 71 92]
 [74 62 46 32 88 23 55 65 77  3]]

在我的机器上运行这个1000x1000数组需要80秒。