-2

まず、これが問題です: https://projecteuler.net/problem=82。これは私のコードです:

# https://projecteuler.net/problem=82

matrice = open('matrix3.txt','r').read().split('\n')
m = []
for el in matrice:
    if el=='':
        continue
    tmp = el.split(',')
    m.append(tmp)
matrix = [[0 for i in range(80)]for j in range(80)]
x,y = 0,0
while(True):
    matrix[x][y]=int(m[x][y])
    y+=1
    if y==80:
        y=0
        x+=1
        if x==80:
            break 
tmp = [0]*80
x,y = 0,78
while(True):
    if x==0:
        tmp[x]=min(matrix[x][y+1],matrix[x+1][y]+matrix[x+1][y+1])
    if x==79:
        tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1])
    else:
        tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1],matrix[x+1][y]+matrix[x+1][y+1])
    x+=1
    if x==80:
        for e in range(80):
            matrix[e][y]+=tmp[e]
        tmp = [0]*80
        x=0
        y+=-1
        if y<0:
            break
minimo = 10**9
for e in range(80):
     if matrix[e][0]<minimo:
        minimo=matrix[e][0]
print(minimo)

このコードの背後にある考え方は次のとおりです。79 番目の列 (0 からカウントを開始する場合は 78 番目) から開始し、その列の特定のエントリから右の列に到達するための最良の (最小限の) 方法を計算します。コラムが終わったら、見つけた最小限の結果に置き換え、左側のコラムで同じことを始めます。

なぜ私が間違った答えを得たのかを理解するのを手伝ってくれる人はいますか? (私は 262716 を受け取ります)

例の行列に対して同じコードが機能します (もちろん、インデックスを変更すると機能します)。

4

1 に答える 1

3

質問、コード、およびアルゴリズムを正しく理解していれば、ある列から次の列に移動するための最良の方法を実際に計算していないように見えます。次の列。たとえば、最初の反復 ( when y=78) を考えてみましょう。次に、あなたが望むのは、79 番目の列のどこかにtmp[0]到達するための最小合計を保持することだと思いますが、2 つの可能性のみを考慮します: 右に移動するか、下に移動してから右に移動します。matrix[0][78]次の列に移動する最善の方法が、matrix[0][78]6 エントリ下に移動してから右に移動することだとしたら? あなたのコードはその可能性を決して考慮しません。

最小パスが各列で一度だけ上下することが起こるため、コードはおそらく小さな例で機能します。しかし、それは偶然だと思います (また、選択が不十分な例でもある可能性があります)。

この問題を解決する 1 つの方法は、次のアプローチを使用することです。入力が NxN 行列の場合、NxN array を定義しますmin_path。入力行列の最初の列の任意のエントリから始まり、 で終わるパスの合計が最小にmin_pathなるように入力します。一番左の列から始めて、一度に 1 列ずつ入力します。を計算するには、 の (j-1) 列のすべてのエントリと、それらの各エントリから (i, j) に到達するコストを調べます。このソリューションを示す Python コードを次に示します: https://gist.github.com/estark37/5216851。これは O(N^4) ソリューションですが、おそらくより高速にすることができます! （おそらく、呼び出しの結果を事前に計算することによってですか？）min_path[x][y][x][y]min_pathmin_path[i][j]min_pathsum_to

于 2013-03-21T21:22:40.013 に答える