Optimierung der minimalen Kosten Pfad funktioniert nicht

Question

Ich versuche, einen Algorithmus zu schreiben, der den Pfad in n * n Matrix mit minimalen Kosten finden wird (jede Koordinate hat einen vordefinierten Kosten). Die Pfadkosten sind definiert als die Summe aller Koordinatenkosten. Die erste Eingabezeile enthält die Größe einer Matrix und die folgenden n Zeilen sind Tabellenzeilen. Die letzten zwei Codezeilen sind 1. Anfangskoordinaten 2. Endekoordinaten. Ausgabe ist die minimale Pfadkosten.

Beispiel Eingabe:

5 
0 1 2 1 1 
0 0 1 5 1 
1 0 0 1 1 
1 1 0 7 0 
1 8 0 0 0 
0 0 
4 4 

Ausgang 0

sein soll Dies ist Code mit memoization (es ohne memoization funktioniert, aber es ist langsam)

import copy 
import sys 

sys.setrecursionlimit(9000) 

INF = 100000 

n = int(input()) 

memo = {} 

def input_matrix(n) : 
    p = [] 
    for i in range(n) : 
     p.append(list(map(int, input().split()))) 
    return p 

def min_cost(matrix, x, y, end_x, end_y) : 
    if x == end_x and y == end_y : 
     return 0 
    if (x, y) in memo : 
     return memo[(x, y)] 
    if x == len(matrix) or y == len(matrix) or x == -1 or y == -1 or matrix[y][x] == -1: 
     return INF 

    z = copy.deepcopy(matrix) 
    z[y][x] = -1 

    memo[(x, y)] = min(
     min_cost(z, x+1, y, end_x, end_y)+matrix[y][x], 
     min_cost(z, x-1, y, end_x, end_y)+matrix[y][x], 
     min_cost(z, x, y+1, end_x, end_y)+matrix[y][x], 
     min_cost(z, x, y-1, end_x, end_y)+matrix[y][x] 
    ) 
    return memo[(x, y)] 

matrix = input_matrix(n) 

begin_coords = list(map(int, input().split())) 
end_coords = list(map(int, input().split())) 

print(min_cost(matrix, begin_coords[0], begin_coords[1], end_coords[0], end_coords[1])) 

Answer 1

Das Problem ist, dass die Nutzung von Der Cache ist nicht korrekt. Betrachten Sie das folgende Beispiel, in dem Ihr Code gibt 1 statt 0:

3 
0 0 1 
1 0 0 
1 1 0 
0 0 
2 2 

Wenn Sie versuchen, den Code Fluss folgen Sie werden sehen, dass Ihre Algorithmen, um die Matrix in der folgenden Art und Weise durchsucht:

0 -> 0 -> 1 -> x 
      | 
1 <- 0 <- 0 -> x 
| 
1 -> 1 -> 0 

Darüber hinaus setzen Sie den Wert in der Matrix bei -1, wenn Sie den rekursiven Aufruf durchführen, so dass, wenn Sie schließlich das Ziel erreichen die Matrix:

-1 -1 -1 
-1 -1 -1 
-1 -1 0 

Sicher, Sie kopieren die Matrizen, aber während eines rekursiven Aufrufs bleibt der gesamte Pfad, der zum Erreichen dieses Punkts verwendet wurde, -1.

I.e. Wenn der Code 2, 2 findet, wird 0 zurückgegeben. Der Anruf auf versucht, den Wert für 0, 2 zu berechnen, gibt aber inf zurück, da die untere linke Ecke -1 ist, der Anruf auf 1, 3 und 1, 1 auch +inf zurückgeben. So erhalten wir für x=1, y=2 den richtigen Wert 1. Der Code Backtracking, den Erhalt der Matrix:

-1 -1 -1 
-1 -1 -1 
-1 1 0 

Und wir haben 1,2 -> 1 in unserem memo. Wir müssen den Anruf für 0, 2 beenden, die wiederum versucht -1, 2, 0, 3 und 0, 1 alle diese zurück +inf und damit berechnen wir 0 2 -> 2, die korrekt ist.

Jetzt aber beginnt die Dinge zu schief gehen. Der Anruf bei 0, 1 hat bereits versucht, 1, 1 gehen, aber das +inf zurückgibt, da der Wert auf -1 festgelegt ist, das gleiche gilt für alle anderen rekursiven Aufrufe. Daher setzen wir 0, 1 -> 3was falsch ist.

Grundsätzlich durch den Wert in der Matrix zu -1 bei rekursiven Aufruf Einstellung haben Sie den rekursive Aufruf verhindern für 0, 1 nach rechts zu gehen und den richtigen Wert von 1 erhalten.

Das Problem tritt in der zwischengespeicherten Version auf, weil jetzt * jedes Mal, wenn wir zu 0 1 zurückkehren, wir den falschen Wert erhalten.Ohne Cache ist der Code in der Lage 0 1 über einen Pfad zu erreichen, der nicht von 1 1 kommt und daher das 0 1 -> 1 entdeckt.

Anstelle von Cachine würde ich einen dynamischen Programmieransatz verwenden. Füllen Sie die Matrix mit +inf Werten. Beginnen Sie an der Zielposition und legt ein 0 dort, dann berechnen die benachbarten Werte von Zeile/Spalte:

def min_cost(matrix, x, y, end_x, end_y): 
    n = len(matrix) 
    memo = [[float('+inf') for _ in range(n)] for _ in range(n)] 
    memo[end_y, end_x] = 0 
    changed = True 
    while changed: 
     changed = False 
     for x in range(n): 
      for y in range(n): 
       m = matrix[y][x] 
       old_v = memo[y][x] 
       memo[y][x] = min(
        memo[y][x], 
        m + min(memo[h][k] for h in (y-1, y+1) if 0 <= h < n for k in (x-1, x+1) if 0 <= k < n) 
       ) 
       if memo[y][x] != old_v: 
        changed = True 
    return memo[y, x] 

aber dies noch nicht so effizient ist, wie es sein könnte. Wenn Sie die dynamische Programmierung korrekt anwenden, erhalten Sie die Bellman-Ford Algorithm. Ihr Raster ist nur ein Diagramm, in dem jeder Knoten x, y vier ausgehende Kanten hat (außer denen an der Grenze).