对Euler项目的错误回答#81

Question

问题81： https://projecteuler.net/problem=81 tldr：只需在matrix.txt（一个包含80×80矩阵的文本文件）中向右和向下移动，即可找到从左上到右下的最小路径和

这看起来像是一个加权边无环图中的最短路径问题，我将dijkstra算法应用于它。我试过的一些测试用例得到了正确的答案，但我得到了问题的错误答案

编辑：出于某种原因，当我在代码中添加注释时，它会将其格式设置为粗体，并破坏代码的格式设置，所以我将把它们放在这里

评论：

ar包含数组，sp是包含所有最短路径的备忘录 u[0]是数字，u[1]=i，u[2]=j Q是一个优先级队列，每个元素都有（值，位置x，位置y） sp是一个dict，它存储到（值、位置x、位置y）的最短路径 S存储我们已知最短路径的项目（值、位置x、位置y）

我的代码：

import numpy as np


def readfile(filename):
    file = open(filename,"r")
    ar=np.zeros((80,80))
    sp={}
    for i in range(80):
        l=file.readline()
        line=l.split(',')
        for j in range(80):
            ar[i][j]=int(line[j])
            sp[(int(line[j]),i,j)]=10000000
    return ar,sp

def extract_min():
    min_n,i,j=100000,-1,-1
    for n in Q:
        if n[0]<min_n:
            min_n=n[0]
            i=n[1]
            j=n[2]
    return min_n,i,j

def adj(u):

    try: a,i,j=(ar[u[1]][u[2]+1],u[1],u[2]+1)
    except:a,i,j=-1,-1,-1
    try: b,k,m=(ar[u[1]+1][u[2]],u[1]+1,u[2])
    except:b,k,m=-1,-1,-1
    return ((a,i,j),(b,k,m))

def relax(u,v):

    if sp[v]>sp[u]+v[0]:
        sp[v]=sp[u]+v[0]
        parent[v]=u

def dijkstra():

    Q.append(source)
    S=[]
    while len(Q)!=0:
        u=extract_min()
        Q.remove(u)
        S.append(u)
        for v in adj(u):
            if v not in Q and v not in S and v[0]!=-1:
                relax(u,v)
                Q.append(v)

ar,sp=readfile("p081_matrix.txt")
source=(ar[0][0],0,0)
dest=(ar[79][79],79,79)
sp[source]=source[0]
Q=[]
parent={}
dijkstra()
print(sp[dest])

Answer 1

这个问题不需要复杂的树搜索。答案可以在单个过程中迭代计算

下面是一个简单的解决方案，它从上到下、从左到右遍历矩阵的单元格，累加总和，并根据上面和左边单元格的计算值选择最小的一个。第一行和第一列是无条件求和，因为没有备用路径可通过

from itertools import accumulate
def minSumPath(M):
    R = list(accumulate(M[0]))
    for row,values in enumerate(M[1:],1):
        R = [*accumulate((R[0]+values[0],*zip(R[1:],values[1:])),
                         lambda left,rv:min(left,rv[0])+rv[1])]   
    return R[-1]
           
M = [ [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]]

print(minSumPath(M)) # 2427

随着循环的进行，R保持到前一行中每个位置的最小和路径。在上述示例中，R将按如下方式进行：

[131,  804,  1038, 1141, 1159]
[332,  428,   770, 1735, 1309]
[962,  1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, 2096, 2427]

最后一行的最后一个值就是答案

注意，这种方法可以很容易地调整为使用行迭代器作为输入。这样，它将非常节省内存，因为它只需要保存2行数据即可处理输入文件

您还可以使用一种简单的递归方法，通过计算右下角单元格左上方单元格的和路径来获得结果。即使使用记忆，这也比上面的迭代解决方案慢60倍。这是一种有趣的概念方法：

from functools import lru_cache

def minSumPath(M):
    
    @lru_cache() # needs hashable (tuple) parameters
    def minSumPathT(T):
        if 1 in map(len,(T,T[0])): return sum(map(sum,T)) # single row or column
        fromAbove = minSumPathT(T[:-1])
        fromLeft  = minSumPathT(tuple(row[:-1] for row in T))
        return T[-1][-1] + min(fromAbove,fromLeft)
    
    return minSumPathT(tuple(map(tuple,M)))

Answer 2

更新

正如我所评论的，我不认为Dijkstra的算法是最好的方法，但我已经更新了您的代码，使其能够工作。我在修改的行中添加了注释。这些变化有两种类型：

1. 用小写字母“updated”注释的行表示仅影响性能的微小更改，例如用集合替换列表的使用，或者改进样式，例如不再需要try-except块
2. 用大写字母“UPDATED”注释的行表示需要纠正的实际问题
3. 我删除了Dijkstra实现，因为它在帮助您发现程序错误方面没有任何用处。但是，考虑一下：你估计当前X到Y位置的距离是一个字典，其字典是一个元组^ {< CD1> }，{{< CD2}}是数组[x，y]上数组的内容，其值是距离。为什么不使用一个由x和y索引的二维数组，其值是距离，这就是我所使用的

更正后的代码：

import numpy as np


def readfile(filename):
    file = open(filename,"r")
    ar=np.zeros((80,80), dtype=np.int32) #updated: use an integer type
    sp={}
    for i in range(80):
        l=file.readline()
        line=l.split(',')
        for j in range(80):
            ar[i][j]=int(line[j])
            sp[(int(line[j]),i,j)]=10000000
    return ar,sp

def extract_min():
    min_n,i,j=100000,-1,-1
    for n in Q:
        if n[0]<min_n:
            min_n=n[0]
            i=n[1]
            j=n[2]
    return min_n,i,j

def adj(u): #updated: new replacement that does not use try/except

    l = []
    row = u[1]
    col = u[2]
    if row < 79:
        l.append((ar[row+1][col], row+1, col))
    if col < 79:
        l.append((ar[row][col+1], row, col+1))
    return l

def relax(u,v):

    if sp[v]>sp[u]+v[0]:
        sp[v]=sp[u]+v[0]
        parent[v]=u
        return True # UPDATED
    return False #UPDATED

def dijkstra():

    Q.add(source) #updated
    #S=[] #UPDATED
    while len(Q)!=0:
        u=extract_min()
        Q.remove(u)
        #S.add(u) #UPDATED
        for v in adj(u):
            if relax(u, v) and v not in Q: #UPDATED
                Q.add(v) #UPDATED

def print_path_and_sum(): #updated

    l = []
    n = dest
    while n:
        l.append(n)
        n = parent.get(n)
    sum = 0
    while l:
        n = l.pop()
        sum += n[0]
        print(n)
    print(sum)

ar,sp=readfile("p081_matrix.txt")
source=(ar[0][0],0,0)
dest=(ar[79][79],79,79)
sp[source]=source[0]
Q=set() # updated
parent={}
dijkstra()
print_path_and_sum() #updated
print(sp[dest])

不同的解决方案

def solve(matrix):
    MAX_N = len(matrix) - 1
    # do last row:
    for col in range(MAX_N - 1, -1, -1):
        matrix[MAX_N][col] += matrix[MAX_N][col + 1]
    # do remaining rows:
    for row in range(MAX_N - 1, -1, -1):
        for col in range(MAX_N, -1, -1):
            if col == MAX_N:
                matrix[row][col] += matrix[row + 1][col]
            else:
                matrix[row][col] += min(matrix[row][col+1], matrix[row + 1][col])
    return matrix[0][0]

matrix = []
with open('p081_matrix.txt') as f:
    for line in f:
        matrix.append([int(n) for n in line.split(',')])
print(solve(matrix))

使用路径信息发布不同的解决方案

from copy import deepcopy

def solve(matrix):
    for row in range(MAX_N, -1, -1):
        for col in range(MAX_N, -1, -1):
            if row == MAX_N and col == MAX_N:
                continue
            if col == MAX_N:
                follow[(row, col)] = (row + 1, col)
                matrix[row][col] += matrix[row + 1][col]
            elif row == MAX_N:
                follow[(row, col)] = (row, col + 1)
                matrix[row][col] += matrix[row][col + 1]
            elif matrix[row][col+1] < matrix[row + 1][col]:
                follow[(row, col)] = (row, col + 1)
                matrix[row][col] += matrix[row][col + 1]
            else:
                follow[(row, col)] = (row + 1, col)
                matrix[row][col] += matrix[row + 1][col]
    return matrix[0][0]

def print_path_and_sum():
    sum = 0
    t = (0, 0)
    while t:
        v = matrix_copy[t[0]][t[1]]
        print(t, v)
        sum += v
        t = follow.get(t)
    print(sum)

matrix = []
with open('p081_matrix.txtt') as f:
    for line in f:
        matrix.append([int(n) for n in line.split(',')])
MAX_N = len(matrix) - 1
follow = {}
matrix_copy = deepcopy(matrix)
solution = solve(matrix)
print_path_and_sum()
print(solution)