Longest Increasing Path in a Matrix

SchwerDynamische Programmierung Graphen Topologische Sortierung

+10

Du erhältst matrix, ein Raster aus ganzen Zahlen mit m Zeilen und n Spalten, als Liste von Zeilen. Ein Pfad verläuft von Zelle zu Zelle, jeweils einen Schritt nach oben, unten, links oder rechts (keine diagonalen Schritte, kein Überschreiten der Ränder), und jeder Schritt muss auf einem strikt größeren Wert landen. Gib die Anzahl der Zellen auf dem längsten solchen Pfad zurück. Eine einzelne Zelle für sich ist ein Pfad aus 1 Zelle.

Funktion

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: das Raster aus Werten als Liste gleich langer Zeilen
Gibt zurückinteger: die Anzahl der Zellen auf dem längsten streng monoton steigenden Pfad

Einschränkungen

1 ≤ m, n ≤ 100, wobei m = matrix.length und n = matrix[i].length
Jede Zeile hat dieselbe Länge n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Beispiele

Eingabe: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Ausgabe: 7
Erklärung: Der Pfad 3, 4, 5, 6, 7, 8, 9 verläuft die rechte Spalte hinunter, entlang der unteren Zeile nach links, die mittlere Spalte hinauf und nach links zur 9 in der Ecke: 7 Zellen. Der kleinste Wert schneidet schlechter ab: Von der 1 aus sind die besten Pfade 1, 2, 7, 8, 9 und 1, 6, 7, 8, 9, jeweils mit 5 Zellen.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch die Zellen eines längsten Pfads zurückgeben, nicht nur seine Länge?

Lösung

Ziehe von jeder Zelle einen Pfeil zu jedem Nachbarn mit einem größeren Wert. Entlang jedes Pfeils steigen die Werte, daher kann keine Pfeilkette zu ihrem Ausgangspunkt zurückführen: Das Gitter ist ein gerichteter azyklischer Graph, und gesucht ist sein längster Pfad. In einem allgemeinen Graphen ist diese Frage für große Eingaben aussichtslos, aber ohne Zyklen hängt der längste Pfad von einer Zelle nur von dieser Zelle ab. Daher berechnest du ihn einmal pro Zelle, und das gesamte Problem reduziert sich auf O(m × n). Eine memoisierten Tiefensuche berechnet ihn von oben nach unten; wenn du das Gitter von seinen Spitzen aus schichtweise abträgst, berechnet der umgekehrt angewandte Algorithmus von Kahn ihn von unten nach oben.

Folge jedem aufsteigenden Pfad

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Beginne an jeder Zelle einen Pfad. Probiere von der Zelle, auf der du dich befindest, jeden der vier Nachbarn aus, deren Wert größer ist, und gehe von dort auf dieselbe Weise weiter, bis es keinen größeren Nachbarn mehr gibt. Zähle die Zellen jedes Pfads und merke dir die größte Anzahl.

Der Pfad benötigt keine Menge besuchter Zellen. Die Werte steigen bei jedem Schritt, daher kann der Pfad nie zu einer Zelle zurückkehren: Um wieder auf ihr zu stehen, müsste er zu ihrem Wert zurückfallen. Lege die Pfade als Einträge der Form (Zelle, Länge) auf einem Stapel ab. Wird ein Eintrag entnommen, endet ein Pfad an dieser Zelle; durch das Ablegen ihrer größeren Nachbarn wird er verlängert.

Die Methode ist korrekt und hoffnungslos langsam, weil sich die Pfade verzweigen. Auf einem Gitter mit 100 × 100 Zellen, in dem jeder Wert die Summe aus Zeilen- und Spaltenindex ist, ist jeder Schritt nach rechts oder unten ein Schritt nach oben, und allein von der Zelle oben links aus gibt es mehr als 10^58 Pfade. Schlimmer noch: Der Pfad von jeder gegebenen Zelle wird jedes Mal neu berechnet, wenn ein anderer Pfad durch sie verläuft. Genau diese Verschwendung beseitigt der nächste Ansatz.

Algorithmus

Lege für jede Zelle (diese Zelle, 1) auf einen Stapel.
Entnimm einen Eintrag (Zelle, Länge) und aktualisiere die Antwort mit der Länge.
Lege für jeden Nachbarn innerhalb des Gitters mit einem strikt größeren Wert (Nachbar, Länge + 1) auf den Stapel.
Wiederhole den Vorgang, bis der Stapel leer ist, und gehe dann zur nächsten Startzelle.
Gib die größte ermittelte Länge zurück.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Memoisierte Tiefensuche mit einem eigenen Stack

Idee

Sei best[cell] die Anzahl der Zellen auf dem längsten ansteigenden Pfad, der bei dieser Zelle beginnt. Der Pfad endet entweder direkt dort, oder sein nächster Schritt führt zu einem größeren Nachbarn und setzt sich entlang des längsten Pfads von diesem Nachbarn fort. Also gilt best[cell] = 1 + max(best[nb]) über die größeren Nachbarn nb, oder 1, wenn es keine gibt. Das kann sicher wiederverwendet werden, weil die Struktur azyklisch ist: Die Zellen vor cell auf einem beliebigen Pfad sind alle kleiner, sodass sie niemals danach auftauchen können, und die beste Fortsetzung von cell ist unabhängig davon, wie du dort angekommen bist, immer dieselbe. Berechne jedes best einmal und speichere es; so reduziert sich der exponentielle Baum der Wege auf einen Besuch pro Zelle.

Im ersten Beispiel hat 9 keinen größeren Nachbarn, also ist best dort 1. Dann erhält 8 den Wert 2, 7 den Wert 3, 6 und 2 den Wert 4, 5 und 1 den Wert 5, 4 den Wert 6 und 3 den Wert 7 – die Antwort. Jede Zelle betrachtet ihre 4 Nachbarn, daher beträgt der Aufwand O(m × n).

Der natürliche Code ist rekursiv: eine Funktion, die best für eine Zelle zurückgibt und sich für jeden größeren Nachbarn selbst aufruft. Die Aufruftiefe entspricht der Länge des Pfads, dem sie folgt, und die Einschränkungen erlauben einen Pfad durch jede Zelle: Werte, die sich in einem 100 × 100-Raster hin und her schlängeln, ergeben einen Pfad mit 10.000 Zellen, während Python standardmäßig bei 1.000 verschachtelten Aufrufen stoppt. Der folgende Code führt die Rekursion selbst aus, sodass kein Pfad zu lang für ihn ist. Halte einen Stapel von Zellen und speichere für jede Zelle, wie viele ihrer vier Richtungen du bereits ausprobiert hast. Betrachte die oberste Zelle: Wenn noch eine Richtung übrig ist, probiere sie aus und lege den Nachbarn dort auf den Stapel, wenn er größer und noch nicht fertig ist. Wenn alle vier Richtungen ausprobiert wurden, ist jeder größere Nachbar fertig; entferne also die Zelle vom Stapel und setze ihr best. Das entspricht genau der Reihenfolge, in der ein rekursiver Aufruf vorgehen würde.

Die Suche benötigt keine Markierung für „in Bearbeitung“, anders als die Zyklenerkennung. Jede Zelle auf dem Stapel ist größer als die darunterliegende, sodass sich ein größerer Nachbar der obersten Zelle niemals weiter unten auf dem Stapel befinden kann.

Algorithmus

Setze best für jede Zelle auf 0 (noch nicht bekannt) und einen Richtungszähler auf 0.
Lege jede Zelle, für die best 0 ist, auf einen Stapel.
Betrachte die oberste Zelle. Wenn es noch eine Richtung gibt, erhöhe ihren Zähler und lege den Nachbarn in dieser Richtung auf den Stapel, sofern er sich innerhalb des Gitters befindet, größer und noch nicht fertig ist.
Wenn alle vier Richtungen ausprobiert wurden, nimm die Zelle vom Stapel und setze best auf 1 plus den größten Wert von best unter ihren größeren Nachbarn oder auf 1, wenn sie keine hat.
Gib den größten Wert von best zurück.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Schäle das Raster von seinen Spitzen ab

Idee

Drehe die dynamische Programmierung um und baue sie von den höchsten Werten abwärts auf, so wie Kahns Algorithmus eine topologische Reihenfolge erstellt. Nenne eine Zelle einen Gipfel, wenn kein Nachbar größer ist. Von einem Gipfel aus kann kein Pfad weitergehen, also besteht er aus 1 Zelle. Entferne alle Gipfel gleichzeitig: Das ist Schicht 1. Nun haben einige Zellen ihren letzten größeren Nachbarn verloren und sind daher Gipfel des verbleibenden Gitters. Entferne sie als Schicht 2 und fahre fort, bis das Gitter leer ist. Die Anzahl der Schichten ist die Antwort.

Warum: Eine Zelle landet genau dann in Schicht k, wenn der längste Pfad, der an ihr beginnt, k Zellen hat. Eine Zelle wird in der Runde entfernt, nachdem ihr letzter größerer Nachbar entfernt wurde. Ihre Schicht ist also 1 plus die höchste Schicht unter ihren größeren Nachbarn. Das ist die Formel best[cell] = 1 + max(best[nb]) aus dem vorherigen Ansatz. Die tiefste Schicht gehört zum Anfang eines längsten Pfads.

Im ersten Beispiel ist die einzige Spitze die 9 (ihre Nachbarn sind 8 und 2). Durch das Entfernen der 9 wird die 8 frei, durch das Entfernen der 8 wird die 7 frei, durch das Entfernen der 7 werden die 2 und die 6 frei, durch diese beiden werden die 1 und die 5 frei, durch die 5 wird die 4 frei und durch die 4 wird die 3 frei. Das sind 7 Schichten, und der Pfad 3, 4, 5, 6, 7, 8, 9 führt durch jeweils eine Zelle jeder Schicht.

Um die nächste Schicht schnell zu finden, zähle für jede Zelle, wie viele größere Nachbarn sie noch hat. Wenn eine Zelle entfernt wird, verringert sich der Zähler jedes strikt kleineren Nachbarn. Erreicht ein Zähler 0, kommt dieser Nachbar in die nächste Schicht. Jede Zelle wird einmal entfernt und jedes Nachbarpaar wird eine konstante Anzahl von Malen betrachtet. Daher beträgt der Aufwand O(m × n), ganz ohne Stapel und Rekursion.

Algorithmus

Zähle für jede Zelle die Nachbarn mit einem größeren Wert.
Füge jede Zelle, deren Zähler 0 beträgt, der aktuellen Ebene hinzu.
Solange die Ebene nicht leer ist, erhöhe den Ebenenzähler um 1. Verringere für jede Zelle darin den Zähler jedes strikt kleineren Nachbarn und füge einen Nachbarn, dessen Zähler 0 erreicht, der nächsten Ebene hinzu.
Mache die nächste Ebene zur aktuellen und wiederhole den Vorgang.
Gib den Ebenenzähler zurück.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Stolperfallen und Grenzfälle

Die Fehler hier entstehen durch das Wort „streng“, durch tiefe Rekursion und durch Gewohnheiten, die von anderen Gitterproblemen übernommen wurden.

Vergleich mit >= statt mit >. Bei zwei benachbarten 4ern zählt jeder als Schritt nach oben gegenüber dem anderen, die Pfeile bilden eine Schleife, eine Brute-Force-Suche läuft für immer hin und her, und eine Suche mit Memoisierung liest eine Länge aus, deren Berechnung noch läuft.
Rekursion bei sehr langen Pfaden. Eine rekursive Suche geht so viele Aufrufe tief, wie der Pfad lang ist, und die Einschränkungen erlauben einen Pfad durch jede Zelle: Werte, die sich in einem 100 × 100-Gitter hin und her schlängeln, bilden einen Pfad aus 10,000 Zellen, das Zehnfache von Pythons Standardlimit von 1,000 verschachtelten Aufrufen. Für so lange Pfade brauchst du eine iterative Suche mit einem eigenen Stack oder ein erhöhtes Rekursionslimit (sys.setrecursionlimit in Python); selbst ein sehr hohes Limit kann jedoch den Stack des Interpreters überlaufen lassen.
Zellen überspringen, die bereits besucht wurden, wie bei einer Flood-Fill-Suche. Eine bereits fertig berechnete Zelle zu erreichen, ist keine Sackgasse: Ihre gespeicherte Länge ist genau das, was die aktuelle Zelle benötigt. Lies sie aus, überspringe sie nicht.
Nur beim kleinsten Wert beginnen. Im ersten Beispiel ergibt die 1 einen Pfad mit 5 Zellen, aber die Antwort, 7, beginnt bei der 3. Der längste Pfad kann bei jeder Zelle beginnen, die keinen kleineren Nachbarn hat, und solche Zellen kann es viele geben.
0 zurückgeben. Jede Zelle bildet einen Pfad aus 1 Zelle, daher ist die Antwort bei einem Gitter mit lauter gleichen Werten oder einem 1 × 1-Gitter 1. Setze die Länge für jede Zelle auf 1, nicht auf 0.
Beim Peeling-Ansatz den Zähler eines gleich großen Nachbarn verringern. Nur ein strikt kleinerer Nachbar hat einen größeren verloren.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des längsten monoton steigenden Pfads in einer Matrix?

O(m × n) Zeit und O(m × n) Speicherplatz mit memoisiertem Tiefensuchverfahren oder topologischem Abtragen. Jede der m × n Zellen wird einmal fertiggestellt und betrachtet ihre 4 Nachbarn eine konstante Anzahl von Malen, und jede Methode speichert eine Zahl pro Zelle. Alle Pfade von jeder Zelle aus auszuprobieren, ist dagegen exponentiell: Auf einem 100 × 100-Raster, in dem jeder Wert der Summe aus Zeile und Spalte entspricht, führen mehr als 10^58 Pfade von der Zelle oben links weg.

Warum benötigt dieses Problem keine Menge besuchter Knoten?

Ein Pfad, der nur aufsteigt, kann niemals zu einer Zelle zurückkehren, denn dazu müsste er wieder auf den Wert dieser Zelle hinabsteigen. Die Regel des strikt ansteigenden Verlaufs verbietet also bereits erneute Besuche, und der Graph der Schritte enthält keine Zyklen. Deshalb ist auch die Memoisierung sicher: Die Zellen vor einer bestimmten Zelle können den Pfad nach ihr nicht beeinflussen.

Ist der längste aufsteigende Pfad in einer Matrix ein Problem der dynamischen Programmierung oder ein Graphproblem?

Beides. Es ist der längste Pfad in einem gerichteten azyklischen Graphen, was dynamische Programmierung über eine topologische Ordnung bedeutet: Die Antwort für eine Zelle ist 1 plus die beste Antwort unter ihren größeren Nachbarn. Die Tiefensuche mit Memoisierung füllt die Tabelle in der Reihenfolge, in der die Suche die Zellen abschließt, und das topologische Abtragen füllt sie Schicht für Schicht, beginnend bei den Spitzen. Das Sortieren der Zellen nach Wert in absteigender Reihenfolge ergibt eine dritte gültige Reihenfolge, mit Kosten von O(m × n × log(m × n)) für die Sortierung.

Worin unterscheidet sich das von der längsten aufsteigenden Teilsequenz?

Eine Teilfolge darf Elemente überspringen und muss ihre Reihenfolge beibehalten, während ein Pfad hier zu einer angrenzenden Zelle in eine von vier Richtungen führen muss. Das Teilfolgenproblem ist dynamische Programmierung auf einer Linie; dieses Problem ist dynamische Programmierung auf einem Gitter, das in einen Graphen umgewandelt wurde. Beide beruhen auf derselben Tatsache: Eine streng steigende Kette kann niemals zu sich selbst zurückführen.

Python

def longestIncreasingPath(matrix):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Erwartet

Longest Increasing Path in a Matrix

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Folge jedem aufsteigenden Pfad

Memoisierte Tiefensuche mit einem eigenen Stack

Schäle das Raster von seinen Spitzen ab

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben