减少加权网格路径查找器的时间复杂度

Question

[在学校，我为加权网格制作了一个探路器，但是超出7x7网格的任何内容都需要花费大量时间。我想知道我是否可以完全改善我的代码，或者是否有办法降低时间复杂度。无论是可读性还是效率，我都会感谢任何改进我的代码的指针。谢谢

import math
import random

class Grid:
    def __init__(self,width,height):
        self.board = []
        self.width = width;
        self.height = height; 
        for x in range(width*height):
            self.board.append([])
        for x in range(width):
            for y in range(height):
                rand = random.randint(0,3)
                self.board[x].append(rand)
    def display(self):
        for x in range(self.width):
            for y in range(self.height):
                print(str(self.board[x][y]) + " ",end="")
            print()

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def add(self,x,y):
        return Point(self.x+x,self.y+y)
    def sub(self,x,y):
        return Point(self.x-x,self.y-y)

class Node:
    def __init__(self,start,end):
        self.start = start
        self.end = end
        self.elements = [start]
    def size(self):
        return len(self.elements)
    def get(self,index):
        return self.elements[index]
    def append(self,element):
        self.elements.append(element)
    def calc(self,grid):
        cur_point = self.elements[self.size()-1]
        total = distance(cur_point,end)
        for x in range(self.size()):
            point = self.elements[x]
            total += grid.board[point.x][point.y]
        return total
    def clone(self):
        node = Node(self.start,self.end)
        node.elements = self.elements[:]
        return node
    def display_path(self,grid):
        for x in range(self.size()):
            point = self.elements[x]
            grid.board[point.x][point.y] = "P"
        grid.display()

class PriorityList:
    def __init__(self,node):
        self.elements = [node]
    def size(self):
        return len(self.elements)
    def get(self,index):
        return self.elements[index]
    def append(self,element):
        self.elements.append(element)
    def sort(self,grid):
        index = 1
        while index < self.size():
            node = self.elements[index]
            n = self.elements[index-1]
            if node.calc(grid) < n.calc(grid):
                self.elements[index] = n
                self.elements[index-1] = node
                index = 1
            index += 1

def distance(p1,p2):
    return math.sqrt( math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2) )

def getPoint(x,y):
    x = int(input("Enter " + x + ": "))
    y = int(input("Enter " + y + ": "))
    return Point(x,y)

print("Customize grid...")
dimensions = getPoint("Width","Height")
print("Enter the starting point...")
start = getPoint("X","Y").sub(1,1)
print("Enter the ending point...")
end = getPoint("X","Y").sub(1,1)

grid = Grid(dimensions.x,dimensions.y)
grid.display()

print()

n = Node(start,end)

queue = PriorityList(n)

class Pathfinder(Exception): pass
try:
    while True:
        queue.sort(grid)
        node = queue.get(0)
        discovered = False
        for x in range(-1,2):
            for y in range(-1,2):
                point = node.get(node.size()-1)
                if point.x + x >= 0 and point.y + y >= 0 and point.x + x < grid.width and point.y + y < grid.height:
                    if x != 0 or y != 0:
                        discovered = True
                        new = node.clone()
                        new.append(point.add(x,y))
                        queue.append(new)
                        if point.x+x == end.x and point.y+y == end.y:
                            score = new.calc(grid)
                            new.display_path(grid)
                            print("Score: " + str(score))
                            raise Pathfinder
                        discovered = True
        if discovered:
            queue.elements.remove(queue.get(0))
except Pathfinder:
    pass          

Answer 1

此问题属于Code Review SE，您可能在那里会得到更好的答案。但是我想提几件事。

我建议使用numpy而不是Python列表。例如您的numpy类

Grid

可以简化为：

class YourGrid:
    def __init__(self,width,height):
        self.board = []
        self.width = width;
        self.height = height; 
        for x in range(width*height):
            self.board.append([])
        for x in range(width):
            for y in range(height):
                rand = random.randint(0,3)
                self.board[x].append(rand)
    def display(self):
        for x in range(self.width):
            for y in range(self.height):
                print(str(self.board[x][y]) + " ",end="")
            print()

与更大的电路板尺寸进行比较：

class NumpyGrid:
    def __init__(self, width, height): 
        self.width = width
        self.height = height
        self.board = np.random.randint(0, 4, size=(width, height))

    def display(self):
        print(self.board)

这当然会扩大：随着增加大小，直接的Python列表实现会变慢。尽可能避免for循环，追加方法，这会使代码效率低下。 PyCon的Jake VanderPlas对此有一个

>>> %timeit YourGrid(100, 100)
17.6 ms ± 215 µs per loop
>>> %timeit NumpyGrid(100, 100)
73.7 µs ± 3.38 µs per loop

。这对于您的nice talk部分尤其如此：那里的列表操作过多，因此放慢了速度。

我认为您的while True类应实现更多功能。以距离为例，这并不难：

Point

如果不使用任何类功能，为什么要使其面向对象？

[另外，使用

    def distance(self, other):
        if not isinstance(other, Point):
            raise TypeError("Point object is expected.")
        return math.sqrt(math.pow(other.x-self.x,2) + math.pow(other.y-self.y,2)) 

或numpy.linalg.norm计算点之间的距离要快得多，但这可能是一个过大的杀伤力。

此

numpy.linalg.norm

应该是

scipy.spatial.distance.cdist

并且可以通过scipy.spatial.distance.cdist访问。

def size(self):
        return len(self.elements)

应该是

def __len__(self):
        return len(self.elements)

在len(object)类中，您将返回其自身的新实例。我不认为你应该那样做。也许您只想就地修改x和y，所以可以是

def get(self, index):

注意，还有一个称为def __getitem__(self, indeces): 的内置方法。

您的整个主脚本应该在Point防护中：

def add(self, x, y):
    self.x += x
    self.y += y

您不验证任何用户输入。

您通过自定义例外中断了__add__主循环。我认为可能只是__main__，没有意义。或将条件移至while循环。我的意思是一个小草图：

if __name__=='__main__':
    print("Customize grid...")
    dimensions = getPoint("Width","Height")
...

根据样式，应遵循while。

我不会尝试重写它，但是除了上面我发布的内容外，可能还有很多需要改进的地方。