-1

以下の 5 行 5 列の行列では、左上から右下へ、右と下にのみ移動することによる最小パスの合計は、太字の赤で示され、2427 に等しくなります。

131 673 234 103 18

201 96 342 965 150

630 803 746 422 111

537 699 497 121 956

805 732 524 37 331

最小パス合計を、matrix.txt (右クリックして [リンク/ターゲットを名前を付けて保存...]) で見つけます。これは、80 x 80 のマトリックスを含む 31K テキスト ファイルで、左上から右下に移動するだけで右に移動し、下。

備考: 彼らが道をマークするとき、彼らは間違いを犯したと思いますhttp://projecteuler.net/problem=81

import numpy as np

matrix0 = [ map(int, row.split()) for row in open('matrix.txt')]

matrix=np.arange(6400).reshape(80,80)

for i in range(80):
    for j in range(80):
        matrix[i, j]=0

for i in range(80):
    for j in range(80):
        matrix[i, j]=matrix0[i][j]

sum=matrix[0,0]

k=0
n=0
while (k+n)<158:
    for i in range(k, k+1):
        for j in range(n, n+1):
            if i!=79 and j!=79:
                if matrix[i+1, j]<=matrix[i, j+1]:
                    sum=sum+matrix[i+1, j]
                    k=i+1
                    n=j
                else:
                    sum+=matrix[i, j+1]
                    k=i
                    n=j+1
            elif i==79:
                sum+=matrix[i, j+1]
                k=i
                n=j+1
            elif j==79:
                sum+=matrix[i+1, j]
                k=i+1
                n=j                 

print sum

問題のようなマトリックス5x5にこのコードを使用すると、正しい答えが得られます。より大きなマトリックスで機能しない理由がわかりませんか?

4

1 に答える 1

5

検索を適切に実行していないためです。問題は全体の最小コスト パスを求めているため、A* 検索またはダイクストラのアルゴリズムが必要です。各ノードで最も低いブランチの単純な 1 回のパス チェックでは、それをカットできません。

于 2012-06-27T08:21:45.870 に答える