Python: implementazione dell'algoritmo Astar

Question

Ho implementato l'algoritmo Astar per un problema su un giudice online relativo al labirinto date le posizioni di inizio e fine insieme a una griglia che rappresenta il labirinto. Produco la lunghezza del percorso insieme al percorso stesso. La seguente è l'implementazione in Python usando la distanza euclidea:

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)

Answer 1

self.start, self.grid, self.height, self.width = start, grid, height, width

Non li metterei tutti sulla stessa linea in questo modo. Penso che sarebbe molto più facile leggere distribuito su più righe:

self.start = start
self.grid = grid
self.height = height
self.width = width

---

Probabilmente avrei la Nodeclasse come toplevel invece che nidificata. Non credo che tu stia guadagnando molto ad averlo dentro AStar. Potresti chiamarlo _Nodeper renderlo "module-private" in modo che il tentativo di importarlo in un altro file possa generare avvisi.

In Node's __lt__implementazione, io non lo chiamerei il secondo parametro comparator. Un comparatore è qualcosa che confronta, mentre in questo caso è solo un altro nodo. other_nodeo qualcosa sarebbe più appropriato.

---

In heuristic, personalmente utilizzerei un elselì:

if (distance == "Manhattan"):
    return abs((x1 - x2) + abs(y1 - y2))
else:
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

Rende più chiaro che verrà eseguita solo una delle righe. Personalmente, trascuro solo elsein un caso come quello se iffosse un controllo delle precondizioni di "uscita anticipata", e voglio evitare di annidare l'intero resto della funzione all'interno di un blocco. Ma qui non è un problema.

---

nodeNeighbors( che dovrebbe esserenode_neighbors ) sarebbe più pulito suddiviso su più righe:

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]

Penso che questo renda molto più facile vedere cosa sta succedendo.

---

Ancora una volta, in molti punti stai assegnando due o più variabili su una riga:

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

Li spezzerei. Soprattutto una volta che si arriva a 3+ su una riga, affinché il lettore possa vedere quale variabile corrisponde a quale valore, dovrà contare da sinistra invece di controllare solo cosa c'è su ciascun lato di un file =.

---

In computePath, sembra che closedListdovrebbe essere un set. Non sembra che l'ordine sia importante con esso e neighbour in closedListsarà più veloce con un set di quanto non lo sarà con un elenco. Sembra però che openListsia necessario essere un elenco anche se a causa del passaggio a heapify.

---

Non credo che riassegnerei stdine stdout. La riassegnazione di stdinsembra completamente inutile e la modifica stdoutrenderà più difficile il debug successivo utilizzando le printistruzioni. Non vuoi necessariamente che tutto il testo stampato venga inviato al file.

Se necessario, puoi specificare su quale file vuoi stampare durante la stampa:

with open('output.txt', 'w') as out_f:
    print("To file!", file=out_f)