34

私は最初の少し複雑なアルゴリズム、AStarPathfindingアルゴリズムの実装をコーディングしました。グラフの実装に関するPython.orgのアドバイスに従って、各ノードがリンクされているすべてのノードが辞書に含まれるようにしました。さて、これはすべてゲームのためのものなので、各ノードは実際にはノードのグリッド内の単なるタイルです。したがって、ヒューリスティックとそれらへの時折の参照をどのように作成しているか。

timeitのおかげで、この関数を1秒間に100回強実行できることがわかりました。当然のことながら、これは私を少し不安にさせます。これは、グラフィックスやゲームロジックの計算など、他の「ゲーム関連」が行われていないことです。ですから、誰かが私のアルゴリズムを高速化できるかどうかを確認したいと思います。私はCythonに完全に慣れていないか、それと同類であり、Cの行をコーディングできません。

これ以上とりとめのない、これが私のAStar関数です。

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path
4

3 に答える 3

39

簡単な最適化は、開いているセットと閉じているセットのリストの代わりにセットを使用することです。

openSet   = set()
closedSet = set()

これにより、すべてのテストがO（ n ）ではなくO（1）にinなります。not in

于 2010-11-11T21:19:46.183 に答える
10

すでに述べたようにセットを使用しますが、ヒープを使用して最小要素（次の要素）を見つけますcurrent。これには、openSetとopenHeapの両方を保持する必要がありますが、メモリは実際には問題にはなりません。また、O（1）に挿入を設定し、O（log N）にヒープを設定して、高速になるようにします。唯一の問題は、heapqモジュールが実際にキーを使用するように作成されていないことです。個人的には、キーを使用するように変更するだけです。それほど難しいことではないはずです。または、ヒープ内で（tile.H、tile）のタプルを使用することもできます。

また、再帰の代わりに反復を使用するというaaronasterlingの考えに従いますが、最後に要素を追加し、最後にpath逆pathにします。その理由は、リストの0番目にアイテムを挿入するのは非常に遅いため（O（N）だと思います）、正しく思い出せば、追加するのはO（1）です。その部分の最終的なコードは次のようになります。

def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

あなたのコードからそうあるべきであるように見えたので、私は最後にリターンパスを置きました。

セット、ヒープなどを使用した最終的なコードは次のとおりです。

import heapq


def aStar(graph, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()

    def retracePath(c):
        path = [c]
        while c.parent is not None:
            c = c.parent
            path.append(c)
        path.reverse()
        return path

    openSet.add(current)
    openHeap.append((0, current))
    while openSet:
        current = heapq.heappop(openHeap)[1]
        if current == end:
            return retracePath(current)
        openSet.remove(current)
        closedSet.add(current)
        for tile in graph[current]:
            if tile not in closedSet:
                tile.H = (abs(end.x - tile.x)+abs(end.y-tile.y))*10
                if tile not in openSet:
                    openSet.add(tile)
                    heapq.heappush(openHeap, (tile.H, tile))
                tile.parent = current
    return []
于 2010-11-12T00:23:51.160 に答える
5

上で提案したようclosedSetに、セットにします。

openListヒープとしてコーディングしてみましたimport heapq：

import heapq

def aStar(self, graph, current, end):
    closedList = set()
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList = [(-1, current)]
    heapq.heapify(openList)
    while openList:
        score, current = openList.heappop()
        if current == end:
            return retracePath(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.heappush((tile.H, tile))
                tile.parent = current
    return path

ただし、で検索する必要があるため、次if tile not in openListのようにします。

def aStar(self, graph, current, end):
    openList = set()
    closedList = set()

    def retracePath(c):
        def parentgen(c):
             while c:
                 yield c
                 c = c.parent
        result = [element for element in parentgen(c)]
        result.reverse()
        return result

    openList.add(current)
    while openList:
        current = sorted(openList, key=lambda inst:inst.H)[0]
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.add(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                openList.add(tile)
                tile.parent = current
    return []
于 2010-11-11T21:53:51.997 に答える