Python: implémentation de l'algorithme Astar

Question

J'ai implémenté l'algorithme Astar pour un problème sur un juge en ligne relatif au labyrinthe en fonction des positions de début et de fin avec une grille représentant le labyrinthe. Je sortie la longueur du chemin avec le chemin lui-même. Voici l'implémentation en Python en utilisant la distance euclidienne:

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

Je ne mettrais pas tout cela sur la même ligne comme ça. Je pense que ce serait beaucoup plus facile à lire réparti sur plusieurs lignes:

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

---

J'aurais probablement la Nodeclasse comme toplevel au lieu d'être imbriquée. Je ne pense pas que vous êtes gagnant beaucoup en ayant à l'intérieur AStar. Vous pouvez le nommer _Nodepour le rendre "module-private" afin que tenter de l'importer dans un autre fichier déclenche potentiellement des avertissements.

Dans Nodel' __lt__implémentation de, je n'appellerais pas le deuxième paramètre comparator. Un comparateur est quelque chose qui compare, alors que dans ce cas, ce n'est qu'un autre nœud. other_nodeou quelque chose serait plus approprié.

---

Dans heuristic, j'utiliserais personnellement un elselà-bas:

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

Cela indique plus clairement qu'une seule des lignes sera exécutée. Personnellement, je ne néglige le elsedans un cas comme celui-là que s'il ifs'agissait d'un contrôle de précondition "sortie anticipée", et je veux éviter d'imbriquer tout le reste de la fonction dans un bloc. Ce n'est pas un problème ici cependant.

---

nodeNeighbors( ce qui devrait êtrenode_neighbors ) serait plus propre brisé sur plusieurs lignes:

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]

Je pense que cela permet de voir beaucoup plus facilement ce qui se passe.

---

Encore une fois, dans de nombreux endroits, vous affectez deux ou plusieurs variables sur une seule ligne:

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

Je les briserais. Surtout une fois que vous arrivez à 3+ sur une ligne, pour que le lecteur voie quelle variable correspond à quelle valeur, il devra compter à partir de la gauche au lieu de simplement vérifier ce qui se trouve de chaque côté d'un =.

---

Dans computePath, il semble que closedListdevrait être un ensemble. Il ne semble pas que l'ordre compte avec lui, et neighbour in closedListsera plus rapide avec un ensemble qu'avec une liste. Il semble cependant openListnécessaire d'être une liste en raison de sa transmission heapify.

---

Je ne pense pas que je réaffecterais stdinet stdout. La réaffectation de stdinsemble totalement inutile et la modification stdoutrendra plus difficile le débogage ultérieur à l'aide d' printinstructions. Vous ne voulez pas nécessairement que tout le texte imprimé soit envoyé dans le fichier.

Si nécessaire, vous pouvez spécifier le fichier sur lequel vous souhaitez imprimer lors de l'impression:

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