python - 为什么这个寻路功能会崩溃？

Question

我有一个 A* 搜索算法，由于内存错误，该算法使程序崩溃，我不知道为什么。这些是相关的代码:

def __init__(self, graph):
    self.graph = graph

def search(self, start, end):
    openset = set()
    closedset = set()
    current = start
    openset.add(current)
    while openset:
        print current
        current = min(openset, key=lambda o:o.g + o.h)
        if current == end:
            path = []
            while current.parent:
                path.append(current)
                current = current.parent
            path.append(current)
            return path[::-1]
        openset.remove(current)
        closedset.add(current)
        for node in self.graph[current]:
            if node in closedset:
                continue
            if node in openset:
                new_g = current.g + current.move_cost(node)
                if node.g > new_g:
                    node.g = new_g
                    node.parent = current
            else:
                node.g = current.g + current.move_cost(node)
                node.h = self.heuristic(node, start, end)
                node.parent = current
                openset.add(node)
    return None

传递给它的图表是在程序启动时生成的:

def make_graph(self, size, impassable):
    nodes = [[astar_gridnode(x, y) for y in range(size)] for x in range(size)]
    graph = {}
    for x, y in product(range(size), range(size)):
        node = nodes[x][y]
        graph[node] = []
        for i, j in product([-1, 0, 1], [-1, 0, 1]):
            # Check that we are inside the grid area.
            if not (0 <= x + i < size): continue
            if not (0 <= y + j < size): continue
            # Check if the target area is impassable.
            if (x + i, y + j) in impassable: continue
            # All looks good. Add target space as reachable from current (x, y) space.
            graph[nodes[x][y]].append(nodes[x+i][y+j])
    return graph, nodes

搜索的调用方式如下:

def find_path(self, agent, target_coords, impassable, graph, nodes):
    paths = astar_grid(graph)
    start = nodes[agent.grid_pos[0]][agent.grid_pos[1]]
    end = nodes[target_coords[0]][target_coords[1]]
    path = paths.search(start, end)

这一切都像第一次完成搜索时应该的那样工作，并且如果使用开始、结束变量和不与前一个路径相交的路径完成搜索，它就会工作。如果在每次搜索之前生成一个新图，它也可以工作，但这是不可能的，因为图对象很大，会导致程序在创建时卡住几秒钟。

如果进行的搜索与先前的路径相交，则程序会卡住一分钟，并且出现此错误:

File "C:\...\pathfinding.py", line 16, in find_path
path = paths.search(start, end)
  File "C:\...\astar.py", line 19, in search
current = current.parent
MemoryError

崩溃的原因是什么？我们该如何解决？我不明白为什么它会崩溃，因为在我看来，原始图在搜索中没有被修改，并且每次调用搜索时都会创建一个新的搜索对象，这让我对它的工作原理感到困惑当它工作时，当它工作时崩溃。

Answer 1

我同意 Hughdbrown 的观点 - 你很可能在父链中有一个循环，并且在分配 current = current.parent 之前立即打印出 current 可能会告诉你你这是否属实。

您说原始图表在搜索中没有被修改，但确实。您正在修改 .parent 指针。起初，所有 .parent 指针都设置为 None，但在运行搜索后，其中一些指针变为非 None 。由于它应该是 None 但事实并非如此，while current.parent: 条件无法找到路径的末尾，并且它会分支到先前计算的路径.

尝试在搜索开始时设置start.parent = None。或者在搜索完成后清除父指针(更昂贵但更干净)(您只需清除 openset 和 linedset 中的内容)。