-1

在下面的 5 x 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（右键单击并“将链接/目标另存为...”）中找到最小路径总和，这是一个 31K 的文本文件，其中包含一个 80 x 80 矩阵，从左上角到右下角只需向右移动和下。

备注：我认为他们做错了，当他们标记方式时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* 搜索或 Dijkstra 算法。对每个节点的最低分支进行简单的一次通过检查不会削减它。

于 2012-06-27T08:21:45.870 回答