ordenamiento - Python: agiliza un algoritmo de búsqueda de estrellas

ejemplos de busqueda secuencial

Question

He codificado mi primer algoritmo ligeramente complejo, una implementación del algoritmo A Star Pathfinding . Seguí algunos consejos de Python.org sobre la implementación de gráficos para que un diccionario contenga todos los nodos a los que está vinculado cada nodo. Ahora, dado que esto es todo por un juego, cada nodo es realmente solo un mosaico en una grilla de nodos, por lo tanto, cómo estoy resolviendo la heurística y mi referencia ocasional a ellos.

Gracias a timeit, sé que puedo ejecutar esta función con éxito un poco más de cien veces por segundo. Es comprensible que esto me sienta un poco incómodo, sin otros elementos de juego, como los gráficos o el cálculo de la lógica del juego. Así que me encantaría ver si alguno de ustedes puede acelerar mi algoritmo, no estoy completamente familiarizado con Cython o su parentesco, no puedo codificar una línea de C.

Sin más divagaciones, esta es mi función A Star.

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

Answer 1

Como se sugirió anteriormente, convierta closedSet en un conjunto.

Intenté codificar openList como heap de import heapq montón:

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

Sin embargo, aún necesita buscar if tile not in openList , así que haría esto:

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 []

Answer 2

Una optimización fácil es usar conjuntos en lugar de listas para los conjuntos abierto y cerrado.

openSet   = set()
closedSet = set()

Esto hará que todas las in y not in pruebas O (1) en lugar de O ( n ).

Answer 3

Usaría los juegos como se dijo, pero también usaría un montón para encontrar el elemento mínimo (el que será el siguiente). Esto requeriría mantener tanto un openSet como un openHeap, pero la memoria no debería ser realmente un problema. Además, establece insertar en O (1) y montones en O (log N) para que sean rápidos. El único problema es que el módulo heapq no está hecho para usar claves con él. Personalmente, simplemente lo modificaría para usar las teclas. No debería ser muy difícil. Alternativamente, puede usar tuplas de (mosaico.H, mosaico) en el montón.

Además, seguiría la idea de aaronasterling de usar iteración en lugar de recursión, pero también agregaría elementos al final de la path y la path inversa al final. La razón es que insertar un artículo en el lugar 0 en una lista es muy lento, (O (N) creo), mientras que al agregarlo está O (1) si recuerdo correctamente. El código final para esa parte sería:

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

Pongo la ruta de retorno al final porque parece que debería hacerlo desde tu código.

Aquí está el código final que usa conjuntos, montones y lo que no:

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 []