1

我有一个 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

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

4

1 回答 1

1

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

你说原始图在搜索中没有被修改，但它是。您正在修改.parent指针。起初，所有.parent指针都设置为None，但在您运行搜索之后，其中一些指针是非None。因为它应该是None而它不是，所以while current.parent:条件未能找到路径的终点，并且它正在分支到先前计算的路径。

尝试start.parent = None在搜索开始时设置。或者在搜索完成后清除父指针（更昂贵但更干净）（您只需为opensetand中的内容清除它们closedset）。

于 2013-04-15T15:45:21.657 回答