Dreieck Max Summe mit Tiefe zuerst Suche

Question

Ich habe das klassische Problem mit einem Dreieck und müssen den maximalen Weg zu bekommen. Ich darf von (i, j) (i, j-1), (i, j + 1), (i + 1, j)

Beispiel Eingänge bewegen:

 1 
    1 2 3 
    1 2 3 4 5 
1 2 3 4 5 6 7 

und der maximale Pfad ist die Summe von (1) + (2 + 3) + (4 + 3 + 2 + 1) + (2 + 3 + 4 + 5 + 6 + 7). Ich bin nicht zu bewegen, auf einem Knoten zweimal

Ich weiß, erlaubt, wie dies mit DP zu lösen, aber dieses Problem zu uns wurde bei der künstlichen Intelligenz Klasse gezeigt und die Lösung es braucht, ist mit der DFS/GBFS

Wie Ist es möglich, dieses Problem mit DFS zu lösen? Nur rekursiv kam mir in den Sinn, aber es ist nicht in der Nähe von DFS.

Ich bin die Eingabe als eine Kurve, die darstellt, so dass für die

folgenden

1 
    2 3 4 
5 6 7 8 9 

Ich habe folgende Diagramm 1 -> {3} 3 -> {2, 4, 7}, 4 - > {3, 8} etc

ich eine rekursive Funktion zu tun, maxsum (Knoten) und von Knoten 1 und tun so etwas wie das

Rückkehr Max (maxsum (neighbour_1), maxsum (neighbour_2 beginnen dachte) , ..., MaxSum (Nachbar_n)) + Knoten

wo jeder neighbour_i ist nicht besucht Nachbar

Aber wo kommt der DFS-Teil? Wie könnte ich dieses Problem mit GBFS lösen?

Ich bin nicht daran interessiert, Code oder etwas, nur algorithmische Erklärungen

Answer 1

Aber woher kommt der DFS Teil reinkommen?

Der Graph Sie acyclisch ist, und das aufgetretene Problem zu lösen versuchen, ist longest path problem (nachdem der Knoten Gewichte Umwandlung Gewichte zum Rand). Die allgemeine Lösung erfordert, dass Sie DFS verwenden, um eine topologische Ordnung zu finden, aber in Ihrem Fall wissen, dass Sie eine einfache topogical bestellen, das gerade wie in Ihrem Beispiel:

1 
    2 3 4 
5 6 7 8 9 

Mit diesem Auftrag für zweiten Teil - die DP-Lösung . In gewisser Weise überspringst du den DFS Teil.

Sie könnten explizit DFS für den ersten Pfad ausführen und es könnte eine andere topologische Reihenfolge geben (abhängig davon, wie Sie die Kanten durchlaufen), aber es ist nur eine Verschwendung von Aufwand.

Auch für den zweiten Teil, anstatt die DP durchzuführen, könnten Sie BFS Ebene für Ebene verwenden, um die Nachbarn der Elemente in der aktuellen Ebene zu aktualisieren. Aber auch hier macht es wenig Sinn, da die Verwendung von DP die gleichen Ergebnisse liefert und sogar billiger wäre.