Неправильный ответ на проект Эйлера # 81

Question

Задача 81: https://projecteuler.net/problem=81 tldr: Найдите минимальную сумму путей от верхнего левого угла до нижнего правого, перемещаясь только вправо и вниз в matrix.txt, текстовом файле, содержащем матрицу 80 на 80 .

Это похоже на задачу о кратчайшем пути во взвешенном графе acycli c, и я применил к ней алгоритм Дейкстры. Я получаю правильный ответ на несколько тестовых примеров, которые я пробовал, и я получаю неправильный ответ на проблему. форматирование кода, поэтому я просто помещу их сюда.

Комментарии:

ar содержит массив, а sp - памятка, содержащая все кратчайшие пути u [0] - это число, а u [1] = i и u [2] = j Q - очередь с приоритетом, каждый элемент имеет (value, pos x, pos y) sp - это dict, который хранит кратчайшие пути к (value, pos x, pos y) S store (value, pos x, pos 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

Обновление

Как я уже сказал, я не думаю, что алгоритм Дейкстры - лучший подход, но я обновил ваш код, чтобы заставить его работать. Я добавил комментарии к измененным мной строкам. Изменения бывают двух типов:

1. Строки, прокомментированные словом «обновлено» в нижнем регистре, представляют собой незначительные изменения, которые влияют только на производительность, такие как замена использования списка набором или улучшение в стиль, такой как избавление от необходимости в блоке try-except.
2. Строки, прокомментированные словом «ОБНОВЛЕНО» в верхнем регистре, представляют реальную проблему, которую необходимо исправить.
3. Я удалил моя реализация Дейкстры, поскольку она не помогала вам найти, что не так с вашей программой. Однако учтите следующее: способ оценки текущего расстояния до местоположения x, y основан на словаре, ключ которого представляет собой кортеж (a, x, y), где a является содержимым массива в местоположении array [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)