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)

これはすべて、最初に検索が行われたときと同じように機能し、開始変数、終了変数、および前のパスと交差しないパスで検索が行われた場合に機能します。各検索の前に新しいグラフが生成される場合にも機能しますが、グラフ オブジェクトが巨大であり、作成時にプログラムが数秒間フリーズするため、これは不可能です。

以前のパスと交差する検索が行われると、プログラムが 1 分間フリーズし、次のエラーが発生します。

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

私はhuhdbrownに同意します—親チェーンにサイクルがある可能性が非常に高く、current割り当ての直前に印刷すると、current = current.parentこれが真実かどうかがわかります。

元のグラフは検索で変更されていないとおっしゃっていますが、そうです。.parentポインターを変更しています。最初はすべての.parentポインターが に設定されてNoneいますが、検索を実行すると、一部のポインターが に設定されていませんNone。そうあるべきNoneではないため、while current.parent:条件はパスの終わりを見つけることができず、以前に計算されたパスに分岐しています。

start.parent = None検索の先頭に設定してみてください。opensetまたは、検索が終了した後に親ポインターをクリアします (より高価ですが、よりクリーンです) (および内のものに対してのみクリアする必要がありますclosedset)。

于 2013-04-15T15:45:21.657 に答える