最小成本路徑不工作的優化

Question

我想寫一個算法，它會以最小的代價（每個座標都有一個預先定義的成本）在n * n矩陣中找到路徑。路徑成本被定義爲所有座標成本的總和。第一行輸入包含矩陣的大小，後面的n行是表格行。最後兩行代碼是1.開始座標2.結束座標。輸出是最小路徑成本。

例輸入：

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 

輸出應爲0

這是memoization的代碼（它的工作原理沒有記憶化，但它的速度慢）

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

的問題是，您的使用緩存不正確。請看下面的例子，在你的代碼返回1，而不是0：如果您嘗試按照碼流，你會看到你的算法搜索矩陣通過以下方式

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

：

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

而且你是在-1當您執行遞歸調用設置在矩陣中的值，所以當你終於達到目標的矩陣是：

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

當然，您正在複製矩陣，但在遞歸調用期間，達到該點的整個路徑仍然是-1。

I.e.當您的代碼發現2, 2時，它將返回0。 1, 2上的呼叫嘗試計算0, 2的值，但返回inf，因爲左下角爲-1，1, 3和1, 1上的呼叫也返回+inf。因此，對於x=1, y=2，我們得到正確的值1。代碼回溯，得到矩陣：

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

，我們在我們的memo1,2 -> 1。我們必須完成呼叫0, 2，它再次嘗試-1, 2,0, 3和0, 1所有這些返回+inf，因此我們計算0 2 -> 2這是正確的。然而，現在事情開始出問題了。在0, 1的呼叫已嘗試去1, 1，但返回+inf，因爲該值設置爲-1，對於所有其他遞歸調用也是如此。因此我們設置了0, 1 -> 3這是錯誤的。

基本上通過在遞歸調用矩陣中的值設置爲-1你有防止遞歸調用的0, 1去的權利並獲得1正確的值。

該問題出現在緩存版本中，因爲現在*每次我們返回到0 1時，都會得到錯誤的值。沒有緩存，代碼能夠通過不是來自1 1的路徑達到0 1，因此發現0 1 -> 1。

而不是cachine我會使用動態編程方法。用+inf值填充矩陣。開始在目標位置，並把一個0那裏，然後通過行/列計算鄰近值：

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] 

然而，這仍然是效率不高，因爲它可以。如果您正確應用動態編程，您將以Bellman-Ford Algorithm結束。你的網格只是一個圖形，其中每個頂點x, y有四個輸出邊緣（邊界上的那些除外）。