最小コストパスの最適化が機能しない

Question

最小コスト（すべての座標に事前定義コストがあります）のn * n行列でパスを見つけるアルゴリズムを作成しようとしています。パスコストは、すべての座標コストの合計として定義されます。最初の入力行は行列のサイズを含み、次のn行はテーブル行です。コードの最後の2行は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

これはメモ化とコードであるべきであるが、（それがメモ化せずに動作しますが、それは遅いです）

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の値を計算しようとしますが、左下隅が-1であり、1, 3と1, 1の呼び出しが+infであるため、infが返されます。したがって、x=1, y=2については、正しい値1が得られます。

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

そして、私たちは私たちのmemoで1,2 -> 1を持っている：コードが行列を求める、バックトラック。 0, 2の呼び出しを終了しなければなりません。もう一度、-1, 2、0, 3、0, 1を返します。これらはすべて+infです。したがって、0 2 -> 2が正しいと計算されます。

今、問題が発生し始めます。 0, 1のコールはすでに1, 1に行きましたが、その値は-1に設定されているので、+infを返します。これは他のすべての再帰呼び出しでも同じです。したがって、我々は0, 1 -> 3が間違っていると設定します。

は、基本的には再帰呼び出し中に-1に行列に値を設定することによって、あなたは0, 1は、右に行くと1の正しい値を取得するために再帰呼び出しを防ぐことがあります。

キャッシュされたバージョンで表示される問題は、今度は* 0 1に戻るたびに間違った値になるためです。キャッシュがなければ、コードは1 1から来ないパスによって0 1に到達することができ、それゆえに0 1 -> 1が見つかります。

私は動的プログラミング手法を使用します。行列に+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に4つの出力エッジ（境界線を除く）があるグラフです。