Python: implementación del algoritmo Astar
Implementé el algoritmo Astar para un problema en un juez en línea relacionado con las posiciones inicial y final del laberinto, junto con una cuadrícula que representa el laberinto. Produzco la longitud del camino junto con el camino en sí. La siguiente es la implementación en Python usando la distancia euclidiana:
import heapq, math, sys
infinity = float('inf')
class AStar():
def __init__(self, start, grid, height, width):
self.start, self.grid, self.height, self.width = start, grid, height, width
class Node():
def __init__(self, position, fscore=infinity, gscore=infinity, parent = None):
self.fscore, self.gscore, self.position, self.parent = fscore, gscore, position, parent
def __lt__(self, comparator):
return self.fscore < comparator.fscore
def heuristic(self, end, distance = "Euclidean"):
(x1, y1), (x2, y2) = self.start, end
if (distance == "Manhattan"):
return abs(x1 - x2) + abs(y1 - y2)
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
def nodeNeighbours(self, pos):
(x, y) = pos
return [(dx, dy) for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]
def getPath(self, endPoint):
current, path = endPoint, []
while current.position != self.start:
path.append(current.position)
current = current.parent
path.append(self.start)
return list(reversed(path))
def computePath(self, end):
openList, closedList, nodeDict = [], [], {}
currentNode = AStar.Node(self.start, fscore=self.heuristic(end), gscore = 0)
heapq.heappush(openList, currentNode)
while openList:
currentNode = heapq.heappop(openList)
if currentNode.position == end:
return self.getPath(currentNode)
else:
closedList.append(currentNode)
neighbours = []
for toCheck in self.nodeNeighbours(currentNode.position):
if toCheck not in nodeDict.keys():
nodeDict[toCheck] = AStar.Node(toCheck)
neighbours.append(nodeDict[toCheck])
for neighbour in neighbours:
newGscore = currentNode.gscore + 1
if neighbour in openList and newGscore < neighbour.gscore:
openList.remove(neighbour)
if newGscore < neighbour.gscore and neighbour in closedList:
closedList.remove(neighbour)
if neighbour not in openList and neighbour not in closedList:
neighbour.gscore = newGscore
neighbour.fscore = neighbour.gscore + self.heuristic(neighbour.position)
neighbour.parent = currentNode
heapq.heappush(openList, neighbour)
heapq.heapify(openList)
return None
if __name__ == '__main__':
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
matrix = [[int(num) for num in line.split()] for line in sys.stdin]
size = matrix.pop(0)
coordinates = matrix.pop(0)
n, m = size[0], size[1]
x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]
path = AStar((x1-1, y1-1), matrix, n, m).computePath((y2-1, x2-1))
print(len(path))
for pos in path:
print(pos[0] + 1, pos[1] + 1)
Respuestas
self.start, self.grid, self.height, self.width = start, grid, height, width
No los pondría todos en la misma línea de esa manera. Creo que sería mucho más fácil de leer en varias líneas:
self.start = start
self.grid = grid
self.height = height
self.width = width
Probablemente tendría la Nodeclase como nivel superior en lugar de anidada. No creo que estés ganando mucho por tenerlo dentro AStar. Puede asignarle un nombre _Nodepara que sea "privado del módulo", de modo que intentar importarlo a otro archivo genere advertencias.
En Nodela __lt__implementación de, no llamaría al segundo parámetro comparator. Un comparador es algo que compara, mientras que en este caso, es solo otro nodo. other_nodeo algo sería más apropiado.
En heuristic, personalmente haría uso de elseallí:
if (distance == "Manhattan"):
return abs((x1 - x2) + abs(y1 - y2))
else:
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
Deja más claro que solo se ejecutará una de las líneas. Personalmente, solo descuido el elseen un caso como ese si se iftrataba de una verificación de condición previa de "salida anticipada", y quiero evitar anidar el resto de la función dentro de un bloque. Sin embargo, eso no es un problema aquí.
nodeNeighbors( que debería sernode_neighbors ) sería más limpio dividido en varias líneas:
def nodeNeighbours(self, pos):
(x, y) = pos
return [(dx, dy)
for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]
Creo que eso hace que sea mucho más fácil ver lo que sucede en él.
Nuevamente, en muchos lugares está asignando dos o más variables en una línea:
(x1, y1), (x2, y2) = self.start, end
current, path = endPoint, []
openList, closedList, nodeDict = [], [], {}
x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]
Los rompería. Especialmente una vez que llegue a 3+ en una línea, para que el lector vea qué variable coincide con qué valor, necesitará contar desde la izquierda en lugar de simplemente verificar lo que hay a cada lado de un =.
En computePath, parece que closedListdebería ser un set. No parece que el orden importe con él, y neighbour in closedListserá más rápido con un conjunto que con una lista. Sin embargo, parece que openListse requiere que sea una lista debido a que se pasa a heapify.
No creo que reasigne stdiny stdout. La reasignación de stdinparece completamente innecesaria y el cambio stdoutdificultará la depuración posterior mediante printdeclaraciones. No es necesario que todo el texto impreso se envíe al archivo.
Si es necesario, puede especificar en qué archivo desea imprimir al imprimir:
with open('output.txt', 'w') as out_f:
print("To file!", file=out_f)