Python

Question

这是我制作的迷宫解算器，但它无法解决大迷宫（需要很长时间..）。我怎样才能加快这个过程？

import numpy as np
T=np.array([
            [0,1,1,0,0,0],
            [0,0,0,1,1,0],
            [0,1,0,0,1,0],
            [0,1,1,0,0,0],
            [0,0,1,0,0,0],
            [1,1,0,0,1,0]
            ])
trajs=[]
def voi(T,i,j):
    d=[]
    for coor in [(i-1,j),(i,j-1),(i,j+1),(i+1,j)]:
            if 0<=coor[0]<len(T) and 0<=coor[1]<len(T[coor[0]]) and T[coor[0],coor[1]]==0: 
                d=d+[coor]
    return d
def trajet(T,tra,sor):
    M=T.copy()
    while tra[-1]!=sor and len(voi(M,tra[-1][0],tra[-1][1]))==1:
        tra=tra+[voi(M,tra[-1][0],tra[-1][1])[0]]     
        M[tra[-2][0],tra[-2][1]]=-1
    if tra[-1]==sor:
        trajs.append(tra)
    elif len(voi(M,tra[-1][0],tra[-1][1]))>1:
        for i in range(len(voi(M,tra[-1][0],tra[-1][1]))):
            t=tra+[voi(M,tra[-1][0],tra[-1][1])[i]]
            M[t[-2][0],t[-2][1]]=-1  
            trajet(M,t,sor)
trajet(T,[(0,0)],(5,5))

Answer 1

在不修改算法的情况下，除了减少函数调用的次数外，您无能为力。

比如T的大小是固定的，可以避免在voi()函数中多次调用len(T)和len(T(coord[0]))。

您还可以简化 coord[0] 和 coord[1]：每个调用一个函数。

您可以这样重写 voi() 函数：

def voi(T, i, j):
    d = []
    max_x = len(T)
    max_y = len(T[0])
    for x, y in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]:
        if (0 <= x < max_x) and (0 <= y < max_y) and (T[x, y] == 0):
            d += [(x, y)]
    return d

注： d = d + ...可以用d += ...代替。

您可以对 trajet() 函数应用相同的原则：

def trajet(T, tra, sor):
    M = T.copy()
    last_x, last_y = tra[-1]
    while True:
        if (last_x, last_y) == sor:
            trajs.append(tra)
            break
        voi_list = voi(M, last_x, last_y)
        if not voi_list:
            break
        elif len(voi_list) > 1:
            voi_list = voi(M, last_x, last_y)
            if len(voi_list) > 1:
                for voi_item in voi_list:
                    t = tra + [voi_item]
                    M[last_x, last_y] = -1
                    trajet(M, t, sor)
            break
        else:
            voi_first = voi_list[0]
            tra += [voi_first]
            M[last_x, last_y] = -1
            last_x, last_y = voi_first

Python - 升级我的迷宫求解器程序

Python - Upgrading my labyrinth solver program

algorithm

numpy

solver